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. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Using prefix sums combined with a hash map to track remainders modulo k

B. Brute force nested loops checking all subarrays and their sums

C. Dynamic programming to store sums of all subarrays and check divisibility

D. Greedy approach by iteratively subtracting elements until sum is divisible by k

Solution

1. Step 1: Understand the problem constraints and requirements

   The problem requires checking continuous subarrays with sums divisible by k, which suggests prefix sums and modular arithmetic.

2. Step 2: Identify the optimal approach

   Using prefix sums modulo k and a hash map to track first occurrences of remainders allows O(n) time complexity, unlike brute force or greedy which are inefficient or incorrect.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Prefix sums with remainder hashing is the classic optimal solution [OK]

Hint: Prefix sums + remainder hash map -> O(n) solution [OK]

Common Mistakes:

• Thinking greedy can solve divisibility in subarrays
• Assuming DP is needed for sums divisible by k
• Using brute force for optimality

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

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

3. Given the following Python code for summaryRanges, what is the final returned list when input is [1,2,3,5]?

from typing import List

def summaryRanges(nums: List[int]) -> List[str]:
    ranges = []
    n = len(nums)
    start = 0
    while start < n:
        end = start
        while end + 1 < n and nums[end + 1] == nums[end] + 1:
            end += 1
        if start == end:
            ranges.append(str(nums[start]))
        else:
            ranges.append(f"{nums[start]}->{nums[end]}")
        start = end + 1
    return ranges

easy

A. ['1', '2', '3', '5']

B. ['1->3', '5']

C. ['1->2', '3->5']

D. ['1->3', '5->5']

Solution

1. Step 1: Trace first range detection

   start=0 (nums[0]=1), end moves from 0 to 2 because nums[1]=2 and nums[2]=3 are consecutive.

2. Step 2: Append first range and move start

   Append '1->3', then start=3 (nums[3]=5), end=3, no consecutive next element, append '5'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Ranges correctly summarize consecutive sequences [OK]

Hint: Two pointers expand end while consecutive -> correct ranges [OK]

Common Mistakes:

• Appending single elements as ranges like '5->5'
• Splitting consecutive sequences incorrectly
• Off-by-one errors in inner loop

4. Identify the bug in the following code snippet for longest arithmetic subsequence length:

medium

A. Line assigning dp[i][diff] without adding 1 to prev_len

B. Line initializing max_len to 0 instead of 1

C. Line creating dp as list of dicts instead of list of lists

D. Line returning max_len if max_len > 0 else n

Solution

1. Step 1: Examine dp update line

   dp[i][diff] should be prev_len + 1 to extend the subsequence; missing +1 means subsequence length never grows.

2. Step 2: Check other lines

   max_len initialization and return line are correct; dp as list of dicts is intentional for difference tracking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing +1 causes incorrect subsequence length calculation [OK]

Hint: dp[i][diff] must increment prev_len by 1 to extend subsequence [OK]

Common Mistakes:

• Forgetting to add 1 when updating dp[i][diff]
• Initializing max_len incorrectly
• Confusing subsequence with subarray

5. What is the time complexity of the optimized sliding window approach with character filtering for the minimum window substring problem, given n = len(s) and m = len(t)?

medium

A. O(n) because each character in s is visited at most twice after filtering

B. O(n * m) due to nested loops over s and t

C. O(n + m) due to filtering and frequency map operations

D. O(n^2) because shrinking and expanding windows can overlap quadratically

Solution

1. Step 1: Analyze filtering and iteration

   Filtering s to only characters in t takes O(n). The main loop iterates over filtered_s, which is at most n. Each character is visited at most twice by left and right pointers.

2. Step 2: Confirm sliding window complexity

   Sliding window moves right pointer forward and left pointer forward independently, each at most n times. Frequency map updates and checks are O(1) per operation. The total complexity is O(n + m) because counting frequencies of t takes O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with filtering runs in linear time relative to s length plus frequency map setup [OK]

Hint: Sliding window pointers each move linearly [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing filtering cost with main loop cost