#862

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Shortest Subarray with Sum at Least K

Find the shortest subarray with a sum of at least k using binary search and sliding window techniques.

array binary search queue sliding window heap priority queue

Problem Statement

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If no such subarray exists, return -1.

A subarray is a contiguous part of an array. For example, if nums = [1,2,3] and k = 4, the shortest subarray with a sum of at least 4 would be [1, 2, 3]. In this case, the answer is 3.

Examples

Example 1

Input: nums = [1], k = 1

Output: 1

Example details omitted.

Example 2

Input: nums = [1,2], k = 4

Output: -1

Example details omitted.

Example 3

Input: nums = [2,-1,2], k = 3

Output: 3

Example details omitted.

Constraints

1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109

Solution Approach

Binary Search on Answer Space

We perform binary search to find the shortest subarray that satisfies the sum condition. The search space is between 1 and the length of the array.

Sliding Window with Prefix Sum

Using a sliding window approach combined with prefix sums allows us to efficiently calculate subarray sums without recomputing them for every possible subarray.

Monotonic Queue for Efficient Search

A monotonic queue is used to maintain the order of subarrays while ensuring that we can efficiently find the shortest subarray with the desired sum condition.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) due to the sliding window and monotonic queue operations, where n is the length of the array. The space complexity is also O(n), since we store the prefix sums and maintain a queue.

What Interviewers Usually Probe

Ensure the candidate can efficiently optimize their solution using binary search and sliding window techniques.
Look for the use of prefix sums and monotonic queues to avoid unnecessary recalculations.
Evaluate their ability to recognize when a solution needs binary search over a valid answer space.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the need for binary search over answer space, which is crucial for optimizing the solution.
Forgetting to properly handle the case where no subarray satisfies the sum condition, leading to a wrong answer.
Not managing the monotonic queue properly, which can lead to inefficiency or incorrect results.

Follow-up variants

What happens if the array contains negative numbers? How does this affect the sliding window approach?
Can this problem be solved using a brute force approach, and what are the trade-offs?
How does the time complexity change if we used a naive method instead of binary search and sliding window?

FAQ

What is the main pattern used in the Shortest Subarray with Sum at Least K problem?

The primary pattern used in this problem is binary search over the valid answer space, combined with sliding window and monotonic queue techniques.

How do you handle negative numbers in the array for this problem?

Negative numbers complicate the use of sliding windows but can be managed by ensuring the prefix sum is computed and adjusted correctly, leveraging the monotonic queue to maintain order.

Why is binary search used in this problem?

Binary search is applied to find the minimal subarray length by searching over the valid answer space, optimizing the solution's efficiency.

What happens if there’s no valid subarray with sum at least k?

If no valid subarray is found, the solution should return -1, indicating that it’s impossible to form such a subarray.

Can the solution be optimized further beyond O(n) time complexity?

The solution using binary search, sliding window, and monotonic queue achieves the optimal O(n) time complexity, and further optimizations are unlikely.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        q = deque()
        ans = inf
        for i, v in enumerate(s):
            while q and v - s[q[0]] >= k:
                ans = min(ans, i - q.popleft())
            while q and s[q[-1]] >= v:
                q.pop()
            q.append(i)
        return -1 if ans == inf else ans

Continue Practicing

#2398 maximum number of robots within budget #1425 constrained subsequence sum #1438 longest continuous subarray with absolute diff less than or equal to limit