A solution to LeetCode Problem 560. Subarray Sum Equals K in JavaScript

Posted on by Vikas Kad

   

A solution to LeetCode Problem 560. Subarray Sum Equals K in JavaScript 

If you’re preparing for technical interviews or want to improve your coding skills, solving practice problems on LeetCode is a great way. 
In this post, we’ll discuss a solution to the “560. Subarray Sum Equals K” problem on LeetCode.

Problem Statement:

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to 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
  • -107 <= k <= 107

Solution:

One approach to solving this problem is to use a brute force method, where we check every possible subarray and see if its sum is equal to k. However, this approach has a time complexity of O(n^2), which is not efficient for large arrays.
A more efficient solution is to use a prefix sum array, where we store the sum of the elements from the start of the array up to the current index. We can then use this prefix sum array to find the sum of any subarray in constant time.
To solve the problem, we can iterate through the prefix sum array and for each element, we check if there is any previous element such that the difference between the two elements is equal to k. If we find such an element, it means that the subarray between these two elements has a sum of k. We can then increment our count by the number of subarrays between these two elements.
Here is the implementation of this solution in JavaScript:

function subarraySum(nums, k) {
  let count = 0;
  let sum = 0;
  const map = new Map();
  map.set(0, 1);

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
}

In the above code, we use a map to store the frequency of each prefix sum. We also initialize the map with a key of 0 and a value of 1, as there is always at least one subarray with a sum of 0 (the empty subarray).

As we iterate through the array, we add the current element to the sum and check if there is a previous element such that the difference between the two elements is equal to k. If we find such an element, we increment the count by the frequency of that element in the map. We also update the frequency of the current sum in the map.

This solution has a time complexity of O(n) and a space complexity of O(n), making it more efficient than the brute force method.

I hope this blog post was helpful in understanding how to solve the LeetCode Problem 560: Subarray Sum Equals K in JavaScript. If you have any questions or comments, feel free to leave them below.

3 thoughts on “A solution to LeetCode Problem 560. Subarray Sum Equals K in JavaScript”

  2. I’ve recently started a site, the information you offer on this website has helped me tremendously. Thank you for all of your time & work. “Patriotism is often an arbitrary veneration of real estate above principles.” by George Jean Nathan.

    Reply

  3. naturally like your web-site but you have to check the spelling on several of your posts. Several of them are rife with spelling issues and I find it very troublesome to tell the truth nevertheless I’ll definitely come back again.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *