Skip to main content

18. Subarray Sum Equals K

mediumAsked at Flipkart

Count contiguous subarrays summing to a target — Flipkart uses it to test the prefix-sum + hash map pattern behind their daily sales-target reporting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k. Values may be negative so two-pointer sliding does not apply.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Examples

Example 1

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

Example 2

Input
nums = [1,2,3], k = 3
Output
2

Approaches

1. Brute force windows

Enumerate every (i, j) and check the sum.

Time
O(n^2)
Space
O(1)
for (let i=0;i<n;i++) { let s=0; for (let j=i;j<n;j++) { s+=nums[j]; if (s===k) count++; } }

Tradeoff:

2. Prefix-sum hash map

Track running sum; if (sum - k) was seen before, every prior occurrence yields a subarray ending here. Single linear pass.

Time
O(n)
Space
O(n)
function subarraySum(nums, k) {
  const counts = new Map([[0, 1]]);
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    ans += counts.get(sum - k) || 0;
    counts.set(sum, (counts.get(sum) || 0) + 1);
  }
  return ans;
}

Tradeoff:

Flipkart-specific tips

Flipkart panels love when you call out why two-pointer sliding fails (negative numbers) before introducing the prefix-sum approach — it shows you reasoned, not memorized.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Subarray Sum Equals K and other Flipkart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →