Subarray Sum Equals K

🎯

Subarray Sum Equals K

mediumHASH_MAPFacebookAmazonGoogle

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

💡 This problem asks how many continuous segments of an array sum to a target value. Beginners often struggle because the naive approach is slow and they don't immediately see how prefix sums and hash maps can optimize the search.

📋

Problem Statement

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

💡

Example

Input"nums = [1,1,1], k = 2"

Output2

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

• Empty array → 0
• All elements zero and k = 0 → count all subarrays
• Negative numbers included → must handle correctly
• Single element equals k → count is 1

⚠️

Common Mistakes

Not initializing prefix_counts with {0:1}

Misses subarrays starting at index 0, resulting in incorrect counts

✅ Initialize prefix_counts with 0 sum count as 1 before iteration

Checking prefix_sum - k in map but not adding its count

Count remains zero or too low, missing valid subarrays

✅ Add prefix_counts[prefix_sum - k] to count whenever found

Using nested loops but summing prefix sums inside inner loop

Leads to O(n^3) time complexity, causing timeouts

✅ Use running sum variable to avoid recomputing sums repeatedly

Using sliding window approach directly with negative numbers

Incorrect results because sliding window only works with non-negative numbers

✅ Use prefix sum + hash map approach for arrays with negatives

Not handling negative numbers in prefix sums

Incorrect counts or runtime errors if assumptions about sums are violated

✅ Use hash map to track all prefix sums regardless of sign

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly checking every possible subarray sum, which helps understand the problem's nature before optimizing.

Intuition

Try every possible subarray by using two nested loops and sum elements to check if they equal k.

Algorithm

1. Initialize count to 0.
2. Use two nested loops: outer loop picks start index, inner loop picks end index.
3. Sum elements from start to end index.
4. If sum equals k, increment count.

💡 The nested loops and summing inside the inner loop make this approach slow and hard to scale.

</>

Code

def subarraySum(nums, k):
    count = 0
    n = len(nums)
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

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

Line Notes

count = 0Initialize count to track number of valid subarrays found so far

for start in range(n)Outer loop selects the start index of the subarray to consider

total = 0Reset running sum for the new start index to accumulate subarray sums

for end in range(start, n)Inner loop extends the subarray to the end index

total += nums[end]Add current element to the running sum of the subarray

if total == kCheck if the current subarray sum matches the target k

count += 1Increment count when a valid subarray is found

return countReturn the total count after checking all subarrays

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int total = 0;
            for (int end = start; end < n; end++) {
                total += nums[end];
                if (total == k) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subarraySum(new int[]{1,1,1}, 2)); // Output: 2
    }
}

Line Notes

int count = 0;Initialize count to track valid subarrays found

for (int start = 0; start < n; start++)Outer loop picks the start index of subarray

int total = 0;Reset sum accumulator for each new start index

for (int end = start; end < n; end++)Inner loop picks the end index of subarray

total += nums[end];Add current element to running sum

if (total == k)Check if current subarray sum equals target k

count++;Increment count when a valid subarray is found

return count;Return total count after all subarrays checked

#include <iostream>
#include <vector>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int total = 0;
        for (int end = start; end < n; end++) {
            total += nums[end];
            if (total == k) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {1,1,1};
    cout << subarraySum(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

int count = 0;Initialize count to track number of valid subarrays

for (int start = 0; start < n; start++)Outer loop selects start index of subarray

int total = 0;Reset running sum for each new start index

for (int end = start; end < n; end++)Inner loop selects end index of subarray

total += nums[end];Add current element to running sum

if (total == k)Check if current subarray sum equals target k

count++;Increment count when a valid subarray is found

return count;Return total count after checking all subarrays

function subarraySum(nums, k) {
    let count = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let total = 0;
        for (let end = start; end < n; end++) {
            total += nums[end];
            if (total === k) {
                count++;
            }
        }
    }
    return count;
}

// Test
console.log(subarraySum([1,1,1], 2)); // Output: 2

Line Notes

let count = 0;Initialize count to track number of valid subarrays

for (let start = 0; start < n; start++)Outer loop selects start index of subarray

let total = 0;Reset running sum for each new start index

for (let end = start; end < n; end++)Inner loop selects end index of subarray

total += nums[end];Add current element to running sum

if (total === k)Check if current subarray sum equals target k

count++;Increment count when a valid subarray is found

return count;Return total count after checking all subarrays

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, summing inside inner loop is O(1), total O(n^2).

💡 For n=1000, this means about 1,000,000 operations, which is slow but still feasible; for n=100,000 it is too slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem and is a good starting point.

🧠

Prefix Sum + Hash Map (Optimal)

💡 This approach uses prefix sums and a hash map to count subarrays efficiently by tracking cumulative sums and their frequencies.

Intuition

Keep track of cumulative sums and use a hash map to find how many previous sums equal current_sum - k, which indicates subarrays summing to k.

Algorithm

1. Initialize a hash map with {0:1} to count prefix sums.
2. Iterate through nums, accumulating sum.
3. Check if (current_sum - k) exists in map; if yes, add its count to result.
4. Update map with current_sum count.

💡 The key insight is that subarray sums can be found by differences of prefix sums, and the hash map tracks how often each prefix sum occurs.

</>

Code

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    prefix_counts = {0: 1}
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in prefix_counts:
            count += prefix_counts[prefix_sum - k]
        prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1
    return count

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

Line Notes

count = 0Initialize count of valid subarrays found so far

prefix_sum = 0Running total of elements seen so far to form prefix sums

prefix_counts = {0: 1}Map to store counts of prefix sums; 0 sum occurs once initially to handle subarrays starting at index 0

for num in nums:Iterate over each element in the array

prefix_sum += numUpdate running prefix sum with current element

if prefix_sum - k in prefix_counts:Check if a prefix sum exists that forms a subarray summing to k

count += prefix_counts[prefix_sum - k]Add number of such prefix sums to count, representing valid subarrays ending here

prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1Update count of current prefix sum in the map

import java.util.HashMap;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, prefix_sum = 0;
        HashMap<Integer, Integer> prefix_counts = new HashMap<>();
        prefix_counts.put(0, 1);
        for (int num : nums) {
            prefix_sum += num;
            if (prefix_counts.containsKey(prefix_sum - k)) {
                count += prefix_counts.get(prefix_sum - k);
            }
            prefix_counts.put(prefix_sum, prefix_counts.getOrDefault(prefix_sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subarraySum(new int[]{1,1,1}, 2)); // Output: 2
    }
}

Line Notes

int count = 0, prefix_sum = 0;Initialize count and running prefix sum

HashMap<Integer, Integer> prefix_counts = new HashMap<>();Map to store prefix sum frequencies

prefix_counts.put(0, 1);Prefix sum 0 occurs once initially to handle subarrays starting at index 0

for (int num : nums)Iterate over array elements

prefix_sum += num;Update running prefix sum with current element

if (prefix_counts.containsKey(prefix_sum - k))Check if complement prefix sum exists indicating valid subarray

count += prefix_counts.get(prefix_sum - k);Add frequency of complement prefix sum to count

prefix_counts.put(prefix_sum, prefix_counts.getOrDefault(prefix_sum, 0) + 1);Update frequency of current prefix sum

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    int count = 0, prefix_sum = 0;
    unordered_map<int, int> prefix_counts;
    prefix_counts[0] = 1;
    for (int num : nums) {
        prefix_sum += num;
        if (prefix_counts.find(prefix_sum - k) != prefix_counts.end()) {
            count += prefix_counts[prefix_sum - k];
        }
        prefix_counts[prefix_sum]++;
    }
    return count;
}

int main() {
    vector<int> nums = {1,1,1};
    cout << subarraySum(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

int count = 0, prefix_sum = 0;Initialize count and running prefix sum

unordered_map<int, int> prefix_counts;Hash map to store prefix sum counts

prefix_counts[0] = 1;Prefix sum 0 occurs once initially to handle subarrays starting at index 0

for (int num : nums)Iterate over each element

prefix_sum += num;Update running prefix sum with current element

if (prefix_counts.find(prefix_sum - k) != prefix_counts.end())Check if complement prefix sum exists indicating valid subarray

count += prefix_counts[prefix_sum - k];Add frequency of complement prefix sum to count

prefix_counts[prefix_sum]++;Increment count of current prefix sum

function subarraySum(nums, k) {
    let count = 0, prefix_sum = 0;
    const prefix_counts = new Map();
    prefix_counts.set(0, 1);
    for (const num of nums) {
        prefix_sum += num;
        if (prefix_counts.has(prefix_sum - k)) {
            count += prefix_counts.get(prefix_sum - k);
        }
        prefix_counts.set(prefix_sum, (prefix_counts.get(prefix_sum) || 0) + 1);
    }
    return count;
}

// Test
console.log(subarraySum([1,1,1], 2)); // Output: 2

Line Notes

let count = 0, prefix_sum = 0;Initialize count and running prefix sum

const prefix_counts = new Map();Map to store prefix sum frequencies

prefix_counts.set(0, 1);Prefix sum 0 occurs once initially to handle subarrays starting at index 0

for (const num of nums)Iterate over array elements

prefix_sum += num;Update running prefix sum with current element

if (prefix_counts.has(prefix_sum - k))Check if complement prefix sum exists indicating valid subarray

count += prefix_counts.get(prefix_sum - k);Add frequency of complement prefix sum to count

prefix_counts.set(prefix_sum, (prefix_counts.get(prefix_sum) || 0) + 1);Update frequency of current prefix sum

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through array with constant time hash map operations, total O(n).

💡 For n=100,000 this means about 100,000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This is the optimal approach and the one to implement in interviews for efficiency.

🧠

Prefix Sum + Hash Map (Using defaultdict / Map with Default)

💡 This approach is a slight variation of the optimal method using language-specific features to simplify code and improve readability.

Intuition

Same as approach 2 but uses default dictionary or map default values to avoid explicit checks.

Algorithm

1. Initialize a default dictionary or map with default 0 for prefix sums.
2. Iterate through nums, accumulate prefix sum.
3. Add count of prefix_sum - k to result if exists.
4. Increment count of current prefix sum.

💡 This reduces code clutter and potential bugs from missing keys.

</>

Code

from collections import defaultdict

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1
    for num in nums:
        prefix_sum += num
        count += prefix_counts[prefix_sum - k]
        prefix_counts[prefix_sum] += 1
    return count

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

Line Notes

from collections import defaultdictImport defaultdict to simplify map initialization with default 0 values

prefix_counts = defaultdict(int)Create map that returns 0 for missing keys automatically

prefix_counts[0] = 1Initialize prefix sum 0 count to handle subarrays starting at index 0

count += prefix_counts[prefix_sum - k]Add counts directly without checking if key exists, simplifying code

prefix_counts[prefix_sum] += 1Increment count for current prefix sum

import java.util.HashMap;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, prefix_sum = 0;
        HashMap<Integer, Integer> prefix_counts = new HashMap<>();
        prefix_counts.put(0, 1);
        for (int num : nums) {
            prefix_sum += num;
            count += prefix_counts.getOrDefault(prefix_sum - k, 0);
            prefix_counts.put(prefix_sum, prefix_counts.getOrDefault(prefix_sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.subarraySum(new int[]{1,1,1}, 2)); // Output: 2
    }
}

Line Notes

HashMap<Integer, Integer> prefix_counts = new HashMap<>();Create map for prefix sums with default 0 values using getOrDefault

prefix_counts.put(0, 1);Initialize prefix sum 0 count to handle subarrays starting at index 0

count += prefix_counts.getOrDefault(prefix_sum - k, 0);Add counts safely without explicit key existence check

prefix_counts.put(prefix_sum, prefix_counts.getOrDefault(prefix_sum, 0) + 1);Increment prefix sum count

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    int count = 0, prefix_sum = 0;
    unordered_map<int, int> prefix_counts;
    prefix_counts[0] = 1;
    for (int num : nums) {
        prefix_sum += num;
        count += prefix_counts[prefix_sum - k];
        prefix_counts[prefix_sum]++;
    }
    return count;
}

int main() {
    vector<int> nums = {1,1,1};
    cout << subarraySum(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

unordered_map<int, int> prefix_counts;Map to store prefix sums with default 0 for missing keys

prefix_counts[0] = 1;Initialize prefix sum 0 count to handle subarrays starting at index 0

count += prefix_counts[prefix_sum - k];Add counts directly, defaulting to 0 if key missing

prefix_counts[prefix_sum]++;Increment count for current prefix sum

function subarraySum(nums, k) {
    let count = 0, prefix_sum = 0;
    const prefix_counts = new Map([[0, 1]]);
    for (const num of nums) {
        prefix_sum += num;
        count += prefix_counts.get(prefix_sum - k) || 0;
        prefix_counts.set(prefix_sum, (prefix_counts.get(prefix_sum) || 0) + 1);
    }
    return count;
}

// Test
console.log(subarraySum([1,1,1], 2)); // Output: 2

Line Notes

const prefix_counts = new Map([[0, 1]]);Initialize map with prefix sum 0 count to handle subarrays starting at index 0

count += prefix_counts.get(prefix_sum - k) || 0;Add counts safely with default 0 if key missing

prefix_counts.set(prefix_sum, (prefix_counts.get(prefix_sum) || 0) + 1);Increment count for current prefix sum

⏱

Complexity

TimeO(n)

SpaceO(n)

Same as approach 2 but with cleaner code using default values.

💡 This approach is easier to write and less error-prone while maintaining optimal performance.

Interview Verdict: Accepted

This is a stylistic improvement on the optimal approach, recommended for clean code.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the optimal prefix sum + hash map approach unless asked otherwise.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	Yes	Mention only - never code for large inputs
2. Prefix Sum + Hash Map	O(n)	O(n)	No	Yes, with extra bookkeeping	Code this for optimal solution
3. Prefix Sum + Hash Map with Defaults	O(n)	O(n)	No	Yes	Preferred for clean and concise code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Describe brute force approach and its limitations.Step 3: Introduce prefix sums and hash map optimization.Step 4: Code the optimal solution carefully.Step 5: Test with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force to O(n), and coding accuracy with hash maps.

Common Follow-ups

• What if nums contains only positive numbers? → Sliding window possible but not for negatives.
• How to find the actual subarrays, not just count? → Store indices and reconstruct.
• Can this be done with less space? → No, hash map needed for prefix sums.
• What if k is zero? → Works the same, just count zero-sum subarrays.

💡 These follow-ups test your deeper understanding and ability to adapt the solution to variations.

🔍

Pattern Recognition

When to Use

Use this pattern when asked to find count of continuous subarrays with a target sum, especially with negative numbers allowed.

Signature Phrases

'continuous subarray sum equals k''count number of subarrays with sum k'

NOT This Pattern When

Problems asking for maximum subarray sum or non-continuous subsets use different techniques.

Similar Problems

Continuous Subarray Sum - similar prefix sum usage but with moduloSubarray Product Less Than K - similar counting but with product and sliding windowCount Number of Nice Subarrays - counting subarrays with certain properties using prefix sums

Practice

1. The following code attempts to find the longest contiguous subarray with equal number of 0s and 1s. Which line contains a subtle bug that can cause incorrect results on some inputs?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

medium

A. Line 3: Not initializing seen with {0: -1}

B. Line 6: Incorrect prefix_sum update logic

C. Line 8: Using max instead of min for max_length update

D. Line 10: Returning max_length instead of prefix_sum

Solution

1. Step 1: Check initialization of seen map

   Seen should start with {0: -1} to handle subarrays starting at index 0.

2. Step 2: Consequence of missing initialization

   Without {0: -1}, subarrays starting at index 0 with equal 0s and 1s are missed, causing incorrect max_length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing initial entry causes missed subarrays at start [OK]

Hint: Always initialize seen with sum 0 at index -1 [OK]

Common Mistakes:

• Forgetting initial seen entry
• Incorrect prefix sum update
• Wrong max_length update logic

2. What is the time complexity of the optimal Happy Number detection algorithm that uses a known set of unhappy cycle numbers and repeatedly computes the sum of squares of digits until termination?

medium

A. O(n) where n is the input number

B. O(k * n) where k is iterations and n is the number of digits

C. O(log n) because each iteration reduces the number size drastically

D. O(k * log n) where k is the number of iterations until 1 or cycle

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits, which takes O(log n) time since number of digits is proportional to log n.

2. Step 2: Count iterations until termination

   There are k iterations until number reaches 1 or cycle; total time is O(k * log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Time depends on iterations and digit count, not linear in n [OK]

Hint: Sum of squares per iteration costs O(log n) [OK]

Common Mistakes:

• Confusing input size n with number of digits
• Assuming linear O(n) time

3. Suppose the problem changes: now you want to detect if any number appears at least twice, but the array is extremely large and cannot fit into memory. Which approach is best suited to handle this scenario?

hard

A. Sort the array externally (external sort) and then scan for duplicates in a streaming fashion.

B. Use a hash set in memory as before, but process the array in chunks and merge results.

C. Use a bloom filter to probabilistically detect duplicates with limited memory.

D. Use nested loops on the entire array since it requires no extra space.

Solution

1. Step 1: Understand memory constraints

   The array is too large to fit in memory, so hash sets or sorting in memory are infeasible.

2. Step 2: Evaluate options

   External sorting is possible and practical for large data sets that cannot fit into memory. Bloom filters provide probabilistic detection but can yield false positives, which may not be acceptable depending on requirements. Nested loops are impractical due to O(n²) time complexity.

3. Step 3: Choose external sorting

   External sorting allows sorting data on disk and then scanning sequentially for duplicates, which is efficient and exact.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   External sorting handles large data sets with limited memory and provides exact duplicate detection [OK]

Hint: External sorting enables exact duplicate detection on large data sets [OK]

Common Mistakes:

• Assuming hash sets can handle huge data
• Ignoring external sorting costs
• Choosing nested loops despite inefficiency
• Overlooking bloom filter false positives

4. Suppose the problem is modified so that characters can be reused multiple times and you want to find the first unique character index after removing all duplicates. Which modification to the optimal approach correctly handles this variant?

hard

A. Sort the string and pick the first character that appears once, ignoring original indices.

B. Use a queue to track characters as they appear and remove duplicates dynamically during iteration.

C. Use the same frequency map approach but only consider characters with frequency exactly one after removal.

D. Use a brute force nested loop to check uniqueness after each removal.

Solution

1. Step 1: Understand the reuse and removal requirement

   Characters can be reused, so duplicates must be removed dynamically to find first unique.

2. Step 2: Identify approach that dynamically tracks uniqueness

   A queue can track order and remove duplicates as they appear, maintaining first unique efficiently.

3. Step 3: Evaluate other options

   Sorting loses original order; brute force is inefficient; frequency map alone can't handle dynamic removals.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Queue-based approach handles dynamic uniqueness correctly [OK]

Hint: Dynamic uniqueness needs a queue, not just frequency map [OK]

Common Mistakes:

• Assuming static frequency map suffices
• Sorting loses original order
• Brute force is too slow

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