Continuous Subarray Sum

Medium

Yahoo

2 views

Topics:

ArraysHash TableMath

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Continuous Subarray Sum

Medium

Yahoo

2 views

Topics:

ArraysHash TableMath

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 <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the values within the `nums` array, and what is the range for `k`? Could either be negative, zero, or very large?
What should I return if the input array `nums` is null or empty?
Is `k` guaranteed to be non-negative? If `k` is zero, what defines a multiple of `k`?
Does the continuous subarray have to be contiguous (adjacent elements), or can it be non-contiguous?
If multiple continuous subarrays satisfy the condition, should I return as soon as I find one, or do I need to find the shortest/longest such subarray (assuming there's a return of the subarray itself and not just a boolean)?

Brute Force Solution

Approach

The brute force approach to solving this problem is all about trying every single possible group of numbers to see if any of them meet our requirement. We will look at every possible group size and starting location within the list of numbers. This is similar to checking every combination of items in a vending machine to see if any give you exact change.

Here's how the algorithm would work step-by-step:

First, consider the first number by itself. Does this single number meet the requirement?
Next, consider the first two numbers added together. Does this sum meet the requirement?
Continue adding one more number at a time to this group, checking the sum each time, until you reach the end of the list.
Now, start from the second number in the list, and repeat the process of adding numbers one by one and checking their sum.
Keep doing this, shifting the starting point one number at a time, until you've started at every number in the list.
During this process, keep track of any group of numbers that meets the requirement.
Finally, once you've checked all possible groups, you can report if you found any that meet the requirement, or indicate that no such group exists.

Code Implementation

def continuous_subarray_sum_brute_force(numbers, target):
    list_length = len(numbers)

    # Iterate through all possible starting indices
    for start_index in range(list_length):

        # Iterate through all possible subarray lengths
        for end_index in range(start_index, list_length):
            current_sum = 0

            # Calculate the sum of the current subarray
            for index in range(start_index, end_index + 1):
                current_sum += numbers[index]

            # Check if the current subarray sum is a multiple of the target
            if target != 0:                if current_sum % target == 0:
                    return True # Subarray found matching target criteria
            else:
                if current_sum == 0:
                    return True # Subarray found matching target criteria

    # No subarray found meeting the criteria
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through the array using nested loops. The outer loop starts at each of the n elements, representing the beginning of a potential subarray. The inner loop expands the subarray from that starting point to the end of the array, performing a sum calculation for each expansion. In the worst case, this means for each of the n starting points, we may iterate up to n times, resulting in approximately n * n/2 calculations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach calculates subarray sums iteratively. It doesn't use any auxiliary data structures like arrays, hash maps, or recursion. It only keeps track of the starting index of the subarray, the current index within the subarray, and the current sum which requires constant space. Therefore, the space complexity is independent of the input size N (the number of elements in the list) and is O(1).

Optimal Solution

Approach

The key idea is to use remainders after division. We keep track of the running sum's remainder and use that to check if a suitable subarray exists, avoiding the need to check every possible subarray.

Here's how the algorithm would work step-by-step:

Calculate a running total as you go through the numbers.
After each new number, find the remainder after dividing the running total by the target number.
Remember the first time you see each remainder.
If you see the same remainder again, it means the sum of the numbers between those two times is a multiple of the target number.
If this multiple contains at least two numbers, you've found a continuous group that satisfies the condition. Return true as soon as you find one.
If you go through all the numbers and don't find such a group, return false.

Code Implementation

def continuous_subarray_sum(numbers, target):
    if not numbers or len(numbers) < 2:
        return False

    remainder_map = {0: -1}
    running_sum = 0

    for index, number in enumerate(numbers):
        running_sum += number
        remainder = running_sum % target

        # Store the first occurrence of each remainder.
        if remainder not in remainder_map:
            remainder_map[remainder] = index
        else:
            # If remainder repeats, check subarray length.
            if index - remainder_map[remainder] > 1:
                return True

    # No subarray found meeting the criteria.
    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once to calculate the running sum and remainder. A hash map (or similar data structure) is used to store and retrieve remainders. Hash map operations like insertion and lookup have an average time complexity of O(1). Therefore, the dominant operation is the single iteration through the array, resulting in a time complexity of O(n).

Space Complexity

O(min(N, K)) – The provided solution uses a hash map to store remainders and their first occurrences. In the worst case, we might store a different remainder for each prefix sum. However, since the remainder is always between 0 and K-1, where K is the target number, the maximum number of distinct remainders we can store is min(N, K), where N is the number of elements in the input array. Therefore, the auxiliary space used by the hash map is proportional to min(N, K), resulting in a space complexity of O(min(N, K)).

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately as a continuous subarray of size at least two cannot exist.
Array with less than two elements	Return false immediately because the problem requires a subarray of at least size 2.
k is zero and the array contains at least two consecutive zeros	Handle the zero k case by checking for a subarray with a sum of zero when k is zero, and return true immediately if found.
k is zero and the array does not contain at least two consecutive zeros	Handle the zero k case by checking for a subarray with a sum of zero when k is zero, and return false if not found.
Array with all elements equal to zero	If k is non-zero, return true; otherwise, handle as described in the edge case where k is zero.
Array with negative numbers and k is negative	The modulus operator should be correctly applied to negative numbers to handle the cases with negative elements and negative k values.
Large array with large numbers leading to potential integer overflow	Use long data type to store prefix sums to avoid integer overflow.
Large array where no solution exists	The solution should be efficient enough (O(n)) to avoid timeouts even when no subarray satisfies the condition.