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. Consider the following Python function to detect duplicates. What is the value of the variable seen after processing the third element in the input [2, 4, 2, 5]?

easy

A. {4, 2}

B. {2, 4, 2}

C. {2, 4, 5}

D. {2, 4}

Solution

1. Step 1: Trace the loop iterations

   After first element (2), seen = {2}. After second element (4), seen = {2, 4}. After third element (2), since 2 is already in seen, the function returns True before adding anything new.

2. Step 2: Determine seen after third element

   Because the function returns immediately upon detecting duplicate, seen remains {2, 4} at that point.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Duplicate detected at third element, no new additions after second iteration [OK]

Hint: Function returns immediately on duplicate, so seen stops growing [OK]

Common Mistakes:

• Assuming duplicate is added again to set
• Confusing order of insertion
• Misreading when return occurs

2. You are given an unsorted array of integers and need to find the length of the longest sequence of consecutive integers that appear in the array. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a hash set to store all numbers, then for each number that is the start of a sequence, count consecutive numbers forward.

B. Use dynamic programming to build the longest consecutive subsequence ending at each element.

C. Sort the array and then scan linearly to find the longest consecutive sequence.

D. Use a nested loop to check for consecutive sequences starting from each element.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest consecutive sequence in an unsorted array efficiently.

2. Step 2: Evaluate approaches

   Sorting then scanning is O(n log n), nested loops are O(n²), and DP is not straightforward here. Using a hash set to detect sequence starts and count forward achieves O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set membership checks are O(1), enabling linear time [OK]

Hint: Hash set start detection enables O(n) solution [OK]

Common Mistakes:

• Assuming sorting is optimal enough
• Trying DP which doesn't fit this problem
• Using nested loops leading to O(n²)

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

4. What is the time complexity of the optimal frequency counting approach for checking if two strings of length n are anagrams, assuming the strings contain only lowercase English letters?

medium

A. O(n log n) due to sorting the strings

B. O(n) because each string is traversed once and frequency updates are O(1)

C. O(n * 26) because for each character you update a frequency array of size 26

D. O(1) since the frequency array size is fixed and independent of input length

Solution

1. Step 1: Identify loops over input strings

   Both strings are traversed once, each iteration doing O(1) work updating counts.

2. Step 2: Analyze frequency array operations

   Frequency array is fixed size 26, so updates are constant time, not multiplied by n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Overall time is linear in string length n [OK]

Hint: Frequency updates are O(1), total O(n) time [OK]

Common Mistakes:

• Confusing sorting complexity with counting
• Multiplying by 26 unnecessarily
• Assuming constant time overall

5. Suppose the problem changes so that you want the longest subarray with sum divisible by k, but the array elements can be negative and you want to handle very large inputs efficiently. Which modification to the optimal prefix sum + hash map approach is necessary to maintain O(n) time and O(k) space complexity?

hard

A. Use a balanced tree instead of a hash map to store earliest remainder indices for ordered queries.

B. Store prefix sums without modulo and check divisibility by k for all subarrays.

C. Use an array of size k to store earliest indices and adjust negative remainders by adding k.

D. Switch to a brute force nested loop approach since negative numbers break prefix sums.

Solution

1. Step 1: Handle negative numbers correctly

   Negative prefix sums can produce negative remainders; adding k ensures remainder is in [0, k-1].

2. Step 2: Use array for earliest indices

   Since remainder range is fixed [0, k-1], an array of size k is more efficient than a hash map, maintaining O(k) space.

3. Step 3: Maintain O(n) time

   Each element is processed once, and array lookups are O(1), so time remains O(n).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Array + remainder adjustment handles negatives efficiently [OK]

Hint: Adjust negative remainders and use fixed-size array [OK]

Common Mistakes:

• Using brute force for large inputs
• Ignoring negative remainder adjustment
• Using data structures with higher overhead