Katkat
Back

Count subarrays with sum equals k

AppleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize subarray sum calculations using prefix sums and hash maps to achieve linear time complexity.

Problem Statement

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

Function Signature

def subarray_sum(nums: List[int], k: int) -> int:

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 Explanation: The subarrays are [1, 1] (indices 0 to 1) and [1, 1] (indices 1 to 2).

Example 2: Input: nums = [1, 2, 3], k = 3 Output: 2 Explanation: The subarrays are [1, 2] and [3].

Edge Cases

  • Arrays containing negative numbers, zeros, or a single element.
  • Scenarios where no subarray sums to k (return 0).
  • Scenarios where multiple subarrays share the same sum due to zeros in the input.

Hints

Hint 1

Consider calculating the prefix sum at each index, which represents the sum of all elements from index 0 to i.

Hint 2

A subarray sum from index i to j can be expressed as the difference between the prefix sum at j and the prefix sum at i-1.

Hint 3

Use a hash map (dictionary) to store the frequency of each prefix sum encountered so far to identify how many previous prefix sums satisfy the condition `current_sum - k = previous_sum`.

Follow-up questions

  • How would your approach change if you were asked to find the length of the longest subarray with a sum equal to k?
  • What is the space complexity of your solution, and can it be optimized further?
  • How would you handle the case where the array is too large to fit into memory and must be processed as a stream?