Subarray Sum Equals K

▶

Steps

setup

Initialize count, prefix_sum, and prefix_counts

Initialize count to 0, prefix_sum to 0, and prefix_counts map with 0 mapped to 1 to handle subarrays starting at index 0.

💡 Setting prefix_counts[0] = 1 accounts for subarrays that start from the beginning and sum exactly to k.

Line:

count = 0
prefix_sum = 0
prefix_counts = defaultdict(int)
prefix_counts[0] = 1

💡 The map starts with one occurrence of prefix sum 0, enabling detection of subarrays starting at index 0.

fill_row

Process first number: Add nums[0] to prefix_sum

Add the first number 1 to prefix_sum, updating prefix_sum from 0 to 1.

💡 Updating prefix_sum accumulates the sum of elements from the start to current index.

Line:

prefix_sum += num  # num = 1

💡 prefix_sum now represents the sum of nums[0..0].

compare

Lookup prefix_sum - k in prefix_counts

Calculate prefix_sum - k = 1 - 2 = -1 and look up -1 in prefix_counts to find how many subarrays ending here sum to k.

💡 If prefix_sum - k exists in the map, it means a subarray summing to k ends at current index.

Line:

count += prefix_counts[prefix_sum - k]  # prefix_sum - k = -1

💡 No subarray ending at index 0 sums to k because prefix_sum - k is not in the map.

insert

Increment count of current prefix_sum in prefix_counts

Increment the count of prefix_sum = 1 in prefix_counts from 0 to 1.

💡 Updating prefix_counts tracks how many times each prefix sum has appeared for future lookups.

Line:

prefix_counts[prefix_sum] += 1  # prefix_sum = 1

💡 prefix_counts now records one occurrence of prefix sum 1.

fill_row

Process second number: Add nums[1] to prefix_sum

Add the second number 1 to prefix_sum, updating prefix_sum from 1 to 2.

💡 prefix_sum accumulates sum of nums[0..1].

Line:

prefix_sum += num  # num = 1

💡 prefix_sum now represents sum of first two elements.

compare

Lookup prefix_sum - k in prefix_counts

Calculate prefix_sum - k = 2 - 2 = 0 and look up 0 in prefix_counts to find subarrays ending here that sum to k.

💡 Finding prefix_sum - k in the map means subarrays ending at current index sum to k.

Line:

count += prefix_counts[prefix_sum - k]  # prefix_sum - k = 0

💡 One subarray ending at index 1 sums to k, increasing count from 0 to 1.

insert

Increment count of current prefix_sum in prefix_counts

Increment the count of prefix_sum = 2 in prefix_counts from 0 to 1.

💡 Updating prefix_counts prepares for future subarray checks.

Line:

prefix_counts[prefix_sum] += 1  # prefix_sum = 2

💡 prefix_counts now records one occurrence of prefix sum 2.

fill_row

Process third number: Add nums[2] to prefix_sum

Add the third number 1 to prefix_sum, updating prefix_sum from 2 to 3.

💡 prefix_sum now represents sum of nums[0..2].

Line:

prefix_sum += num  # num = 1

💡 prefix_sum accumulates all elements so far.

compare

Lookup prefix_sum - k in prefix_counts

Calculate prefix_sum - k = 3 - 2 = 1 and look up 1 in prefix_counts to find subarrays ending here that sum to k.

💡 A hit means subarrays ending at current index sum to k.

Line:

count += prefix_counts[prefix_sum - k]  # prefix_sum - k = 1

💡 One more subarray ending at index 2 sums to k, increasing count from 1 to 2.

insert

Increment count of current prefix_sum in prefix_counts

Increment the count of prefix_sum = 3 in prefix_counts from 0 to 1.

💡 Updating prefix_counts completes the iteration for the last element.

Line:

prefix_counts[prefix_sum] += 1  # prefix_sum = 3

💡 prefix_counts now records one occurrence of prefix sum 3.

reconstruct

Return final count

Return the total count of subarrays summing to k, which is 2.

💡 The final count represents how many subarrays sum to k in the entire array.

Line:

return count

💡 The algorithm has efficiently counted all valid subarrays using prefix sums and the hash map.

from collections import defaultdict

def subarraySum(nums, k):
    count = 0  # STEP 1
    prefix_sum = 0  # STEP 1
    prefix_counts = defaultdict(int)  # STEP 1
    prefix_counts[0] = 1  # STEP 1
    for num in nums:
        prefix_sum += num  # STEP 2,5,8
        count += prefix_counts[prefix_sum - k]  # STEP 3,6,9
        prefix_counts[prefix_sum] += 1  # STEP 4,7,10
    return count  # STEP 11

if __name__ == '__main__':
    print(subarraySum([1,1,1], 2))  # Output: 2

📊

Subarray Sum Equals K - Watch the Algorithm Execute, Step by Step

Watching each prefix sum update and hash map lookup reveals how the algorithm efficiently counts subarrays without nested loops.

insert

0→1

Result: 0

check

0→1

Result: 0

lookup

Lookup: -1→ 0

0→1

Result: 0

increment

0→1

1→1

Result: 0

check

0→1

1→1

Result: 0

lookup

Lookup: 0→ 1

0→1lookup

1→1

Result: 1

increment

0→1

1→1

2→1

Result: 1

check

0→1

1→1

2→1

Result: 1

lookup

Lookup: 1→ 1

0→1

1→1lookup

2→1

Result: 2

increment

0→1

1→1

2→1

3→1

Result: 2

check

0→1

1→1

2→1

3→1

Result: 2

Key Takeaways

✓ Prefix sums allow us to convert the problem of finding subarrays summing to k into a problem of finding pairs of prefix sums differing by k.

This insight is hard to see from code alone because it requires understanding the mathematical relationship between prefix sums and subarray sums.

✓ The hash map stores counts of prefix sums seen so far, enabling O(1) lookups to find how many subarrays end at the current index with sum k.

Visualizing the map updates clarifies how the algorithm avoids nested loops and achieves linear time complexity.

✓ Each time we find prefix_sum - k in the map, it means one or more subarrays ending at the current index sum to k, incrementing the count accordingly.

Seeing hits and misses in the map during lookup steps concretely shows how subarrays are counted incrementally.

Practice

1. You are given an integer array and a target integer k. You need to determine if there exists a continuous subarray of at least length 2 whose sum is a multiple of k (including zero). Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that tries to extend subarrays until sum is divisible by k

B. Sorting the array and using two pointers to find subarrays summing to multiples of k

C. Dynamic programming that stores sums of all subarrays explicitly

D. Prefix sum combined with a hash map tracking remainders modulo k

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking sums of continuous subarrays for divisibility by k, which suggests prefix sums and modular arithmetic.

2. Step 2: Identify the approach that efficiently tracks prefix sums modulo k

   Using a hash map to store the earliest index of each remainder allows O(n) detection of subarrays with sums divisible by k.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + remainder hash map is the classic optimal approach [OK]

Hint: Prefix sums + remainder hash map solves this optimally [OK]

Common Mistakes:

• Thinking greedy can find all valid subarrays
• Trying to sort array breaks continuous subarray property
• Using DP to store all subarray sums causes O(n^2) time

2. 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

3. Given the following Python code for a time-based key-value store, what is the output of tm.get("foo", 3) after the shown operations?

easy

A. "bar"

B. ""

C. IndexError

D. "foo"

Solution

1. Step 1: Trace bisect_right on times=[1] with timestamp=3

   bisect_right returns the insertion point to the right of 3, which is index 1.

2. Step 2: Determine returned value

   Since i=1, return values[i-1] = values[0] = "bar".

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   bisect_right returns 1, so value at index 0 is "bar" [OK]

Hint: bisect_right returns insertion index; value at i-1 is correct [OK]

Common Mistakes:

• Returning empty string if timestamp > max stored
• Off-by-one error in index
• Confusing bisect_left with bisect_right

4. Identify the bug in the following code snippet for grouping anagrams:

medium

A. Line 4: defaultdict initialization

B. Line 7: Incrementing count array

C. Line 10: Appending string to map

D. Line 9: Using ''.join(count) to create key

Solution

1. Step 1: Understand key creation

   Count is a list of integers; ''.join(count) tries to join integers as strings, causing TypeError or incorrect keys.

2. Step 2: Correct key creation

   Key should be a tuple of counts to be hashable and unique, e.g., key = tuple(count).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Using ''.join on int list causes errors or wrong grouping [OK]

Hint: Keys must be hashable types like tuples, not joined strings of ints [OK]

Common Mistakes:

• Joining int list without conversion
• Using list as dict key
• Forgetting to convert count to tuple

5. Suppose the input strings can contain uppercase letters and digits in addition to lowercase letters. Which modification to the optimal frequency counting approach correctly handles this scenario?

hard

A. Use a frequency array of size 62 (26 lowercase + 26 uppercase + 10 digits) and map characters accordingly.

B. Use a frequency array of size 26 and convert all characters to lowercase before counting.

C. Sort each string and use the sorted string as the hash map key.

D. Use a hash map with character counts stored as a dictionary instead of an array.

Solution

1. Step 1: Identify character set

   Input includes lowercase, uppercase, and digits, total 62 distinct characters.

2. Step 2: Adjust frequency counting

   Frequency array size must be 62, mapping each character to an index to count correctly.

3. Step 3: Evaluate alternatives

   Converting to lowercase loses information, sorting is slower, dictionary counts add overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency array size matches character set size [OK]

Hint: Frequency array size must cover all possible characters [OK]

Common Mistakes:

• Lowercasing loses info
• Using smaller array size
• Assuming sorting is always best