Scale Engineer

Subarray Sum Equals K

Med
#0543Time: O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic runtime, which is too slow for the given constraints.Space: O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.25 companies
Patterns
Prefix Sum
Data structures
ArrayHash Table
Companies
AMDByteDanceCapgeminiCisco

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward approach is to consider every possible subarray, calculate its sum, and check if the sum equals k. We can optimize the sum calculation by iterating through all possible start points and for each start point, extending the subarray to the right while keeping a running sum.

Algorithm

  • Initialize a counter count to 0.
  • Use an outer loop with index start from 0 to n-1 to select the starting element of the subarray.
  • Inside the outer loop, initialize a currentSum to 0.
  • Use an inner loop with index end from start to n-1. This loop defines the end of the subarray.
  • In each step of the inner loop, add nums[end] to currentSum. This currentSum represents the sum of the subarray nums[start...end].
  • If currentSum is equal to k, increment count.
  • After both loops complete, return count.

Walkthrough

This approach iterates through all possible starting points of a subarray. For each starting point, it iterates through all possible ending points, effectively generating every contiguous subarray. A running sum is maintained for the current subarray, and if this sum equals k, a counter is incremented.

public int subarraySum(int[] nums, int k) {    int count = 0;    for (int start = 0; start < nums.length; start++) {        int currentSum = 0;        for (int end = start; end < nums.length; end++) {            currentSum += nums[end];            if (currentSum == k) {                count++;            }        }    }    return count;}

Complexity

Time

O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic runtime, which is too slow for the given constraints.

Space

O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space (O(1) space complexity).

Cons

  • Inefficient time complexity, leading to "Time Limit Exceeded" on larger test cases as per the problem constraints.

Solutions

class Solution {public  int subarraySum(int[] nums, int k) {    Map<Integer, Integer> counter = new HashMap<>();    counter.put(0, 1);    int ans = 0, s = 0;    for (int num : nums) {      s += num;      ans += counter.getOrDefault(s - k, 0);      counter.put(s, counter.getOrDefault(s, 0) + 1);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem