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:
k.Note that:
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 <= 1050 <= nums[i] <= 1090 <= sum(nums[i]) <= 231 - 11 <= k <= 231 - 1The idea is to use a running or cumulative sum and check the remainder when this sum is divided by k. If any two prefix sums have the same remainder, the subarray sum between these indices is divisible by k.
We maintain a hashmap to store each remainder and its index. As we iterate over the array, we update the running sum and check its remainder. If the remainder has been seen before and the subarray length is at least 2, we return true. If not, we continue. If we finish the loop without finding such a subarray, we return false.
In this C implementation, we use a dynamically allocated array to simulate a hashmap. We initialize all elements to -1, except the zero remainder, which is initialized to index 0 to handle the case where a subarray from the start has a sum that is a multiple of k.
The main loop updates the cumulative sum, calculates its modulo with k, and checks if this remainder was seen before in the hashmap, with the appropriate handling for negative mod cases. If so and the subarray has at least length 2, it returns true. Otherwise, it logs the index of this new remainder.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of nums, since we iterate over the array only once.
Space Complexity: O(k), as we use a hashmap (or array) to store remainders which can be 0 through k-1 in the worst case.
This approach attempts every possible subarray of length at least 2, calculating the sum for each and checking if it is a multiple of k. Although not efficient, this serves as a basic solution for smaller inputs.
The process involves iterating over each possible starting point of a subarray, then for each starting point, iterating over each possible ending point to compute the sum, subsequently verifying its divisibility by k.
This brute force approach implemented in C checks all subarrays of length at least 2. It attempts every start position and iterates all feasible end positions to compute subarray sum and verify divisibility by k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n²) because of the nested loop structure iterating through potential subarray limits.
Space Complexity: O(1) as no extra space apart from a few variables is used.
| Approach | Complexity |
|---|---|
| Prefix Sum with Modulo and HashMap | Time Complexity: O(n), where n is the length of nums, since we iterate over the array only once. Space Complexity: O(k), as we use a hashmap (or array) to store remainders which can be 0 through k-1 in the worst case. |
| Iterative Brute Force (Naive Approach) | Time Complexity: O(n²) because of the nested loop structure iterating through potential subarray limits. Space Complexity: O(1) as no extra space apart from a few variables is used. |
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python • NeetCode • 266,725 views views
Watch 9 more video solutions →Practice Continuous Subarray Sum with our built-in code editor and test cases.
Practice on FleetCode