Abstract / Summary

Adjust elements in an array to make their total sum divisible by a given number p.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 43% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the smallest contiguous sub-array that can be removed so that the sum of the remaining elements becomes divisible by a given integer p. The algorithm works by augmenting the original array with sentinel zeros, building a prefix-sum map keyed by modulo values, and then scanning the array backwards to locate the optimal removal length. Throughout the process it leverages constant-time list operations and avoids recomputation of sums, which yields an efficient solution for large inputs.

Prefix-sum construction with modulo buckets

The first major phase computes cumulative sums while grouping indices by the remainder of the sum modulo p. This grouping enables rapid lookup of positions that can balance a target remainder later on.

remain = defaultdict(list)
have = 0
for i, n in enumerate(nums):
    have += n
    remain[have % p].append(i)

Each entry in remain holds a list of indices where a particular remainder occurs. By storing the indices in the order they appear, the algorithm can later prune entries that lie to the right of the current scanning position.

Early exit when the total sum is already divisible

Before any further work, the code checks whether the total sum of the augmented array satisfies the divisibility condition. If the remainder is zero, no removal is necessary and the function returns immediately.

if have % p == 0:
    return 0

This guard eliminates unnecessary work for the common case where the input already meets the requirement.

Backward scan to locate the minimal removable segment

The core search proceeds from the end of the augmented array toward the front. At each step it updates a running suffix sum, computes its remainder, and determines the complementary remainder needed to achieve a total sum divisible by p.

result = size
have = 0
for i in reversed(range(length)):
    n = nums[i]
    have += n
    mod = have % p
    need = p - mod if mod > 0 else 0

The variable need represents the remainder that must be found on the left side of the current index to form a valid removal window.

Pruning of right-side positions

Because the scan moves leftward, any indices stored in remain[need] that are greater than or equal to the current position cannot contribute to a valid sub-array. The algorithm discards such entries in a tight loop, ensuring that the remaining list always contains only candidates on the left.

while remain[need] and remain[need][-1] >= i:
    remain[need].pop()

By popping from the end of the list, the operation runs in amortized constant time, and the list stays sorted in decreasing order relative to the current scan direction.

Updating the best answer

If after pruning there is still at least one index left in remain[need], the distance between the current position and the nearest left candidate yields a candidate removal length. The algorithm updates the best result accordingly.

if remain[need]:
    remove = i - remain[need][-1] - 1
    result = min(result, remove)

The subtraction of one accounts for the exclusive nature of the removal window, and the min call preserves the smallest length found so far.

Edge-case handling through sentinel zeros

The initial augmentation of the input list with a leading and trailing zero simplifies boundary conditions. By guaranteeing that there is always a zero at both ends, the algorithm avoids special checks for sub-arrays that start at index zero or end at the last element. This design also ensures that the removal length never exceeds the original array size, as the sentinel values are never counted toward the final answer.

nums = [0] + nums + [0]

Performance-focused data structures

The use of defaultdict(list) provides on-demand creation of buckets without explicit existence checks, reducing branching overhead. Storing indices in lists rather than more complex structures keeps memory layout compact and cache-friendly. The backward iteration combined with in-place popping eliminates the need for binary search or additional pointer arithmetic, resulting in a tight inner loop that operates with minimal instruction count.

Final result determination

After the scan completes, the algorithm returns the smallest removal length found, or -1 if no valid sub-array exists. The comparison against the original size ensures that sentinel zeros do not inflate the answer.

return result if result < size else -1

Through careful construction of prefix sums, strategic use of modulo buckets, and a reverse scan that prunes irrelevant candidates on the fly, the code delivers a concise and performant solution to the minimum sub-array removal problem.

Imagine a big box of numbered blocks sitting in a row. The goal is to take away a small section of these blocks so that what stays behind can be shared equally among a group of people. If the group has a specific number of members, we want to make sure the total number of blocks left over is something that divides perfectly.

To solve this, the computer looks at all the blocks from the left side and keeps a running total of how many there are. It writes down each total and keeps track of which blocks were used. Because the group has a certain size, the computer only cares about the leftovers after sharing, which is like keeping track of the remainders.

After looking at the blocks from left to right, the computer turns around and looks at the blocks starting from the right side. It now knows exactly how many blocks it needs to toss out to make everything balance out perfectly. By checking the notebook where it wrote down the positions of the blocks from the first pass, it can quickly find the smallest slice of blocks that solves the problem. If it finds a way to take away just a few blocks, it remembers that as the best way to do it. Otherwise, it decides that the task might be impossible, so it stops and says so.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++	JS	Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality