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. 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. 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. Sort the array and then scan linearly to find the longest consecutive sequence.

B. For each number, scan the entire array to count consecutive numbers starting from it.

C. Use dynamic programming to store the longest consecutive sequence ending at each number.

D. Use a hash set to track numbers and only start counting sequences from numbers that have no predecessor in the set.

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 for optimality

   Sorting then scanning is O(n log n), brute force scanning is O(n²), and DP is not straightforward here. Using a hash set to track numbers and only starting sequences from numbers without a predecessor ensures each sequence is counted once, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash set approach avoids redundant work and achieves linear time [OK]

Hint: Only start sequences from numbers without a predecessor [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Trying DP without clear subproblem
• Brute force scanning entire array repeatedly

3. You are given an array of positive integers and a target value x. You want to remove elements from the start and/or end of the array so that the sum of removed elements equals x. Which approach guarantees finding the minimum number of removals efficiently?

easy

A. Use a greedy approach removing the largest elements first from either end until sum equals x.

B. Find the longest subarray whose sum equals total sum minus x using a sliding window, then subtract its length from the array length.

C. Use dynamic programming to find all combinations of prefix and suffix sums that add up to x.

D. Try all possible combinations of removing elements from the start and end using nested loops.

Solution

1. Step 1: Understand the problem transformation

   The problem of removing elements from the ends summing to x is equivalent to finding a subarray in the middle with sum = totalSum - x.

2. Step 2: Recognize the sliding window pattern

   Finding the longest subarray with sum = target (totalSum - x) can be done in O(n) using a sliding window, which leads to minimum removals = array length - longest subarray length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window finds longest subarray efficiently [OK]

Hint: Transform to longest subarray sum problem [OK]

Common Mistakes:

• Trying greedy removal from ends fails on some cases
• Brute force is too slow for large inputs
• Dynamic programming overcomplicates the problem

4. What is the time complexity of the optimal hash map with prefix sum remainders approach for the Continuous Subarray Sum problem, assuming the input array length is n and the divisor is k?

medium

A. O(n * k) due to nested loops over array and modulo values

B. O(n^2) because of checking all subarrays implicitly via prefix sums

C. O(n) because each element is processed once and hash map operations are O(1) on average

D. O(k) since the remainder map size is limited by k

Solution

1. Step 1: Analyze the loop and hash map operations

   The algorithm iterates over the array once (O(n)) and performs O(1) average-time hash map lookups and insertions.

2. Step 2: Consider the size of the remainder map

   The remainder map size is at most min(n, k), but this does not increase the iteration count beyond O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) time [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing prefix sums with nested loops
• Assuming modulo k adds multiplicative factor
• Ignoring average O(1) hash map operations

5. Suppose the problem is modified so that elements can be reused multiple times to form pairs whose sums are divisible by k. Which of the following changes to the original frequency map approach correctly handles this variant?

hard

A. Use a dynamic programming approach to count combinations allowing reuse and check divisibility.

B. Use a frequency map but check only if the total number of elements is even, ignoring remainder counts.

C. Use a greedy approach to pair elements as many times as possible without frequency constraints.

D. Keep the frequency map but allow pairing elements with themselves any number of times.

Solution

1. Step 1: Understand reuse changes problem nature

   Allowing reuse means frequency counts no longer limit pairing; pairs can be formed repeatedly from same elements.

2. Step 2: Identify suitable approach

   Frequency map approach relies on fixed counts and fails with reuse. Dynamic programming can track sums with unlimited usage, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles unlimited reuse and sum divisibility constraints [OK]

Hint: Reuse breaks fixed frequency assumptions; DP needed [OK]

Common Mistakes:

• Assuming frequency map still works unchanged
• Ignoring remainder counts when reuse allowed
• Using greedy without correctness guarantees