Subarray Sum Equals K LeetCode Solution


Frequently asked in Amazon Bloomberg ByteDance Expedia Facebook Google LinkedIn Oracle PayPal Quora Snapchat Tesla Twilio Visa Walmart Labs Yandex
LeetCode LeetCodeSolutions tiktokViews 5573

Problem Statement

The Subarray Sum Equals K LeetCode Solution – “Subarray Sum Equals K” states that you are given an array of integers “nums” and an integer ‘k’, return the total number of continuous subarrays whose sum equals to ‘k’.

Example:

Subarray Sum Equals K LeetCode Solution

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

Explanation:

There are two subarrays whose sum is 3:

  • First from index 0 to 1 i.e. [1, 2],
  • Second from index 2 to 2 i.e. [3]
nums = [1, 1, 1],
k=3
2

Explanation:

There are two subarrays whose sum is 2:

  • First from index 0 to 1 i.e. [1, 1],
  • Second from index 1 to 2 i.e. [1, 1]

Approach

Idea:

The main idea is to use a hash map to store the frequency of prefix sums.

So, we’ll iterate over the array, finding how many subarrays exist whose sum equals k and ends at the current point on each iteration.

So, if the value of the prefix sum up to this point is ‘prefixSum,’ the next step is to determine how many prefix sums exist whose value is (prefixSum – k). It can be found in O(1) by using the hash map, which stores the frequency of prefix sums.

Code

C++ Program of Subarray Sum Equals K:

#include <bits/stdc++.h>
using namespace std;
int subarraySum(vector<int> &nums, int k)
{
    int n = nums.size();
    int answer = 0;
    unordered_map<int, int> prefixSumsFrequency;
    prefixSumsFrequency[0] = 1;
    int prefixSum = 0;
    for (int i = 0; i < n; i++)
    {
        prefixSum += nums[i];
        answer += prefixSumsFrequency[prefixSum - k];
        prefixSumsFrequency[prefixSum]++;
    }
    return answer;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    int k = 3;
    cout << subarraySum(nums, k);
    return 0;
}
2

JAVA Program of Subarray Sum Equals K:

import java.util.*;

public class TutorialCup {
    public static int subarraySum(int[] nums, int k) {
        int answer = 0, prefixSum = 0;
        Map<Integer, Integer> prefixSumsFrequency = new HashMap<>();
        prefixSumsFrequency.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            answer += prefixSumsFrequency.getOrDefault(prefixSum - k, 0);
            prefixSumsFrequency.put(prefixSum, prefixSumsFrequency.getOrDefault(prefixSum, 0) + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 2, 3 };
        int k = 3;
        System.out.println(subarraySum(nums, k));
    }
}

2

Complexity Analysis for Subarray Sum Equals K LeetCode Solution

Time Complexity

The time complexity of the above code is O(n) because we are traversing the array only once.

Space Complexity

The space complexity of the above code is O(n) because we are using a hash map to store the frequency of prefix sums.

Reference https://en.wikipedia.org/wiki/Maximum_subarray_problem, https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

Translate »