algoadvance

Leetcode 523. Continuous Subarray Sum

Problem Statement

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

A continuous subarray is defined as a non-empty sequence of elements of the array in the order they occur.

Clarifying Questions

  1. What should we do if k is zero? If k is zero, it means we are looking for any subarray whose sum is zero.

  2. Can negative numbers be present in nums? Yes, the array can have negative, zero, and positive integers.

  3. What’s the size range of nums and the possible values of k? The length of the array nums will be in the range [1, 10^5], and the integer k will be in the range [-10^9, 10^9] including zero.

Strategy

  1. Use Remainder Theorem (modulus operation):
    • If we find any two prefix sums prefix_sum[i] and prefix_sum[j] such that (prefix_sum[j] - prefix_sum[i]) % k == 0, then the sum of the elements between i+1 and j is a multiple of k.
    • To efficiently check for these conditions, use a hashmap (unordered_map) to store the remainders of prefix sums divided by k.
  2. Initialization:
    • Start by initializing a hashmap with the remainder of zero mapped to index -1 to handle cases where the prefix sum itself is a multiple of k.
  3. Iterate through the array:
    • Keep a running sum of the elements.
    • Compute the remainder of the current prefix sum with k.
    • If this remainder has been seen before and the subarray length is at least 2, return true.
    • Otherwise, store the current remainder with its index in the hashmap.
  4. Edge cases:
    • Handle negative remainders by adjusting using % k.
    • If k is zero, check if there are at least two consecutive zeroes.

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> remainder_index_map;
        remainder_index_map[0] = -1; // to handle cases where the sum itself is a multiple of k
        int running_sum = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            running_sum += nums[i];
            int remainder = (k == 0) ? running_sum : running_sum % k;
            
            // Adjust for negative remainder
            if (remainder < 0) remainder += k;
            
            if (remainder_index_map.find(remainder) != remainder_index_map.end()) {
                if (i - remainder_index_map[remainder] > 1) {
                    return true;
                }
            } else {
                remainder_index_map[remainder] = i;
            }
        }
        
        return false;
    }
};

Time Complexity

Summary

This approach efficiently checks for any continuous subarray whose sum is a multiple of k by leveraging the properties of the remainder operation and utilizing a hashmap to track remainders of prefix sums.

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