algoadvance

Leetcode 560. Subarray Sum Equals K

Problem Statement

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

Clarifying Questions

Before we begin, let’s clarify a few points:

  1. Can the elements in the array be negative? (Yes)
  2. What should be returned if no subarray sums up to k? (Return 0)
  3. Is the array sorted? (No, the array is not sorted)
  4. Could the array be empty? (Yes)

Strategy

To solve the problem efficiently, we need an algorithm that can compute the results in linear time, i.e., O(n). A brute-force approach would be to use nested loops to check all possible subarrays, which would result in O(n^2) time complexity. This is not optimal for larger inputs.

A more efficient approach leverages the concept of prefix sums and a hashmap to store the cumulative frequencies of the sums. Here is the strategy:

  1. Traverse through the array while maintaining a cumulative sum.
  2. Use a hashmap (or dictionary) to store the frequency of each cumulative sum encountered.
  3. For each element, you compute the required complement that would make the sum of the subarray equal to k (i.e., current_sum - k).
  4. If this complement is found in the hashmap, it means there is a subarray ending at the current index that sums to k.
  5. Increment the result by the frequency of this complement.
  6. Update the hashmap with the current cumulative sum.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        // HashMap to store (cumulative sum, frequency) pairs
        Map<Integer, Integer> cumulativeSumFreq = new HashMap<>();
        
        cumulativeSumFreq.put(0, 1); // Initialize with cumulative sum 0 having one occurrence
        int cumulativeSum = 0;
        int count = 0;

        // Traverse through the array
        for (int num : nums) {
            cumulativeSum += num; // Update the cumulative sum
            
            // Calculate the complement which when combined with the previous sums would reach k
            int complement = cumulativeSum - k;
            
            // If complement is found in the map, increment the count by the frequency of the complement
            if (cumulativeSumFreq.containsKey(complement)) {
                count += cumulativeSumFreq.get(complement);
            }
            
            // Update the cumulative sum frequency in the map
            cumulativeSumFreq.put(cumulativeSum, cumulativeSumFreq.getOrDefault(cumulativeSum, 0) + 1);
        }
        
        return count;
    }
}

Time Complexity

This solution is efficient and handles large inputs within a reasonable time frame.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI