Continuous Subarray Sum

▶

Steps

setup

Normalize k if negative

Check if k is negative and convert it to positive to simplify remainder calculations.

💡 Ensures remainder calculations are consistent and non-negative.

Line:

if k < 0:
    k = -k

💡 k must be positive for modulo operations to behave predictably.

setup

Initialize remainder_map with 0 mapped to -1

Create a hash map to store remainders of prefix sums, starting with remainder 0 at index -1.

💡 This initialization allows detection of subarrays starting at index 0.

Line:

remainder_map = {0: -1}

💡 Mapping 0 to -1 helps identify subarrays from the start that sum to multiples of k.

fill_cells

Start iterating: i=0, num=23, update total

Add nums[0] = 23 to total prefix sum, total becomes 23.

💡 Accumulate prefix sums to track sums of subarrays ending at current index.

Line:

total += num

💡 Prefix sum at index 0 is 23, representing sum of subarray [23].

fill_cells

Compute remainder for total=23 modulo k=6

Calculate remainder = (23 % 6 + 6) % 6 = 5 to ensure non-negative remainder.

💡 Modulo operation normalizes prefix sums to remainder classes modulo k.

Line:

if k != 0:
    total = (total % k + k) % k

💡 Remainder 5 means prefix sum 23 leaves remainder 5 when divided by 6.

compare

Check if remainder 5 is in remainder_map

Look up remainder 5 in the map; it is not found (miss).

💡 If remainder seen before, subarray sum multiple of k may exist; else store it.

Line:

if total in remainder_map:

💡 New remainder means no subarray ending here sums to multiple of k yet.

insert

Insert remainder 5 with index 0

Add remainder 5 to map with value 0, marking first occurrence at index 0.

💡 Storing first occurrence helps detect future subarrays with same remainder.

Line:

else:
    remainder_map[total] = i

💡 Map now tracks remainder 5 at index 0.

fill_cells

Iterate: i=1, num=2, update total

Add nums[1] = 2 to total (currently 5), total becomes 7.

💡 Accumulate prefix sums to track sums of subarrays ending at current index.

Line:

total += num

💡 Prefix sum at index 1 is 7, representing sum of subarray [23,2].

fill_cells

Compute remainder for total=7 modulo k=6

Calculate remainder = (7 % 6 + 6) % 6 = 1 to ensure non-negative remainder.

💡 Modulo operation normalizes prefix sums to remainder classes modulo k.

Line:

if k != 0:
    total = (total % k + k) % k

💡 Remainder 1 means prefix sum 7 leaves remainder 1 when divided by 6.

compare

Check if remainder 1 is in remainder_map

Look up remainder 1 in the map; it is not found (miss).

💡 If remainder seen before, subarray sum multiple of k may exist; else store it.

Line:

if total in remainder_map:

💡 New remainder means no subarray ending here sums to multiple of k yet.

insert

Insert remainder 1 with index 1

Add remainder 1 to map with value 1, marking first occurrence at index 1.

💡 Storing first occurrence helps detect future subarrays with same remainder.

Line:

else:
    remainder_map[total] = i

💡 Map now tracks remainder 1 at index 1.

fill_cells

Iterate: i=2, num=4, update total

Add nums[2] = 4 to total (currently 1), total becomes 5.

💡 Accumulate prefix sums to track sums of subarrays ending at current index.

Line:

total += num

💡 Prefix sum at index 2 is 5 modulo k, representing sum of subarray [23,2,4].

fill_cells

Compute remainder for total=5 modulo k=6

Calculate remainder = (5 % 6 + 6) % 6 = 5 to ensure non-negative remainder.

💡 Modulo operation normalizes prefix sums to remainder classes modulo k.

Line:

if k != 0:
    total = (total % k + k) % k

💡 Remainder 5 means prefix sum 5 leaves remainder 5 when divided by 6.

compare

Check if remainder 5 is in remainder_map

Look up remainder 5 in the map; it is found at index 0 (hit).

💡 A repeated remainder indicates a subarray summing to multiple of k may exist.

Line:

if total in remainder_map:

💡 Subarray from index 1 to 2 sums to multiple of k because remainders match.

compare

Check subarray length for remainder 5 hit

Calculate subarray length = 2 - 0 = 2, which is greater than 1, so return true.

💡 Subarray length must be at least 2 to satisfy problem constraints.

Line:

if i - remainder_map[total] > 1:
    return True

💡 Found a continuous subarray [2,4] summing to multiple of k=6.

def checkSubarraySum(nums, k):
    # STEP 1
    if k < 0:
        k = -k
    # STEP 2
    remainder_map = {0: -1}
    total = 0
    for i, num in enumerate(nums):
        # STEP 3
        total += num
        # STEP 4
        if k != 0:
            total = (total % k + k) % k
        # STEP 5
        if total in remainder_map:
            # STEP 6
            if i - remainder_map[total] > 1:
                # STEP 14
                return True
        else:
            # STEP 7
            remainder_map[total] = i
    return False

if __name__ == '__main__':
    print(checkSubarraySum([23, 2, 4, 6, 7], 6))  # True

📊

Continuous Subarray Sum - Watch the Algorithm Execute, Step by Step

Watching each step reveals how prefix sums and modular arithmetic combine with hash maps to efficiently detect qualifying subarrays without checking all subarrays explicitly.

check

empty map

insert

0→-1

increment

0→-1

update

Lookup: 5

0→-1

lookup

Lookup: 5

0→-1

insert

0→-1

5→0

increment

0→-1

5→0

update

Lookup: 1

0→-1

5→0

lookup

Lookup: 1

0→-1

5→0

insert

0→-1

5→0

1→1

increment

0→-1

5→0

1→1

update

Lookup: 5→ 0

0→-1

5→0lookup

1→1

lookup

Lookup: 5→ 0

0→-1

5→0lookup

1→1

check

Lookup: 5→ 0

0→-1

5→0lookup

1→1

Result: true

Key Takeaways

✓ Repeated remainders in prefix sums indicate subarrays summing to multiples of k.

This insight is hard to see from code alone because it relies on understanding modular arithmetic and prefix sums together.

✓ Storing the earliest index of each remainder allows quick subarray length checks.

Visualizing the map entries clarifies why only the first occurrence is stored and how it helps detect valid subarrays.

✓ The subarray length condition (>1) ensures the subarray has at least two elements.

Seeing the length check in action with indices makes the problem constraint concrete and understandable.

Practice

1. Consider the following Python code for the optimal Insert Delete GetRandom data structure. After executing the code below, what is the content of the list nums and the dictionary pos?

rs = RandomizedSet()
rs.insert(1)
rs.insert(2)
rs.insert(3)
rs.remove(2)

easy

A. nums = [3, 1], pos = {3: 0, 1: 1}

B. nums = [1, 2, 3], pos = {1: 0, 2: 1, 3: 2}

C. nums = [1], pos = {1: 0}

D. nums = [1, 3], pos = {1: 0, 3: 1}

Solution

1. Step 1: Trace insertions

   Insert 1 -> nums=[1], pos={1:0}; Insert 2 -> nums=[1,2], pos={1:0,2:1}; Insert 3 -> nums=[1,2,3], pos={1:0,2:1,3:2}

2. Step 2: Trace removal of 2

   Remove 2 at idx=1; last_element=3; swap nums[1]=3; update pos[3]=1; pop last element; delete pos[2]; final nums=[1,3], pos={1:0,3:1}

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Swap-delete updates indices correctly [OK]

Hint: Swap last element with removed index to keep O(1) [OK]

Common Mistakes:

• Forgetting to update pos after swap
• Not swapping and popping, causing O(n) remove
• Assuming elements remain in insertion order

2. What is the worst-case time complexity of the optimal hash set approach to detect duplicates in an array of length n?

medium

A. O(n) average, but O(n²) worst-case if many hash collisions occur

B. O(n log n) due to sorting inside the hash set

C. O(n²) because each insertion checks all existing elements

D. O(n) guaranteed due to constant-time hash set operations

Solution

1. Step 1: Understand average case

   Hash set operations (insert, lookup) are O(1) average, so iterating n elements is O(n) average.

2. Step 2: Consider worst-case scenario

   If many hash collisions occur, hash set operations degrade to O(n) each, making total O(n²) in worst case.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash collisions cause worst-case quadratic time, though rare in practice [OK]

Hint: Hash collisions can degrade hash set to O(n²) worst-case [OK]

Common Mistakes:

• Assuming guaranteed O(n) time
• Confusing sorting complexity with hashing
• Thinking insertion checks all elements explicitly

3. What is the time complexity of the optimal bidirectional hash map approach to check if two strings of length n are isomorphic?

medium

A. O(n) because each character is processed once with constant-time hash map operations

B. O(n²) due to nested loops checking all character pairs

C. O(n log n) due to sorting characters before mapping

D. O(1) since hash maps provide constant-time lookups

Solution

1. Step 1: Identify the main loop over string length

   The algorithm iterates once over the strings of length n, processing each character pair exactly once.

2. Step 2: Analyze hash map operations

   Hash map insertions and lookups are average O(1), so total time is O(n) * O(1) = O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No nested loops or sorting involved, so O(n) [OK]

Hint: Single pass with hash maps -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n²)
• Assuming sorting is needed
• Ignoring hash map average case

4. What is the time complexity of the optimal hash set approach for finding the longest consecutive sequence in an array of size n?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n) because each number is processed at most twice

C. O(n²) because of nested loops checking consecutive numbers

D. O(n) average but O(n²) worst case due to hash collisions

Solution

1. Step 1: Analyze outer loop

   The outer loop iterates over each unique number once.

2. Step 2: Analyze inner while loop

   Each number is visited at most once in the inner loop when counting consecutive sequences, so total work is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash set lookups are O(1), total linear time [OK]

Hint: Each element visited once in sequence counting [OK]

Common Mistakes:

• Assuming sorting is involved causing O(n log n)
• Confusing nested loops as O(n²)
• Overestimating hash collision impact

5. Suppose the Two Sum problem is modified so that the same element can be used multiple times to reach the target sum. Which of the following approaches correctly solves this variant?

hard

A. Use the original hash map approach without changes; it works as is.

B. Sort the array and use two pointers, moving pointers only when sum is less or greater than target.

C. Use a dynamic programming approach similar to the coin change problem to allow reuse.

D. Use a brute force nested loop checking all pairs including pairs with the same index.

Solution

1. Step 1: Understand the reuse requirement

   Allowing reuse means the same element can be chosen multiple times, which breaks the original hash map approach that assumes distinct indices.

2. Step 2: Identify suitable algorithm

   Dynamic programming similar to coin change counts combinations allowing reuse, correctly handling multiple uses of the same element.

3. Step 3: Evaluate other options

   Original hash map fails reuse; two pointers assume distinct elements; brute force with same index pairs is invalid.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP approach handles reuse correctly, unlike hash map or two pointers [OK]

Hint: Reuse requires DP, not hash map or two pointers [OK]

Common Mistakes:

• Assuming original hash map works with reuse
• Using two pointers without modification
• Allowing same index pairs in brute force