How do you solve Shortest Subarray with Sum at Least K on LeetCode?

Shortest Subarray with Sum at Least K (LeetCode #862) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using prefix sums allows us to quickly calculate the sum of any subarray.

What is the brute force solution for Shortest Subarray with Sum at Least K?

The brute force approach for Shortest Subarray with Sum at Least K is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible subarray to see if its sum meets or exceeds k. This is straightforward but inefficient, especially for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Shortest Subarray with Sum at Least K?

Always clarify the problem statement and constraints before jumping into coding. Think about edge cases and how your solution handles them. Practice explaining your thought process as you code, as this is often part of the interview.

What are common mistakes when solving Shortest Subarray with Sum at Least K?

Not considering edge cases where no valid subarray exists. Failing to maintain the deque properly, leading to incorrect results.

#862

Shortest Subarray with Sum at Least K

Hard

ArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic QueuePrefix SumDeque

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a prefix sum and a deque to maintain the indices of potential starting points for subarrays. This allows us to efficiently find the shortest subarray with a sum of at least k.

⚙️

Algorithm

5 steps

1Step 1: Calculate the prefix sums of the array.
2Step 2: Initialize a deque to store the indices of the prefix sums.
3Step 3: Iterate through the prefix sums, and for each sum, check if there are any previous sums that can form a valid subarray with the current sum.
4Step 4: If a valid subarray is found, update the minimum length.
5Step 5: Maintain the deque to ensure it only contains useful indices for future calculations.

solution.py16 lines

1from collections import deque
2
3def shortestSubarray(nums, k):
4    n = len(nums)
5    prefix_sum = [0] * (n + 1)
6    for i in range(n):
7        prefix_sum[i + 1] = prefix_sum[i] + nums[i]
8    min_length = float('inf')
9    dq = deque()
10    for i in range(n + 1):
11        while dq and prefix_sum[i] - prefix_sum[dq[0]] >= k:
12            min_length = min(min_length, i - dq.popleft())
13        while dq and prefix_sum[i] <= prefix_sum[dq[-1]]:
14            dq.pop()
15        dq.append(i)
16    return min_length if min_length != float('inf') else -1

ℹ

Complexity note: The time complexity is O(n) because we process each prefix sum once. The space complexity is O(n) due to the storage of the prefix sums and the deque.

1Using prefix sums allows us to quickly calculate the sum of any subarray.
2The deque helps maintain the order of indices, ensuring we can efficiently find the shortest valid subarray.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.