Contiguous Subarray Sum
Determine if a given array contains a subarray of at least two elements whose sum is a multiple of a specified number k.
An array is considered to have a "good subarray" if there exists at least one subarray (consisting of two or more elements) such that the sum of the elements in this subarray is a multiple of k.
For example, the array [23, 2, 4, 7] with k = 6 has a "good subarray" ([2, 4]), as the sum 6 is a multiple of k = 6. The array [5, 0, 0, 0] with k = 3 also has a "good subarray" ([0, 0]), since the sum is 0, and 0 is a multiple of 3.
Examples
nums = [23, 2, 4, 7], k = 6 output: true nums = [5, 0, 0, 0], k = 3 output: true nums = null, k = 1 output: false
In these examples, the output is true if there exists a "good subarray" in the given array nums for the specified k, and false otherwise.
Can you come up with a solution with a time complexity of O(n)?
Can you come up with a solution with a space complexity of O(n)?
Our solution processes the input array by iterating through it while maintaining a hash map (remainder_index_map) of remainders and their corresponding indices. For each element in the array, we accumulate the sum (sum_so_far) and compute the remainder when divided by k. We check if this remainder has been encountered before in the hash map.
- If the remainder is not in the hash map, we store the current index associated with this remainder.
- If the remainder has been seen before, we calculate the distance between the current index and the index of the previously seen remainder. If this distance is greater than or equal to the minimum subarray length (
MIN_GOOD_SUBARRAY_LIMIT), we returnTrue, indicating that a subarray with the required properties exists.
If the loop completes without finding such a subarray, we return False.
The use of a hash map ensures that each element is processed efficiently, as it allows constant-time lookups and insertions.
def has_good_subarray(nums, k):
if nums is None:
return False
MIN_GOOD_SUBARRAY_LIMIT = 2
sum_so_far = 0
remainder_index_map = {0: -1} # Manually put the initial key-value pair
for current_index, num in enumerate(nums):
sum_so_far += num
remainder = sum_so_far % k
if remainder not in remainder_index_map:
remainder_index_map[remainder] = current_index
elif current_index - remainder_index_map[remainder] >= MIN_GOOD_SUBARRAY_LIMIT:
return True
return FalseTime Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, performing constant-time operations (hash map lookups and insertions) for each element.
Space Complexity: The solution uses O(n) space for the hash map that stores the remainders and their indices. In the worst case, all remainders are unique, resulting in the hash map containing n entries.
Let’s say you are given an integer array nums and an integer k. Return true if nums has a subarray where its length is at least two, and the sum of the elements in the subarray is a multiple of k.
Watch Neeraj, a Senior Engineering Manager, give his answer to this software engineering interview question.
Would be better to adjust resolution in the video player directly.