Loading…

hardArraysSometimes asked

Maximum Subarray Sum

Q: How do you solve Maximum Subarray Sum using the Brute Force — All Subarrays approach?

When to use it: State it to anchor the definition, then note the O(n²) cost and the overflow trap on raw sums. The literal approach: enumerate every subarray. Fix a left endpoint `l`, walk the right endpoint `r` rightward, maintain the running sum reduced mod m, and keep the maximum residue seen. **Reduce mod m as you extend.** Don't store the raw running sum — with a[i] up to 10¹⁸ it overflows almost immediately. Keep `cur = (cur + a[r]) % m`; the maximum of `cur` over the inner loop is the best residue for that left endpoint. **Why it's the natural baseline.** The objective is defined over subarrays, so looping over all subarrays is the obvious correct thing. It's fine for small n and confirms the answer when testing the optimal version. **Why we don't ship it.** n up to 10⁵ gives ~5×10⁹ subarray steps — too slow. Prefix sums plus an ordered set collapse it to O(n log n). Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Maximum Subarray Sum using the Prefix Sums + Ordered Set (Optimal) approach?

When to use it: The answer they want: telescope subarrays into prefix differences, query the smallest greater prefix in O(log n). Define `pre[k]` as the sum of the first k elements mod m. Any subarray (l..r) has value `(pre[r+1] − pre[l] + m) mod m`. Sweep left to right computing the running prefix `pre` (mod m at every step), and keep all earlier prefixes in an ordered set. **Why 'smallest prefix strictly greater than pre[r]'.** We want `(pre[r] − pre[l]) mod m` as large as possible. If `pre[l] ≤ pre[r]`, the difference is in `[0, pre[r]]` — at most `pre[r]`, already covered by the candidate `pre[r]` itself (subtracting nothing, i.e. the subarray from the start). The only way to beat that is to make the difference *negative* and let `+ m` wrap it: pick `pre[l] > pre[r]`, giving `pre[r] − pre[l] + m = m − (pre[l] − pre[r])`. To make `m − (pre[l] − pre[r])` large, minimize `pre[l] − pre[r]`, i.e. choose the **smallest** `pre[l]` that is **strictly greater** than `pre[r]`. That's exactly an ordered-set 'higher' / upper-bound query. **Why pre[r] itself is a candidate.** The subarray starting at index 0 and ending at r has value `pre[r]` (nothing subtracted). Including `pre[r]` in the max covers that case for free, so we never need to store a sentinel 0 explicitly. **Why mod every step + long.** With a[i] up to 10¹⁸ and n up to 10⁵, the raw sum reaches 10²³ — long overflows. Reducing mod m each step keeps `pre` in `[0, m)`. The wrap `pre − s + m` reaches about 2×10¹⁴ for m near 10¹⁴, still safely inside 64-bit. Forgetting the `+ m` before the final `% m` yields a negative result and a wrong answer. **Why it's fast.** Insert and 'higher' query are O(log n) in a balanced ordered set (Java TreeSet). One of each per element gives O(n log n) — comfortable for 10⁵. Time complexity: O(n log n). Space complexity: O(n).

Arrays & Hashing · 75 of 83 · 10 min

Given an array of n elements and a modulo m, find the maximum value of (sum of elements of a subarray) mod m, taken over all non-empty contiguous subarrays.

In other words, maximize (a[l] + a[l+1] + … + a[r]) mod m over all 0 ≤ l ≤ r < n.

In plain English

Let pre[k] be the sum of the first k elements taken mod m. The value of subarray (l..r) mod m is (pre[r+1] − pre[l] + m) mod m. We want this as large as possible. For a fixed right endpoint, subtracting a slightly *larger* prefix wraps the difference up near m − 1, which is the maximum. So as we build prefixes left to right, we keep them in an ordered structure and, for each new prefix, query the smallest stored prefix strictly greater than it.

Examples

Example 1

Input: a = [3, 3, 9, 9, 5], m = 7
Output: 6
Note: Prefixes mod 7: 3, 6, 1, 3, 1. The subarray [3,3] sums to 6, and 6 mod 7 = 6 — the maximum achievable below 7.

Example 2

Input: a = [1, 2, 3], m = 2
Output: 1
Note: Subarray sums mod 2 are all 0 or 1; e.g. [1] = 1. The maximum residue is 1.

Example 3

Input: a = [1, 2, 3, 4, 5], m = 4
Output: 3
Note: Subarray [3] = 3 (3 mod 4 = 3) and [1,2] = 3 both hit 3, the largest residue below 4.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10¹⁴
1 ≤ a[i] ≤ 10¹⁸
The answer is a value in the range [0, m − 1]

Clarifying questions4First question: Are subarrays contiguous and non-empty?Explore questions

Q1.Are subarrays contiguous and non-empty?
Yes — contiguous and at least one element. The empty subarray (value 0) is not a candidate, though pre[r] itself naturally covers single elements and prefixes.
Q2.Can the raw sum overflow?
Easily — n up to 10⁵ times a[i] up to 10¹⁸ is 10²³. Always reduce mod m as you go and keep everything in 64-bit (long).
Q3.Why subtract a larger prefix, not a smaller one?
If pre[l] > pre[r], then pre[r] − pre[l] is negative; adding m gives a large positive residue near m − 1. The closer pre[l] is just above pre[r], the closer the result to m − 1.
Q4.Is m guaranteed to fit in a long?
Yes, m ≤ 10¹⁴ fits in 64-bit, and pre − s + m ≤ ~2×10¹⁴ also fits comfortably.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Maximize (sum of a contiguous subarray) mod m. Work with prefix sums taken mod m: a subarray (l..r) has value (pre[r] − pre[l−1] + m) mod m. To make that big you want pre[l−1] to be the *smallest prefix strictly greater* than pre[r] — then the result is close to m−1. Sweep left to right keeping prior prefixes in an ordered set (TreeSet); at each r take max(pre[r], (pre[r] − higher(pre[r]) + m) mod m). O(n log n). Take the running sum mod m every step and use long, or it overflows.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you express the modular subarray value via prefix sums and realize that maximizing (pre[r] − pre[l−1]) mod m means finding the smallest prefix strictly greater than pre[r] — an ordered-set / binary-search query.

Where candidates slip

Accumulating the raw sum and overflowing, forgetting the +m before the final mod (negative result), or scanning all earlier prefixes for an O(n²) blowup.

How to stand out

Explain why 'smallest prefix greater than pre[r]' maximizes the wrapped value, mention that pre[r] alone covers the prefix-starting case, and call out taking mod each step plus using long before being prompted.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — All Subarrays	`O(n²)`	`O(1)`	State it to anchor the definition, then note the O(n²) cost and the overflow trap on raw sums.	Read
2	Prefix Sums + Ordered Set (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want: telescope subarrays into prefix differences, query the smallest greater prefix in O(log n).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewpre = (pre + x) mod ms exists?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — All Subarrays

TimeO(n²)SpaceO(1)

State it to anchor the definition, then note the O(n²) cost and the overflow trap on raw sums.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the most direct way to evaluate every contiguous subarray's sum mod m?

2Hint 2Explore hint

Fix the left end l, extend the right end r one step at a time, keeping a running sum reduced mod m.

3Hint 3Explore hint

Track the maximum (running sum) mod m across all (l, r).

A · Core idea

The literal approach: enumerate every subarray. Fix a left endpoint l, walk the right endpoint r rightward, maintain the running sum reduced mod m, and keep the maximum residue seen.

Reduce mod m as you extend. Don't store the raw running sum — with a[i] up to 10¹⁸ it overflows almost immediately. Keep cur = (cur + a[r]) % m; the maximum of cur over the inner loop is the best residue for that left endpoint.

Why it's the natural baseline. The objective is defined over subarrays, so looping over all subarrays is the obvious correct thing. It's fine for small n and confirms the answer when testing the optimal version.

Why we don't ship it. n up to 10⁵ gives ~5×10⁹ subarray steps — too slow. Prefix sums plus an ordered set collapse it to O(n log n).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [3, 3, 9, 9, 5], m = 7

Array state

l=0, r=1

sum 6, 6 mod 7 = 6

l ↓

[0]

r ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic long maxSubarrayModBrute(long[] a, long m) { int n = a.length; long best = 0; for (int l = 0; l < n; l++) { long cur = 0;Explore the full code

solution.javaJava

Brute Force — All Subarrays — reference

2 teaching notes

1
public long maxSubarrayModBrute(long[] a, long m) {
2
    int n = a.length;
3
    long best = 0;
4
    for (int l = 0; l < n; l++) {
5
        long cur = 0;
6
        for (int r = l; r < n; r++) {
7
            cur = (cur + a[r]) % m;     // reduce each step — never store raw sum
8
            // Every (l, r) residue is a candidate for the maximum.
9
            best = Math.max(best, cur);
10
        }
11
    }
12
    return best;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Re-summing overlapping subarrays is wasted work: the sum of (l..r) and (l..r+1) differ by one element. That overlap is the cue to switch to prefix sums, where any subarray sum is a single subtraction.

ComplexityO(n²) time, O(1) space — For each of n start points you extend up to n endpoints → n²/2 subarrays, O(n²).

E · Edge cases and pitfalls3Storing the raw running sum and overflowing — reduce mod m each step.Explore edge cases

Pitfalls

Storing the raw running sum and overflowing — reduce mod m each step.
Resetting cur incorrectly between left endpoints.
Running O(n²) on n = 10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Prefix Sums + Ordered Set (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want: telescope subarrays into prefix differences, query the smallest greater prefix in O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the subarray (l..r) value as (pre[r] − pre[l−1] + m) mod m. For a fixed r, which earlier prefix makes this largest?

2Hint 2Explore hint

If you pick pre[l−1] just slightly greater than pre[r], the subtraction goes negative and +m wraps it near m − 1 — the biggest possible.

3Hint 3Explore hint

Maintain earlier prefixes in an ordered set; for each pre[r] query the smallest stored value strictly greater than pre[r]. Also consider pre[r] itself.

A · Core idea

Define pre[k] as the sum of the first k elements mod m. Any subarray (l..r) has value (pre[r+1] − pre[l] + m) mod m. Sweep left to right computing the running prefix pre (mod m at every step), and keep all earlier prefixes in an ordered set.

Why 'smallest prefix strictly greater than pre[r]'. We want (pre[r] − pre[l]) mod m as large as possible. If pre[l] ≤ pre[r], the difference is in [0, pre[r]] — at most pre[r], already covered by the candidate pre[r] itself (subtracting nothing, i.e. the subarray from the start). The only way to beat that is to make the difference negative and let + m wrap it: pick pre[l] > pre[r], giving pre[r] − pre[l] + m = m − (pre[l] − pre[r]). To make m − (pre[l] − pre[r]) large, minimize pre[l] − pre[r], i.e. choose the smallest pre[l] that is strictly greater than pre[r]. That's exactly an ordered-set 'higher' / upper-bound query.

Why pre[r] itself is a candidate. The subarray starting at index 0 and ending at r has value pre[r] (nothing subtracted). Including pre[r] in the max covers that case for free, so we never need to store a sentinel 0 explicitly.

Why mod every step + long. With a[i] up to 10¹⁸ and n up to 10⁵, the raw sum reaches 10²³ — long overflows. Reducing mod m each step keeps pre in [0, m). The wrap pre − s + m reaches about 2×10¹⁴ for m near 10¹⁴, still safely inside 64-bit. Forgetting the + m before the final % m yields a negative result and a wrong answer.

Why it's fast. Insert and 'higher' query are O(log n) in a balanced ordered set (Java TreeSet). One of each per element gives O(n log n) — comfortable for 10⁵.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [3, 3, 9, 9, 5], m = 7

Array state

after x=3,3

pre=6 is the maximum residue seen

[0]

pre ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Prefix Sums + Ordered Set (Optimal) — optimal

4 teaching notes

1
public long maxSubarrayMod(long[] a, long m) {
2
    java.util.TreeSet<Long> seen = new java.util.TreeSet<>();
3
    long pre = 0, best = 0;
4
    for (long x : a) {
5
        pre = (pre + x % m) % m;            // reduce every step — no overflow
6
        best = Math.max(best, pre);          // subarray starting at index 0
7
        Long higher = seen.higher(pre);      // smallest stored prefix > pre
8
        if (higher != null) {
9
            // + m keeps the subtraction non-negative before the final mod.
10
            best = Math.max(best, (pre - higher + m) % m);
11
        }
12
        seen.add(pre);
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

The modular objective rewards a prefix that's just above the current one — turning 'maximize a wrapped difference' into a clean 'find the successor of pre[r]' query. Prefix sums telescope the subarray into a single subtraction, and an ordered set makes the successor lookup logarithmic. This 'prefix sum + ordered structure' duo recurs in count-of-range-sum and similar problems.

ComplexityO(n log n) time, O(n) space — Each element does one ordered-set insert and one 'just greater' query, both O(log n) → O(n log n) total. The set holds up to n prefixes → O(n) space.

E · Edge cases and pitfalls5a = [m, 2m, 3m], m arbitrary — Every prefix residue is 0; no higher prefix exists, best stays 0. Multiples of m contribute nothing.Explore edge cases

Edge cases handled

a = [m, 2m, 3m], m arbitraryEvery prefix residue is 0; no higher prefix exists, best stays 0. Multiples of m contribute nothing.
a = [m-1], mpre = m−1; best = m−1, the maximum possible residue from a single element.

Pitfalls

Omitting the + m before the final % m — a negative dividend gives a wrong (often negative) result.
Querying for the largest smaller prefix instead of the smallest greater one — that doesn't maximize the wrap.
Letting the raw sum grow unbounded — reduce mod m each step and keep long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long maxSubarrayMod(long[] a, long m) { java.util.TreeSet<Long> seen = new java.util.TreeSet<>(); long pre = 0, best = 0; for (long x : a) { pre = (pre + x % m) % m; // reduce every step — no overflowExplore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Negative residue from missing + m

pre − higher is negative when higher > pre. Taking % m directly on a negative value yields a negative result in Java.

Explore the code comparison

Don't write this

best = Math.max(best, (pre - higher) % m);

Write this instead

best = Math.max(best, (pre - higher + m) % m);

Overflow from un-reduced sums

a[i] up to 10¹⁸ over 10⁵ elements reaches 10²³ — long overflows. Reduce mod m at every step.

Explore the code comparison

Don't write this

pre = pre + x;            // grows without bound
best = Math.max(best, pre % m);

Write this instead

pre = (pre + x % m) % m;  // stays in [0, m)

Wrong ordered-set query direction

Maximizing the wrapped value needs the smallest prefix strictly GREATER than pre. Picking the largest smaller prefix minimizes, not maximizes.

Explore the code comparison

Don't write this

idx = bisect.bisect_left(seen, pre) - 1   # largest <= pre

Write this instead

idx = bisect.bisect_right(seen, pre)      # smallest > pre

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix sums mod m + ordered-set 'smallest greater' query

Code pattern to memorize

pre = 0; best = 0; set = {}
for x in a:
    pre = (pre + x) % m
    best = max(best, pre)
    s = set.higher(pre)        # smallest stored > pre
    if s exists: best = max(best, (pre - s + m) % m)
    set.add(pre)
return best

Rules to remember

1Subarray sum mod m = (pre[r] − pre[l−1] + m) % m — the + m keeps it non-negative after subtraction.
2To maximize that, subtract the smallest prefix that is strictly greater than pre[r]; that pushes the wrapped result toward m−1.
3pre[r] itself is a valid candidate — it's the subarray starting at index 0, equivalent to subtracting nothing.
4Reduce the running sum mod m at every step; never accumulate the raw sum, it overflows fast.
5Use long everywhere: m can be ~10¹⁴, so pre − s + m reaches ~2×10¹⁴, beyond 32-bit.

Use this pattern when

Maximize / optimize a subarray quantity that telescopes through prefix sums
A modular objective where you need the closest prefix on one side (just-greater / just-smaller)
Repeated 'smallest element greater than x' queries over a growing set

Choose another pattern when

Plain maximum subarray sum (no modulo) → Kadane's algorithm, O(n), no ordered set
You need the actual subarray indices, not just the value → track positions alongside
m is tiny (say ≤ a few thousand) → a counting array over residues can beat the ordered set

Interview takeaway

Turn 'best subarray under mod' into 'for each prefix, find the smallest earlier prefix just above it'. Prefix sums make the subarray telescope, and an ordered set answers the just-greater query in O(log n), giving O(n log n) overall.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPrefix sums plus an ordered set: telescope a subarray objective into a difference of prefixes, then answer a successor/predecessor query in O(log n). Here the modular max wants the smallest prefix just above the current one. Same toolbox as Count of Range Sum and other prefix-difference problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray (Kadane)
Without the modulo, the classic max subarray sum is Kadane's O(n) running max.
Subarray Sum Equals K
Coming soon
Prefix sums + hash map for counting subarrays with an exact sum.
Count of Range Sum
Coming soon
Prefix sums + ordered structure / BIT to count sums in a range — same toolbox.

Same pattern

←

Ice Cream Parlor

Continue · Next problem

Minimum Loss

hardArraysSometimes asked

Maximum Subarray Sum

Arrays & Hashing · 75 of 83 · 10 min

Given an array of n elements and a modulo m, find the maximum value of (sum of elements of a subarray) mod m, taken over all non-empty contiguous subarrays.

In other words, maximize (a[l] + a[l+1] + … + a[r]) mod m over all 0 ≤ l ≤ r < n.

In plain English

Examples

Example 1

Input: a = [3, 3, 9, 9, 5], m = 7
Output: 6
Note: Prefixes mod 7: 3, 6, 1, 3, 1. The subarray [3,3] sums to 6, and 6 mod 7 = 6 — the maximum achievable below 7.

Example 2

Input: a = [1, 2, 3], m = 2
Output: 1
Note: Subarray sums mod 2 are all 0 or 1; e.g. [1] = 1. The maximum residue is 1.

Example 3

Input: a = [1, 2, 3, 4, 5], m = 4
Output: 3
Note: Subarray [3] = 3 (3 mod 4 = 3) and [1,2] = 3 both hit 3, the largest residue below 4.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10¹⁴
1 ≤ a[i] ≤ 10¹⁸
The answer is a value in the range [0, m − 1]

Clarifying questions4First question: Are subarrays contiguous and non-empty?Explore questions

Q1.Are subarrays contiguous and non-empty?
Yes — contiguous and at least one element. The empty subarray (value 0) is not a candidate, though pre[r] itself naturally covers single elements and prefixes.
Q2.Can the raw sum overflow?
Easily — n up to 10⁵ times a[i] up to 10¹⁸ is 10²³. Always reduce mod m as you go and keep everything in 64-bit (long).
Q3.Why subtract a larger prefix, not a smaller one?
If pre[l] > pre[r], then pre[r] − pre[l] is negative; adding m gives a large positive residue near m − 1. The closer pre[l] is just above pre[r], the closer the result to m − 1.
Q4.Is m guaranteed to fit in a long?
Yes, m ≤ 10¹⁴ fits in 64-bit, and pre − s + m ≤ ~2×10¹⁴ also fits comfortably.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Accumulating the raw sum and overflowing, forgetting the +m before the final mod (negative result), or scanning all earlier prefixes for an O(n²) blowup.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — All Subarrays	`O(n²)`	`O(1)`	State it to anchor the definition, then note the O(n²) cost and the overflow trap on raw sums.	Read
2	Prefix Sums + Ordered Set (Optimal)Optimal	`O(n log n)`	`O(n)`	The answer they want: telescope subarrays into prefix differences, query the smallest greater prefix in O(log n).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — All Subarrays

TimeO(n²)SpaceO(1)

State it to anchor the definition, then note the O(n²) cost and the overflow trap on raw sums.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the most direct way to evaluate every contiguous subarray's sum mod m?

2Hint 2Explore hint

Fix the left end l, extend the right end r one step at a time, keeping a running sum reduced mod m.

3Hint 3Explore hint

Track the maximum (running sum) mod m across all (l, r).

A · Core idea

The literal approach: enumerate every subarray. Fix a left endpoint l, walk the right endpoint r rightward, maintain the running sum reduced mod m, and keep the maximum residue seen.

Why we don't ship it. n up to 10⁵ gives ~5×10⁹ subarray steps — too slow. Prefix sums plus an ordered set collapse it to O(n log n).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [3, 3, 9, 9, 5], m = 7

Array state

l=0, r=1

sum 6, 6 mod 7 = 6

l ↓

[0]

r ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic long maxSubarrayModBrute(long[] a, long m) { int n = a.length; long best = 0; for (int l = 0; l < n; l++) { long cur = 0;Explore the full code

solution.javaJava

Brute Force — All Subarrays — reference

2 teaching notes

1
public long maxSubarrayModBrute(long[] a, long m) {
2
    int n = a.length;
3
    long best = 0;
4
    for (int l = 0; l < n; l++) {
5
        long cur = 0;
6
        for (int r = l; r < n; r++) {
7
            cur = (cur + a[r]) % m;     // reduce each step — never store raw sum
8
            // Every (l, r) residue is a candidate for the maximum.
9
            best = Math.max(best, cur);
10
        }
11
    }
12
    return best;
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — For each of n start points you extend up to n endpoints → n²/2 subarrays, O(n²).

E · Edge cases and pitfalls3Storing the raw running sum and overflowing — reduce mod m each step.Explore edge cases

Pitfalls

Storing the raw running sum and overflowing — reduce mod m each step.
Resetting cur incorrectly between left endpoints.
Running O(n²) on n = 10⁵ and timing out.

03.2

Approach 2 of 2 · Optimal

Prefix Sums + Ordered Set (Optimal)

TimeO(n log n)SpaceO(n)

The answer they want: telescope subarrays into prefix differences, query the smallest greater prefix in O(log n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Write the subarray (l..r) value as (pre[r] − pre[l−1] + m) mod m. For a fixed r, which earlier prefix makes this largest?

2Hint 2Explore hint

If you pick pre[l−1] just slightly greater than pre[r], the subtraction goes negative and +m wraps it near m − 1 — the biggest possible.

3Hint 3Explore hint

Maintain earlier prefixes in an ordered set; for each pre[r] query the smallest stored value strictly greater than pre[r]. Also consider pre[r] itself.

A · Core idea

Why it's fast. Insert and 'higher' query are O(log n) in a balanced ordered set (Java TreeSet). One of each per element gives O(n log n) — comfortable for 10⁵.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [3, 3, 9, 9, 5], m = 7

Array state

after x=3,3

pre=6 is the maximum residue seen

[0]

pre ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Prefix Sums + Ordered Set (Optimal) — optimal

4 teaching notes

1
public long maxSubarrayMod(long[] a, long m) {
2
    java.util.TreeSet<Long> seen = new java.util.TreeSet<>();
3
    long pre = 0, best = 0;
4
    for (long x : a) {
5
        pre = (pre + x % m) % m;            // reduce every step — no overflow
6
        best = Math.max(best, pre);          // subarray starting at index 0
7
        Long higher = seen.higher(pre);      // smallest stored prefix > pre
8
        if (higher != null) {
9
            // + m keeps the subtraction non-negative before the final mod.
10
            best = Math.max(best, (pre - higher + m) % m);
11
        }
12
        seen.add(pre);
13
    }
14
    return best;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — Each element does one ordered-set insert and one 'just greater' query, both O(log n) → O(n log n) total. The set holds up to n prefixes → O(n) space.

E · Edge cases and pitfalls5a = [m, 2m, 3m], m arbitrary — Every prefix residue is 0; no higher prefix exists, best stays 0. Multiples of m contribute nothing.Explore edge cases

Edge cases handled

a = [m, 2m, 3m], m arbitraryEvery prefix residue is 0; no higher prefix exists, best stays 0. Multiples of m contribute nothing.
a = [m-1], mpre = m−1; best = m−1, the maximum possible residue from a single element.

Pitfalls

Omitting the + m before the final % m — a negative dividend gives a wrong (often negative) result.
Querying for the largest smaller prefix instead of the smallest greater one — that doesn't maximize the wrap.
Letting the raw sum grow unbounded — reduce mod m each step and keep long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Negative residue from missing + m

pre − higher is negative when higher > pre. Taking % m directly on a negative value yields a negative result in Java.

Explore the code comparison

Don't write this

best = Math.max(best, (pre - higher) % m);

Write this instead

best = Math.max(best, (pre - higher + m) % m);

Overflow from un-reduced sums

a[i] up to 10¹⁸ over 10⁵ elements reaches 10²³ — long overflows. Reduce mod m at every step.

Explore the code comparison

Don't write this

pre = pre + x;            // grows without bound
best = Math.max(best, pre % m);

Write this instead

pre = (pre + x % m) % m;  // stays in [0, m)

Wrong ordered-set query direction

Maximizing the wrapped value needs the smallest prefix strictly GREATER than pre. Picking the largest smaller prefix minimizes, not maximizes.

Explore the code comparison

Don't write this

idx = bisect.bisect_left(seen, pre) - 1   # largest <= pre

Write this instead

idx = bisect.bisect_right(seen, pre)      # smallest > pre

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Prefix sums mod m + ordered-set 'smallest greater' query

Code pattern to memorize

pre = 0; best = 0; set = {}
for x in a:
    pre = (pre + x) % m
    best = max(best, pre)
    s = set.higher(pre)        # smallest stored > pre
    if s exists: best = max(best, (pre - s + m) % m)
    set.add(pre)
return best

Rules to remember

1Subarray sum mod m = (pre[r] − pre[l−1] + m) % m — the + m keeps it non-negative after subtraction.
2To maximize that, subtract the smallest prefix that is strictly greater than pre[r]; that pushes the wrapped result toward m−1.
3pre[r] itself is a valid candidate — it's the subarray starting at index 0, equivalent to subtracting nothing.
4Reduce the running sum mod m at every step; never accumulate the raw sum, it overflows fast.
5Use long everywhere: m can be ~10¹⁴, so pre − s + m reaches ~2×10¹⁴, beyond 32-bit.

Use this pattern when

Maximize / optimize a subarray quantity that telescopes through prefix sums
A modular objective where you need the closest prefix on one side (just-greater / just-smaller)
Repeated 'smallest element greater than x' queries over a growing set

Choose another pattern when

Plain maximum subarray sum (no modulo) → Kadane's algorithm, O(n), no ordered set
You need the actual subarray indices, not just the value → track positions alongside
m is tiny (say ≤ a few thousand) → a counting array over residues can beat the ordered set

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray (Kadane)
Without the modulo, the classic max subarray sum is Kadane's O(n) running max.
Subarray Sum Equals K
Coming soon
Prefix sums + hash map for counting subarrays with an exact sum.
Count of Range Sum
Coming soon
Prefix sums + ordered structure / BIT to count sums in a range — same toolbox.

Same pattern

←

Ice Cream Parlor

Continue · Next problem

Minimum Loss