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 key idea behind Continuous Subarray Sum is to determine whether a subarray of length at least two has a sum that is a multiple of k. A brute-force approach would check every possible subarray and compute its sum, but this leads to a quadratic time complexity and is inefficient for large inputs.
A more optimal strategy uses the concept of prefix sums combined with a hash map. As you iterate through the array, maintain a running sum and compute its remainder when divided by k. If the same remainder appears again at a later index, it means the sum of the elements between those indices is divisible by k. A hash table can store the first occurrence of each remainder to quickly verify this condition.
This approach efficiently detects qualifying subarrays while ensuring the length constraint is satisfied. By tracking remainders and indices, we reduce redundant calculations and achieve a near linear-time solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum with Hash Map | O(n) | O(min(n, k)) |
NeetCode
The 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.
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.
1import java.util.HashMap;
2
3public class Solution {
4 public static boolean checkSubarraySum(int
In this Java code, we use HashMap to maintain the remainder of the cumulative sum and its respective index. The logic similarly involves summing and modding while looking for previously encountered modulus values to ensure subarray validity.
Handling of negative remainders is ensured by adjusting with k if needed, which allows the code to work efficiently for any integer k.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar prefix-sum-based variations frequently appear in FAANG and other top tech interviews. It tests understanding of arrays, hashing, and mathematical properties of prefix sums.
A hash map is the most effective data structure for this problem. It stores the first index where each remainder of the prefix sum modulo k appears, allowing quick detection of valid subarrays.
The optimal approach uses prefix sums along with a hash map to track remainders of the running sum modulo k. If the same remainder appears again with a gap of at least two indices, the subarray between them has a sum divisible by k.
Using modulo helps identify when two prefix sums differ by a multiple of k. If two prefix sums have the same remainder when divided by k, their difference is divisible by k, indicating a valid subarray.
The Python implementation follows a brute force strategy, iterating through all pairs of start and end points for subarrays to deduce their sums and ascertain if divisible by k.
While comprehensive, this solution is notably slow on larger input scales.