Subarray Sum Equals K

📋

Problem

Imagine tracking daily expenses and wanting to find how many continuous periods sum up to a specific budget target.

Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4-10^7 ≤ k ≤ 10^7

Edge cases: Empty array → 0All elements zero and k = 0 → count all subarraysNegative numbers included → must handle correctly

</>

IDE

def subarraySum(nums: list[int], k: int) -> int:public int subarraySum(int[] nums, int k)int subarraySum(vector<int>& nums, int k)function subarraySum(nums, k)

def subarraySum(nums, k):
    # Write your solution here
    pass

class Solution {
    public int subarraySum(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function subarraySum(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not counting any subarrays due to missing prefix sum initialization or incorrect map usage.✅ Initialize prefix sum map with {0:1} before iteration to count subarrays starting at index 0.

Wrong: 1Counting only one subarray when multiple exist, often due to greedy or early return logic.✅ Accumulate count for all prefix sums equal to current_sum - k instead of stopping early.

Wrong: 3Under-counting subarrays when all elements are zero and k=0, missing overlapping subarrays.✅ Use prefix sum counts to accumulate all zero-sum subarrays, not just distinct ones.

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Implement prefix sum + hash map approach with O(n) time complexity.

✓

Test Cases

Focus on base cases like empty input and single elements to solidify your solution.

Consider tricky cases with negatives and overlapping subarrays to avoid common pitfalls.

Optimize your solution to O(n) time using prefix sums and hash maps to handle large inputs.

t1_01basic

Input{"nums":[1,1,1],"k":2}

Expected2

⏱ Performance - must finish in 2000ms

The subarrays [1,1] starting at indices 0 and 1 both sum to 2.

💡 Consider prefix sums and how to find subarrays summing to k efficiently.

💡 Use a hash map to store counts of prefix sums encountered so far.

💡 Increment count by the number of prefix sums equal to current_sum - k.

Why it failed: Returned wrong count; likely missed counting all subarrays or incorrect prefix sum logic. Fix by tracking prefix sums and their frequencies correctly.

✓ Correctly counts all subarrays summing to k using prefix sums and hash map.

t1_02basic

Input{"nums":[1,2,3],"k":3}

Expected2

⏱ Performance - must finish in 2000ms

Subarrays [3] and [1,2] both sum to 3.

💡 Check all continuous subarrays and their sums.

💡 Prefix sums can help find complements quickly.

💡 Count occurrences of prefix_sum - k in the map to find valid subarrays.

Why it failed: Incorrect count; possibly missed subarrays starting at index 0 or failed to update prefix sum map properly. Fix by updating map after checking count.

✓ Correctly identifies all subarrays summing to k.

t2_01edge

Input{"nums":[],"k":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so count is 0.

💡 Consider what happens when input array is empty.

💡 No subarrays exist, so result must be zero.

💡 Return 0 immediately if array length is zero.

Why it failed: Returned non-zero count for empty array; fix by handling empty input case explicitly.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[5],"k":5}

Expected1

⏱ Performance - must finish in 2000ms

Single element equals k, so one subarray counts.

💡 Check single element arrays carefully.

💡 If nums[0] == k, count should be 1.

💡 Initialize prefix sum map with 0 count to handle single element correctly.

Why it failed: Missed counting single element subarray equal to k; fix by initializing prefix sum map with {0:1}.

✓ Correctly counts single element subarray equal to k.

t2_03edge

Input{"nums":[0,0,0],"k":0}

Expected6

⏱ Performance - must finish in 2000ms

All subarrays sum to 0; total subarrays = n*(n+1)/2 = 6.

💡 When k=0 and all elements zero, count all subarrays.

💡 Number of subarrays in array of length n is n*(n+1)/2.

💡 Prefix sums and map count cumulative zeros to find all subarrays.

Why it failed: Under-counted subarrays when all zeros and k=0; fix by correctly counting overlapping zero sums using prefix sums.

✓ Correctly counts all subarrays summing to zero.

t3_01corner

Input{"nums":[1,-1,0],"k":0}

Expected3

⏱ Performance - must finish in 2000ms

Subarrays summing to 0 are [1,-1], [-1,0], [0], and [1,-1,0].

💡 Negative numbers can affect prefix sums.

💡 Check prefix sums carefully to handle negative values.

💡 Use hash map to track prefix sums and their counts correctly.

Why it failed: Failed to handle negative numbers correctly; likely incorrect prefix sum or map update. Fix by including negative values in prefix sums and updating map properly.

✓ Correctly handles negative numbers in prefix sums.

t3_02corner

Input{"nums":[1,2,1,2,1],"k":3}

Expected4

⏱ Performance - must finish in 2000ms

Subarrays summing to 3 are [1,2], [2,1], [1,2], [2,1], [1,2,1,-1], and [2,1,2,-2] (actually only the first four valid subarrays, total 6 counting all overlapping).

💡 Beware of greedy approaches that pick first subarray only.

💡 Count all valid subarrays, including overlapping ones.

💡 Use prefix sums and map to count all occurrences.

Why it failed: Greedy approach missed overlapping subarrays; fix by counting all prefix sum complements, not just first occurrence.

✓ Correctly counts all overlapping subarrays.

t3_03corner

Input{"nums":[1,1,1,1],"k":2}

Expected3

⏱ Performance - must finish in 2000ms

Subarrays summing to 2 are [1,1] starting at indices 0,1,2.

💡 Avoid off-by-one errors in prefix sum indexing.

💡 Ensure prefix sums and map updates are done in correct order.

💡 Increment count before updating map for current prefix sum.

Why it failed: Off-by-one error caused missed subarrays; fix by updating count before adding current prefix sum to map.

✓ Correctly counts all subarrays with proper prefix sum indexing.

t4_01performance

Input{"nums":[10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000,10000,-10000],"k":0}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, alternating large positive and negative values, sum to zero subarrays counted in O(n) time.

💡 Brute force O(n^2) will time out for n=100.

💡 Use prefix sums with hash map for O(n) solution.

💡 Track prefix sums and their counts to avoid nested loops.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing O(n) prefix sum + hash map solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. You are given a sorted list of unique integers and need to summarize consecutive sequences as ranges (e.g., [0,1,2,4,5,7] -> ['0->2','4->5','7']). Which approach guarantees an optimal O(n) time solution with minimal extra space?

easy

A. Using two pointers to scan the list once, expanding the end pointer while consecutive numbers continue, then recording ranges.

B. Using nested loops to check every possible range start and end, appending ranges when sequences break.

C. Using dynamic programming to store the longest consecutive subsequence ending at each index and reconstruct ranges.

D. Using a greedy approach that picks the next number if it is consecutive, otherwise starts a new range, but restarts scanning from the beginning each time.

Solution

1. Step 1: Understand the problem constraints

   The input is sorted and unique, so consecutive sequences can be detected by checking if nums[end + 1] == nums[end] + 1.

2. Step 2: Identify the optimal approach

   Two pointers allow a single pass: one pointer marks the start of a range, the other expands until the sequence breaks, then record the range and move start pointer forward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers scan once -> O(n) time and O(n) space for output [OK]

Hint: Two pointers scan sorted list once for consecutive ranges [OK]

Common Mistakes:

• Thinking nested loops are necessary
• Confusing DP with this linear scan
• Restarting scan repeatedly wastes time

2. What is the time complexity of the optimal sliding window solution for finding the longest substring with at most two distinct characters, assuming the input string length is n?

medium

A. O(n²), because the inner while loop can run up to n times for each character.

B. O(n * k), where k is the number of distinct characters allowed (here k=2).

C. O(n log n), due to maintaining a balanced data structure for frequencies.

D. O(n), because each character is visited at most twice by the left and right pointers.

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once. The left pointer only moves forward when distinct_count > 2, also at most n times.

2. Step 2: Confirm total operations

   Each character is processed at most twice (once when right pointer visits, once when left pointer moves), so total operations are O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with two pointers is classic O(n) approach [OK]

Hint: Two pointers each move at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n²)
• Confusing frequency map maintenance cost
• Thinking k affects complexity linearly

3. Consider the following buggy code for finding the longest substring with at most two distinct characters. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line inside while loop missing check to decrement distinct_count when freq hits zero

B. Line where freq[ord(s[right])] is incremented

C. Line inside while loop where freq[ord(s[left])] is decremented

D. Line where distinct_count is incremented when freq is zero

Solution

1. Step 1: Identify the bug

   The code decrements freq for s[left] inside the while loop but does not check if freq reaches zero to decrement distinct_count.

2. Step 2: Consequences of missing check

   Without decrementing distinct_count, the while loop condition distinct_count > 2 never becomes false, causing infinite loop or incorrect window size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing distinct_count decrement inside while loop is a classic subtle bug [OK]

Hint: Check distinct_count update when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement distinct_count
• Incorrect window size calculation
• Not breaking early in brute force

4. Suppose the problem changes: now you want to count the number of subarrays with exactly k odd numbers, but the array can contain negative integers and zeros. Which modification to the sliding window approach is necessary to handle this correctly?

hard

A. Add extra conditions to handle zeros separately in the sliding window.

B. No change needed; the existing sliding window code works for any integers.

C. Use a prefix sum hashmap approach instead, since sliding window fails with negative numbers.

D. Modify the odd number check to use absolute value: check if abs(nums[i]) % 2 == 1.

Solution

1. Step 1: Identify how odd numbers are detected

   The code checks if nums[i] % 2 == 1, which fails for negative odd numbers (e.g., -1 % 2 == -1 in Python).

2. Step 2: Fix odd number detection

   Using abs(nums[i]) % 2 == 1 correctly identifies odd numbers regardless of sign.

3. Step 3: Confirm sliding window logic remains valid

   Once odd detection is fixed, the sliding window approach works as before.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   abs() fixes odd detection for negatives [OK]

Hint: Use abs() to detect odd numbers with negatives [OK]

Common Mistakes:

• Assuming % 2 == 1 works for negatives
• Switching to prefix sums unnecessarily
• Overcomplicating zero handling

5. Suppose the problem changes: now you want the longest substring with at most two distinct characters, but characters can be reused infinitely many times and the input string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Maintain a sliding window with frequency counts but optimize by using a fixed-size array for frequencies instead of a hash map.

B. Use a brute force nested loop approach with early breaks to handle reuse.

C. Use a priority queue to track the least recently used character to evict when distinct count exceeds two.

D. Switch to a dynamic programming approach that stores results for substrings with reuse allowed.

Solution

1. Step 1: Understand reuse and input size impact

   Characters can be reused infinitely, but the problem remains longest substring with at most two distinct chars. The input is very long, so efficiency is critical.

2. Step 2: Identify efficient data structure

   Using a fixed-size array for frequencies (size 128 for ASCII) is more efficient than a hash map, reducing overhead and ensuring O(n) time and O(1) space.

3. Step 3: Confirm approach correctness

   The sliding window logic remains the same, but frequency tracking is optimized for speed and memory, suitable for very long inputs with reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Fixed-size array frequency tracking is optimal for large inputs with limited charset [OK]

Hint: Fixed-size array beats hash map for fixed charset [OK]

Common Mistakes:

• Using brute force despite input size
• Using complex data structures unnecessarily
• Switching to DP without need