Minimum Size Subarray in Infinite Array

Medium

DE Shaw

1 view

Topics:

ArraysTwo PointersSliding Windows

You are given a 0-indexed array nums and an integer target.

A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.

Example 1:

Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

Example 2:

Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

Example 3:

Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= target <= 10⁹

Minimum Size Subarray in Infinite Array

Medium

DE Shaw

1 view

Topics:

ArraysTwo PointersSliding Windows

You are given a 0-indexed array nums and an integer target.

A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

Return the length of the shortest subarray of the array infinite_nums with a sum equal to target. If there is no such subarray return -1.

Example 1:

Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

Example 2:

Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

Example 3:

Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= target <= 10⁹

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 is the range of values for the integers in the `nums` array and the `target`?
Can the input array `nums` be empty?
If there are multiple subarrays with the minimum size that sum up to the target, can I return any one of them?
Is the target guaranteed to be positive, or can it be zero or negative?
Could the sum of all elements in `nums` be less than the target? What should I return in that case?

Brute Force Solution

Approach

The brute force method is like trying every possible option until you find the right one. For this problem, we'll explore all possible continuous sections of numbers to see which one adds up to the target with the fewest numbers.

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

Start with the smallest possible section: just the first number.
Check if this single number equals the target.
If not, consider the first two numbers together as a section and check their sum.
Continue to consider the first three, four, and so on, until you include all the numbers as the first section, checking the sum each time.
Now, move to the second number. Consider it alone. Then the second and third numbers together. Then the second, third, and fourth numbers together, and so on.
Keep doing this, shifting the starting point of the section one number at a time, and increasing the section size, until you've considered all possible sections.
Each time you find a section that exactly matches the target, remember the number of numbers in that section.
After trying all possible sections, pick the section that had the fewest numbers and still matched the target.

Code Implementation

def min_subarray_infinite_array_brute_force(numbers, target):    minimum_subarray_length = float('inf')
    array_length = len(numbers)
    
    for start_index in range(array_length):
        for end_index in range(start_index, array_length):
            current_subarray = numbers[start_index:end_index+1]
            current_sum = sum(current_subarray)

            if current_sum == target:
                current_subarray_length = end_index - start_index + 1
                # We need to consider the infinite array.
                minimum_subarray_length = min(minimum_subarray_length, current_subarray_length)
                
            elif current_sum < target:
                number_of_repeats = (target - current_sum) // sum(numbers) 
                current_sum += sum(numbers) * number_of_repeats
                current_subarray_length = (end_index - start_index + 1) + array_length * number_of_repeats
                
                if current_sum == target:
                   # Update minimum length if we find a better one
                   minimum_subarray_length = min(minimum_subarray_length, current_subarray_length)
                else:
                    remaining_target = target - current_sum
                    temp_sum = 0
                    temp_length = 0
                    
                    for i in range(array_length):
                        temp_sum += numbers[i]
                        temp_length += 1
                        if temp_sum == remaining_target:
                            current_subarray_length += temp_length
                            minimum_subarray_length = min(minimum_subarray_length, current_subarray_length)
                            break
                        elif temp_sum > remaining_target:
                            break
                            
    if minimum_subarray_length == float('inf'):
        return -1
    else:
        return minimum_subarray_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves iterating through all possible subarrays of the input array. The outer loop iterates from the starting index of the subarray, and the inner loop extends the subarray to calculate its sum. In the worst case, the outer loop runs n times, and for each iteration of the outer loop, the inner loop can run up to n times, resulting in a nested loop structure. Therefore, the time complexity is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The described brute force approach only requires a few variables to store the start and end indices of the subarray, the current sum, and the minimum length found so far. These variables take up a constant amount of space, irrespective of the size of the input array, which we denote as N. Therefore, the auxiliary space used by this algorithm is constant and does not scale with the input size. The space complexity is O(1).

Optimal Solution

Approach

Imagine the array repeats forever. The key is to realize we only need to consider a portion of this infinite array. We find the smallest chunk that adds up to the target value (or a multiple), then we use a sliding window to optimize.

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

First, calculate the sum of all numbers in the original array. If this sum divides evenly into the target, the whole original array repeated some number of times makes exactly the target, so the answer is the length of the original array multiplied by that repetition number.
If it doesn't divide evenly, find a combination of elements in the original array whose sum equals the remainder of the target divided by the original array's sum. This is the 'leftover' amount needed.
To find the shortest combination for the 'leftover', use a technique where you expand and contract a window. Start with an empty window at the beginning of the array.
Keep expanding the window to the right until the sum inside the window is equal to or greater than the 'leftover'.
Once the sum is equal or greater, shrink the window from the left, one number at a time, while making sure the sum remains greater than or equal to the 'leftover'. Keep track of the smallest window size that fulfills this condition.
If you reach the end of the array with the right side of the window, wrap around to the beginning and keep expanding until you have considered all possible windows.
The size of the smallest window found is the answer, because it represents the shortest sequence adding up to the 'leftover'. Adding a complete repetition of the entire original array as many times as needed gets to exactly the target.

Code Implementation

def minimum_size_subarray_infinite(numbers, target):
    array_length = len(numbers)
    total_sum = sum(numbers)

    if total_sum == 0:
        return -1 if target > 0 else 0

    if target == 0:
        return 0

    repetitions = target // total_sum
    remainder = target % total_sum

    if remainder == 0:
        return array_length * repetitions

    # Find the smallest subarray that sums to the remainder.
    start_index = 0
    end_index = 0
    window_sum = 0
    min_length = float('inf')

    # Sliding window to find the minimum length subarray.
    while start_index < 2 * array_length:
        while end_index < 2 * array_length and window_sum < remainder:
            window_sum += numbers[end_index % array_length]
            end_index += 1

        # Update min_length when the window_sum is >= remainder.
        while window_sum >= remainder:
            min_length = min(min_length, end_index - start_index)
            window_sum -= numbers[start_index % array_length]
            start_index += 1

    if min_length == float('inf'):
        return -1

    # The final answer is the minimum length plus repetitions of the array.
    return min_length + repetitions * array_length

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first calculates the sum of the array in O(n) time. The sliding window approach iterates through the array with two pointers (left and right), each moving at most n steps. The while loops within the sliding window only advance the pointers; they do not cause nested iterations in the worst case. Therefore, the dominant operation is the sliding window which is O(n), making the overall time complexity O(n).

Space Complexity

O(1) – The algorithm primarily uses a sliding window technique. It calculates the sum of the array once, requiring O(1) space. The sliding window only uses a few variables to keep track of the window's start, end, current sum, and minimum length. No auxiliary data structures, such as arrays or hash maps that scale with the input array size N, are used, thus resulting in constant auxiliary space.

Edge Cases

Case	How to Handle
Empty input array (nums)	Return -1 immediately as there are no elements to form a subarray.
Target is smaller than any number in the array.	The sliding window algorithm will never find a valid subarray, resulting in returning -1 at the end.
Target is zero.	Return -1 since all numbers are positive, no subarray can sum to zero.
nums array contains only one element and target is not a multiple of that element.	The algorithm will either find a subarray that sums to target or it will not, returning -1 accordingly.
Sum of all elements in nums is greater than target, but no subarray sums to target.	The sliding window approach correctly searches for a subarray, and returns -1 when none is found
Integer overflow if target or intermediate sums become too large.	Use long data type for sums to avoid integer overflow.
Target is a very large number, requiring multiple iterations of nums to achieve the target sum.	Calculate how many complete repetitions of nums are needed, and then use the sliding window approach on the remaining target.
Target is equal to the sum of all elements in nums.	The minimum subarray size is the length of nums.