560 LeetCode problem solution

LeetCode problem link: 560. Subarray Sum Equals K

LeetCode 560 problem description

Medium level problem.

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Example 2:

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

Constraints:

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

LeetCode 560 problem: solution explanation

This problem can be solved using Prefix Sum + Hash Map.

While iterating through the array, we keep the sum of all elements from the beginning of the array to the current position:

sum += num;

Suppose the current prefix sum is sum. We need to know whether there was an earlier prefix sum such that the difference between the current sum and that previous sum is exactly k.

sum - previousSum = k

Therefore:

previousSum = sum - k

So for every position, we look for sum - k among the prefix sums we have already seen.

For example:

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

prefix sums: 0, 1, 3, 4, 6

When the current prefix sum is 3, we look for 3 - 3 = 0. The prefix sum 0 exists, so the subarray [1, 2] has sum 3.

When the current prefix sum is 4, we look for 4 - 3 = 1. The prefix sum 1 exists, so the subarray [2, 1] has sum 3.

We use a Hash Map to store how many times each prefix sum has appeared:

prefix sum -> frequency

This is important because the same prefix sum can occur multiple times, and each occurrence can produce a different valid subarray.

Initially, the Hash Map contains:

0 -> 1

This represents the empty prefix before the array starts. It allows us to count a valid subarray that starts at index 0.

For every number, we first update the current prefix sum, then add the number of previous occurrences of sum - k to the result, and finally store the current prefix sum in the Hash Map.

LeetCode 560 problem: complexity

We process every element exactly once. Hash Map lookup and insertion take O(1) average time.

Time complexity: O(n)
Space complexity: O(n)

The O(n) time complexity is optimal because every element of the array has to be processed at least once.

Pattern: Prefix Sum
Technique: Hash Map / Prefix Sum Frequency

LeetCode 560 C++ solution

class Solution {
public:
  int subarraySum(vector<int>& nums, int k)
  {
    unordered_map<int, int> freq;
    freq.reserve(nums.size() * 2);
    freq[0] = 1;

    int sum = 0;
    int result = 0;

    for(int num : nums)
    {
      sum += num;

      if(auto it = freq.find(sum - k); it != freq.end())
        result += it->second;

      freq[sum]++;
    }

    return result;
  }
};

LeetCode 560 Java solution

class Solution {
  public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);

    int sum = 0;
    int result = 0;

    for(int num : nums) {
      sum += num;

      result += freq.getOrDefault(sum - k, 0);

      freq.put(sum, freq.getOrDefault(sum, 0) + 1);
    }

    return result;
  }
}

LeetCode 560 JavaScript solution

var subarraySum = function(nums, k) {
  const freq = new Map();
  freq.set(0, 1);

  let sum = 0;
  let result = 0;

  for(const num of nums) {
    sum += num;

    result += freq.get(sum - k) || 0;

    freq.set(sum, (freq.get(sum) || 0) + 1);
  }

  return result;
};

LeetCode 560 TypeScript solution

function subarraySum(nums: number[], k: number): number {
  const freq: Map<number, number> = new Map();
  freq.set(0, 1);

  let sum: number = 0;
  let result: number = 0;

  for(const num of nums) {
    sum += num;

    result += freq.get(sum - k) ?? 0;

    freq.set(sum, (freq.get(sum) ?? 0) + 1);
  }

  return result;
}

LeetCode 560 Python solution

class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
    freq = {0: 1}

    total = 0
    result = 0

    for num in nums:
      total += num

      result += freq.get(total - k, 0)

      freq[total] = freq.get(total, 0) + 1

    return result