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.

An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Clarifying Questions

1. Are negative numbers allowed in the input array?
   • Yes, the array may contain negative numbers.
2. What should we return if k is zero?
   • If k is zero, we need to check if there is a subarray whose sum is zero, which is a special case.
3. What is the maximum size of the array?
   • The array size can be quite large, potentially up to 10^5 elements.

Strategy

To solve this problem efficiently:

1. Use a hashmap to store the remainder when each prefix sum is divided by k.
2. If the same remainder appears again, it implies the subarray sum between these indices is a multiple of k.

Key Observations

• For a prefix sum and modular arithmetic:
  • If sum(i) % k == sum(j) % k where i < j, then the subarray sum from i+1 to j is a multiple of k.

Code

import java.util.HashMap;

public class ContinuousSubarraySum {
    public boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> remainderMap = new HashMap<>();
        // Initialize with remainder 0 at index -1 to handle subarray starting from index 0
        remainderMap.put(0, -1);
        int currentSum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            int remainder = (k == 0) ? currentSum : currentSum % k;

            // Fix for negative remainders
            if (remainder < 0) {
                remainder += k;
            }
            
            if (remainderMap.containsKey(remainder)) {
                if (i - remainderMap.get(remainder) > 1) {
                    return true;
                }
            } else {
                remainderMap.put(remainder, i);
            }
        }
        
        return false;
    }

    public static void main(String[] args) {
        ContinuousSubarraySum solution = new ContinuousSubarraySum();
        // Example Test Cases
        int[] nums1 = {23, 2, 4, 6, 7};
        int k1 = 6;
        System.out.println(solution.checkSubarraySum(nums1, k1)); // Expected output: true

        int[] nums2 = {23, 2, 6, 4, 7};
        int k2 = 6;
        System.out.println(solution.checkSubarraySum(nums2, k2)); // Expected output: true

        int[] nums3 = {23, 2, 6, 4, 7};
        int k3 = 13;
        System.out.println(solution.checkSubarraySum(nums3, k3)); // Expected output: false
    }
}

Time Complexity

• Time Complexity: O(n). We traverse the array once, and each operation (insertion in and lookup from the hashmap) occurs in constant time.
• Space Complexity: O(min(n, k)). In the worst case, we may store at most min(n, k) remainders in the hashmap (since storing more would result in detecting a cycle).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?