Subarray with Equal Number of 0s and 1s

🎯

Subarray with Equal Number of 0s and 1s

mediumHASH_MAPAmazonGoogle

Imagine analyzing a binary signal to find the longest balanced segment where zeros and ones appear equally, crucial for error detection in communication systems.

💡 This problem requires tracking a running state (difference between counts of 0s and 1s) rather than just values. Beginners often struggle because they try to count zeros and ones separately or check all subarrays naively, missing the insight that prefix sums and hashing can optimize the search.

📋

Problem Statement

Given a binary array nums, find the length of the longest contiguous subarray with an equal number of 0s and 1s. Return the length of such a subarray.

1 ≤ nums.length ≤ 10^5nums[i] is either 0 or 1

💡

Example

Input"[0,1]"

Output2

The entire array has equal number of 0s and 1s.

Input"[0,1,0]"

Output2

The longest subarray with equal 0s and 1s is [0,1] or [1,0].

Input"[0,0,1,0,0,0,1,1]"

Output6

The longest subarray is [1,0,0,0,1,1] with equal 0s and 1s.

• All zeros → output 0 (no equal subarray)
• All ones → output 0 (no equal subarray)
• Single element array → output 0 (cannot have equal 0s and 1s)
• Array with alternating 0 and 1 → output equals array length (entire array balanced)

⚠️

Common Mistakes

Not transforming 0 to -1 before prefix sum

Prefix sums do not reflect balance, leading to incorrect results

✅ Replace 0 with -1 when computing prefix sums

Not initializing prefix sum 0 at index -1 in hash map

Subarrays starting at index 0 are missed, causing off-by-one errors

✅ Initialize hash map with {0: -1} before iteration

Updating first occurrence of prefix sum multiple times

Longest subarray length is underestimated because only first occurrence matters

✅ Only set first occurrence if prefix sum not already in map/array

Using nested loops for large input arrays

Solution times out or is too slow for big inputs

✅ Use prefix sum + hash map approach for O(n) time

🧠

Brute Force (Nested Loops Checking All Subarrays)

💡 Starting with brute force helps understand the problem's nature by explicitly checking every possible subarray, which clarifies what 'equal number of 0s and 1s' means in practice.

Intuition

Check every subarray and count zeros and ones to see if they are equal. Keep track of the maximum length found.

Algorithm

1. Initialize max_length to 0.
2. Use two nested loops to consider every subarray.
3. For each subarray, count zeros and ones.
4. If counts are equal, update max_length if this subarray is longer.

💡 The nested loops and counting inside them make this approach straightforward but inefficient, which is why it’s a good starting point to understand the problem.

</>

Code

def findMaxLength(nums):
    max_length = 0
    n = len(nums)
    for start in range(n):
        count0 = 0
        count1 = 0
        for end in range(start, n):
            if nums[end] == 0:
                count0 += 1
            else:
                count1 += 1
            if count0 == count1:
                max_length = max(max_length, end - start + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))  # Expected output: 4

Line Notes

max_length = 0Initialize max_length to track the longest balanced subarray found so far

for start in range(n)Outer loop picks the start index of the subarray

for end in range(start, n)Inner loop picks the end index of the subarray

if count0 == count1Check if current subarray has equal zeros and ones to update max_length

public class Solution {
    public static int findMaxLength(int[] nums) {
        int maxLength = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int count0 = 0, count1 = 0;
            for (int end = start; end < n; end++) {
                if (nums[end] == 0) count0++;
                else count1++;
                if (count0 == count1) {
                    maxLength = Math.max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,1,1,1,0};
        System.out.println(findMaxLength(nums)); // Expected output: 4
    }
}

Line Notes

int maxLength = 0;Initialize maxLength to store longest balanced subarray length

for (int start = 0; start < n; start++)Outer loop selects start index of subarray

for (int end = start; end < n; end++)Inner loop selects end index of subarray

if (count0 == count1)Update maxLength if current subarray has equal zeros and ones

#include <iostream>
#include <vector>
using namespace std;

int findMaxLength(vector<int>& nums) {
    int maxLength = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int count0 = 0, count1 = 0;
        for (int end = start; end < n; end++) {
            if (nums[end] == 0) count0++;
            else count1++;
            if (count0 == count1) {
                maxLength = max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl; // Expected output: 4
    return 0;
}

Line Notes

int maxLength = 0;Initialize maxLength to track longest balanced subarray

for (int start = 0; start < n; start++)Outer loop picks start index

for (int end = start; end < n; end++)Inner loop picks end index

if (count0 == count1)Update maxLength if subarray has equal zeros and ones

function findMaxLength(nums) {
    let maxLength = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let count0 = 0, count1 = 0;
        for (let end = start; end < n; end++) {
            if (nums[end] === 0) count0++;
            else count1++;
            if (count0 === count1) {
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0])); // Expected output: 4

Line Notes

let maxLength = 0;Initialize maxLength to store longest balanced subarray length

for (let start = 0; start < n; start++)Outer loop selects start index

for (let end = start; end < n; end++)Inner loop selects end index

if (count0 === count1)Update maxLength if current subarray is balanced

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops generate all subarrays (n*(n+1)/2), and counting zeros and ones inside the inner loop is O(1) per element, so total O(n^2).

💡 For n=1000, this means about 1,000,000 operations, which is slow but still feasible; for n=10^5, it becomes impractical.

Interview Verdict: TLE for large inputs; only useful to introduce the problem

This approach is too slow for big inputs but helps understand the problem and correctness before optimizing.

🧠

Prefix Sum with Hash Map to Track First Occurrence

💡 This approach introduces a key insight: transform the problem by replacing 0s with -1s and track prefix sums to find subarrays with sum zero, enabling O(n) time complexity.

Intuition

Replace 0 with -1, so equal number of 0s and 1s means prefix sum difference is zero. Use a hash map to store first occurrence of each prefix sum to quickly find longest subarray.

Algorithm

1. Initialize a hash map with prefix sum 0 at index -1.
2. Iterate through the array, replacing 0 with -1 and computing prefix sums.
3. If prefix sum has been seen before, update max_length with distance between current and first occurrence indices.
4. Otherwise, store the current prefix sum and index in the hash map.

💡 The key is recognizing that equal zeros and ones correspond to prefix sums repeating, which allows constant time lookups for subarray lengths.

</>

Code

def findMaxLength(nums):
    prefix_sum = 0
    max_length = 0
    first_occurrence = {0: -1}
    for i, num in enumerate(nums):
        prefix_sum += -1 if num == 0 else 1
        if prefix_sum in first_occurrence:
            max_length = max(max_length, i - first_occurrence[prefix_sum])
        else:
            first_occurrence[prefix_sum] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))  # Expected output: 4

Line Notes

prefix_sum = 0Initialize prefix_sum to track running sum of transformed array

first_occurrence = {0: -1}Store prefix sum 0 at index -1 to handle subarrays starting at index 0

prefix_sum += -1 if num == 0 else 1Transform 0 to -1 and add to prefix_sum to track balance

if prefix_sum in first_occurrenceCheck if prefix_sum seen before to find balanced subarray length

import java.util.*;
public class Solution {
    public static int findMaxLength(int[] nums) {
        Map<Integer, Integer> firstOccurrence = new HashMap<>();
        firstOccurrence.put(0, -1);
        int prefixSum = 0, maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += (nums[i] == 0) ? -1 : 1;
            if (firstOccurrence.containsKey(prefixSum)) {
                maxLength = Math.max(maxLength, i - firstOccurrence.get(prefixSum));
            } else {
                firstOccurrence.put(prefixSum, i);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,1,1,1,0};
        System.out.println(findMaxLength(nums)); // Expected output: 4
    }
}

Line Notes

Map<Integer, Integer> firstOccurrence = new HashMap<>();Hash map to store first occurrence of each prefix sum

firstOccurrence.put(0, -1);Initialize prefix sum 0 at index -1 for subarrays starting at 0

prefixSum += (nums[i] == 0) ? -1 : 1;Transform 0 to -1 and update prefix sum

if (firstOccurrence.containsKey(prefixSum))Check if prefix sum seen before to update maxLength

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findMaxLength(vector<int>& nums) {
    unordered_map<int, int> firstOccurrence;
    firstOccurrence[0] = -1;
    int prefixSum = 0, maxLength = 0;
    for (int i = 0; i < nums.size(); i++) {
        prefixSum += (nums[i] == 0) ? -1 : 1;
        if (firstOccurrence.find(prefixSum) != firstOccurrence.end()) {
            maxLength = max(maxLength, i - firstOccurrence[prefixSum]);
        } else {
            firstOccurrence[prefixSum] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl; // Expected output: 4
    return 0;
}

Line Notes

unordered_map<int, int> firstOccurrence;Hash map to store first occurrence indices of prefix sums

firstOccurrence[0] = -1;Initialize prefix sum 0 at index -1 for subarrays starting at 0

prefixSum += (nums[i] == 0) ? -1 : 1;Transform 0 to -1 and update prefix sum

if (firstOccurrence.find(prefixSum) != firstOccurrence.end())Check if prefix sum seen before to update maxLength

function findMaxLength(nums) {
    const firstOccurrence = new Map();
    firstOccurrence.set(0, -1);
    let prefixSum = 0, maxLength = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += (nums[i] === 0) ? -1 : 1;
        if (firstOccurrence.has(prefixSum)) {
            maxLength = Math.max(maxLength, i - firstOccurrence.get(prefixSum));
        } else {
            firstOccurrence.set(prefixSum, i);
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0])); // Expected output: 4

Line Notes

const firstOccurrence = new Map();Map to store first occurrence indices of prefix sums

firstOccurrence.set(0, -1);Initialize prefix sum 0 at index -1 for subarrays starting at 0

prefixSum += (nums[i] === 0) ? -1 : 1;Transform 0 to -1 and update prefix sum

if (firstOccurrence.has(prefixSum))Check if prefix sum seen before to update maxLength

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through array with O(1) hash map operations per element, total O(n). Hash map stores prefix sums, worst case O(n) space.

💡 For n=10^5, this means about 100,000 operations, which is efficient and practical.

Interview Verdict: Accepted and optimal for this problem

This approach is the standard optimal solution and expected in interviews after explaining brute force.

🧠

Prefix Sum with Array Instead of Hash Map (Space Optimization for Limited Range)

💡 If input constraints are small or prefix sums are bounded, we can replace the hash map with an array to reduce overhead and improve speed, demonstrating space optimization.

Intuition

Since prefix sums range from -n to +n, use an array of size 2n+1 to store first occurrences instead of a hash map.

Algorithm

1. Initialize an array of size 2*n+1 with -2 to indicate unseen prefix sums.
2. Set the middle index (offset) to -1 for prefix sum 0.
3. Iterate through nums, updating prefix sum and checking array for first occurrence.
4. Update max_length when prefix sum repeats.

💡 This approach trades off memory for speed by using direct indexing instead of hashing.

</>

Code

def findMaxLength(nums):
    n = len(nums)
    first_occurrence = [-2] * (2 * n + 1)
    offset = n
    first_occurrence[offset] = -1
    prefix_sum = 0
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += -1 if num == 0 else 1
        if first_occurrence[prefix_sum + offset] >= -1:
            max_length = max(max_length, i - first_occurrence[prefix_sum + offset])
        else:
            first_occurrence[prefix_sum + offset] = i
    return max_length

# Driver code
if __name__ == '__main__':
    print(findMaxLength([0,1,0,1,1,1,0]))  # Expected output: 4

Line Notes

first_occurrence = [-2] * (2 * n + 1)Initialize array with -2 to mark unseen prefix sums

offset = nOffset to shift prefix sums to non-negative indices

first_occurrence[offset] = -1Prefix sum 0 first occurs at index -1

if first_occurrence[prefix_sum + offset] >= -1Check if prefix sum seen before to update max_length

public class Solution {
    public static int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] firstOccurrence = new int[2 * n + 1];
        Arrays.fill(firstOccurrence, -2);
        int offset = n;
        firstOccurrence[offset] = -1;
        int prefixSum = 0, maxLength = 0;
        for (int i = 0; i < n; i++) {
            prefixSum += (nums[i] == 0) ? -1 : 1;
            if (firstOccurrence[prefixSum + offset] >= -1) {
                maxLength = Math.max(maxLength, i - firstOccurrence[prefixSum + offset]);
            } else {
                firstOccurrence[prefixSum + offset] = i;
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,1,1,1,0};
        System.out.println(findMaxLength(nums)); // Expected output: 4
    }
}

Line Notes

int[] firstOccurrence = new int[2 * n + 1];Array to store first occurrence indices of prefix sums

Arrays.fill(firstOccurrence, -2);Initialize with -2 to mark unseen prefix sums

firstOccurrence[offset] = -1;Prefix sum 0 first occurs at index -1

if (firstOccurrence[prefixSum + offset] >= -1)Check if prefix sum seen before to update maxLength

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMaxLength(vector<int>& nums) {
    int n = nums.size();
    vector<int> firstOccurrence(2 * n + 1, -2);
    int offset = n;
    firstOccurrence[offset] = -1;
    int prefixSum = 0, maxLength = 0;
    for (int i = 0; i < n; i++) {
        prefixSum += (nums[i] == 0) ? -1 : 1;
        if (firstOccurrence[prefixSum + offset] >= -1) {
            maxLength = max(maxLength, i - firstOccurrence[prefixSum + offset]);
        } else {
            firstOccurrence[prefixSum + offset] = i;
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {0,1,0,1,1,1,0};
    cout << findMaxLength(nums) << endl; // Expected output: 4
    return 0;
}

Line Notes

vector<int> firstOccurrence(2 * n + 1, -2);Array initialized with -2 to mark unseen prefix sums

firstOccurrence[offset] = -1;Prefix sum 0 first occurs at index -1

prefixSum += (nums[i] == 0) ? -1 : 1;Transform 0 to -1 and update prefix sum

if (firstOccurrence[prefixSum + offset] >= -1)Check if prefix sum seen before to update maxLength

function findMaxLength(nums) {
    const n = nums.length;
    const firstOccurrence = new Array(2 * n + 1).fill(-2);
    const offset = n;
    firstOccurrence[offset] = -1;
    let prefixSum = 0, maxLength = 0;
    for (let i = 0; i < n; i++) {
        prefixSum += (nums[i] === 0) ? -1 : 1;
        if (firstOccurrence[prefixSum + offset] >= -1) {
            maxLength = Math.max(maxLength, i - firstOccurrence[prefixSum + offset]);
        } else {
            firstOccurrence[prefixSum + offset] = i;
        }
    }
    return maxLength;
}

// Test
console.log(findMaxLength([0,1,0,1,1,1,0])); // Expected output: 4

Line Notes

const firstOccurrence = new Array(2 * n + 1).fill(-2);Array to store first occurrence indices, initialized to -2

firstOccurrence[offset] = -1;Prefix sum 0 first occurs at index -1

prefixSum += (nums[i] === 0) ? -1 : 1;Transform 0 to -1 and update prefix sum

if (firstOccurrence[prefixSum + offset] >= -1)Check if prefix sum seen before to update maxLength

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass with O(1) array access per element, total O(n). Space is O(n) due to array size 2n+1.

💡 This approach is faster than hash map in practice due to direct indexing, but uses more memory.

Interview Verdict: Accepted; useful when prefix sums are bounded

This is a space-optimized variant of the hash map approach, good to mention if asked about optimization.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always start by explaining brute force briefly, then implement the prefix sum + hash map approach for optimal performance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code
2. Prefix Sum + Hash Map	O(n)	O(n)	No	Yes	Code this approach
3. Prefix Sum + Array (Space Optimized)	O(n)	O(n)	No	Yes	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimal prefix sum + hash map approach.

How to Present

Clarify input and output, ask about constraints.Describe brute force approach to check all subarrays and count zeros and ones.Explain inefficiency of brute force and motivate prefix sum transformation.Present prefix sum + hash map approach with example.Discuss time and space complexity and possible optimizations.

Time Allocation

Clarify: 2min → Brute Force: 3min → Optimal Approach: 8min → Code & Test: 7min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to recognize running state tracking, use prefix sums, hash maps, and optimize from brute force to linear time.

Common Follow-ups

• What if array contains numbers other than 0 and 1? → Use a different approach or transform accordingly.
• Can you find the actual subarray, not just length? → Track start and end indices when updating max_length.

💡 These follow-ups test your flexibility and ability to extend the solution beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem involves subarrays or substrings; 2) Need to find equal counts or balanced elements; 3) Input is binary or can be transformed; 4) Looking for longest or maximum length subarray.

Signature Phrases

'equal number of 0s and 1s''longest contiguous subarray''binary array'

NOT This Pattern When

Problems asking for maximum sum subarray or distinct elements without balance are different patterns.

Similar Problems

Contiguous Array - identical problem on LeetCodeLongest Subarray with Equal Number of 0s and 1s - same pattern with slight variationsSubarray Sum Equals K - similar prefix sum and hash map technique

Practice

1. Consider the following code snippet for finding the longest contiguous subarray with equal 0s and 1s. What is the value of max_length returned for input [0, 1, 0]?

easy

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace prefix_sum and seen dictionary for each index

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}; Index 1: num=1 -> prefix_sum=0, max_length=1-(-1)=2; Index 2: num=0 -> prefix_sum=-1, max_length=max(2,2-0)=2.

2. Step 2: Return max_length after full iteration

   max_length is 2, corresponding to subarray [0,1] or [1,0].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums correctly track balance; max_length updated only when prefix_sum repeats [OK]

Hint: Track prefix sums and earliest indices carefully [OK]

Common Mistakes:

• Off-by-one in max_length calculation
• Not initializing seen with 0:-1
• Updating max_length incorrectly

2. Consider the following Python function that returns the maximum number of pairs summing to k. What is the returned value when calling maxOperations([1, 2, 3, 4], 5)?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace iterations for input [1, 2, 3, 4], k=5

   Iteration 1: num=1, complement=4, freq empty -> freq[1]=1
   Iteration 2: num=2, complement=3, freq={1:1} -> freq[2]=1
   Iteration 3: num=3, complement=2, freq[2]=1 > 0 -> count=1, freq[2]=0
   Iteration 4: num=4, complement=1, freq[1]=1 > 0 -> count=2, freq[1]=0

2. Step 2: Final count returned

   Count is 2 after processing all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pairs (1,4) and (2,3) sum to 5 [OK]

Hint: Pairs (1,4) and (2,3) found -> count 2 [OK]

Common Mistakes:

• Counting pairs multiple times
• Off-by-one in frequency decrement
• Confusing complement logic

3. Identify the bug in the following code snippet for the Minimum Operations to Reduce X to Zero problem:

medium

A. Line with 'if target == 0: return -1' should return len(nums) instead.

B. The while loop condition should be 'current_sum >= target' instead of '>'.

C. The initialization of max_len should be 0 instead of -1.

D. The final return should be 'max_len' instead of 'len(nums) - max_len'.

Solution

1. Step 1: Understand the edge case when target == 0

   If target == 0, it means totalSum == x, so removing all elements is needed, so minimum operations = length of array.

2. Step 2: Identify incorrect return value

   The code returns -1 incorrectly, which signals no solution, but the correct answer is to remove all elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning -1 here causes wrong output on full removal case [OK]

Hint: Check edge cases where x equals total sum [OK]

Common Mistakes:

• Returning -1 instead of full length when target == 0
• Misinterpreting no solution vs full removal
• Ignoring edge cases in initial checks

4. The following code attempts to count the number of subarrays with bounded maximum using the optimal approach, but it contains a subtle bug:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            # Bug: missing reset of length here
            pass
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

