{x}
blog image

Continuous Subarray Sum

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

  • its length is at least two, and
  • the sum of the elements of the subarray is a multiple of k.

Note that:

  • A subarray is a contiguous part of the array.
  • 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.

 

Example 1:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13
Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= sum(nums[i]) <= 231 - 1
  • 1 <= k <= 231 - 1

Solution Explanation: Continuous Subarray Sum

This problem asks whether there exists a subarray within the input array nums that has a length of at least two and whose elements sum to a multiple of k.

Approach: Prefix Sum with Hash Table

The most efficient approach leverages the concept of prefix sums and a hash table to achieve linear time complexity. Here's how it works:

  1. Prefix Sum: We calculate the prefix sum of the array as we iterate through it. The prefix sum at index i is the sum of all elements from index 0 up to i.

  2. Remainders: Instead of storing the entire prefix sum, we only store its remainder when divided by k. This is because if two prefix sums have the same remainder modulo k, their difference (which represents the sum of a subarray) must be a multiple of k.

  3. Hash Table: We use a hash table (dictionary in Python) to store the remainders and their corresponding indices. The key is the remainder, and the value is the index where that remainder first appeared.

  4. Iteration and Check: As we iterate through the array and calculate the prefix sum's remainder, we check if this remainder already exists in the hash table.

    • If it doesn't exist, we add the remainder and its index to the table.
    • If it does exist, it means we've found two prefix sums with the same remainder. The difference between their indices represents a subarray whose sum is a multiple of k. We need to ensure the subarray length is at least 2 (i - d[s] > 1), where i is the current index and d[s] is the index of the previous occurrence of the remainder s.

  5. Return Value: If we find such a subarray, we return true. Otherwise, after iterating through the entire array, we return false.

Time Complexity Analysis:

The algorithm iterates through the array once, performing constant-time operations (modulo, hash table lookup, insertion) in each iteration. Therefore, the time complexity is O(n), where n is the length of the input array.

Space Complexity Analysis:

In the worst case, the hash table may store all the remainders (up to n entries). Hence, the space complexity is O(n).

Code Examples:

The code examples provided in Python, Java, C++, Go, and TypeScript all implement the same algorithm. They differ only in syntax, but the core logic remains consistent. The use of a hash table/dictionary is crucial for achieving the O(n) time complexity.

Example Walkthrough (Python):

Let's say nums = [23, 2, 4, 6, 7] and k = 6.

| Index (i) | nums[i] | Prefix Sum | Remainder (s) | d[s] | i - d[s] > 1 | |---|---|---|---|---|---| | 0 | 23 | 23 | 5 | {5: 0} | False | | 1 | 2 | 25 | 1 | {5: 0, 1: 1} | False | | 2 | 4 | 29 | 5 | {5: 0, 1: 1} | 2 - 0 > 1 (True) |

At index 2, the remainder is 5, which already exists in d at index 0. The condition 2 - 0 > 1 is true, so the function returns true because the subarray [2, 4] sums to 6, a multiple of 6.

This detailed explanation covers the algorithm's logic, complexity analysis, and code implementations in several programming languages.