What is the bug in this code?

medium

A. The variable 'count' is not reset inside the loop, causing overcounting.

B. The function countAtMost should use max instead of length to track subarray size.

C. The 'length' variable is not reset to zero when encountering a number greater than bound.

D. The subtraction in numSubarrayBoundedMax should be reversed to avoid negative results.

Solution

1. Step 1: Understand the role of 'length'

   'length' tracks the length of the current valid subarray segment where elements ≤ bound.

2. Step 2: Identify the bug

   When an element > bound is encountered, 'length' must reset to 0 to avoid counting invalid subarrays. The code misses this reset, causing overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting 'length' on invalid elements is essential [OK]

Hint: Reset 'length' to zero on elements > bound [OK]

Common Mistakes:

• Forgetting to reset length
• Incorrect subtraction order
• Misusing count variable

5. Suppose the problem is modified so that the array can contain negative numbers, and you still need to find a continuous subarray of length at least 2 whose sum is a multiple of k. Which modification to the optimal approach is necessary to handle negative numbers correctly?

hard

A. Use a hash map to store all prefix sums instead of remainders modulo k

B. Adjust the modulo operation to handle negative remainders by adding k before modulo

C. No modification needed; the existing prefix sum remainder approach works unchanged

D. Switch to brute force since negative numbers break the remainder pattern

Solution

1. Step 1: Understand modulo behavior with negative numbers

   In many languages, modulo of negative numbers can be negative, causing incorrect remainder keys.

2. Step 2: Adjust modulo to always produce non-negative remainders

   By adding k before modulo (e.g., (running_sum % k + k) % k), remainders remain consistent and hash map keys valid.

3. Step 3: Confirm no other approach is needed

   Prefix sums and remainder hashing still work; only modulo adjustment is required.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Handling negative modulo correctly preserves remainder map logic [OK]

Hint: Normalize modulo to non-negative for negative numbers [OK]

Common Mistakes:

• Assuming no change needed
• Switching to brute force unnecessarily
• Storing full prefix sums instead of remainders