Is Shortest Subarray with Sum at Least K easy or hard?

The problem is classified as Hard because negative numbers invalidate the standard sliding window technique. Solving it efficiently requires recognizing the prefix sum transformation and maintaining a monotonic deque to keep candidate starting points optimal.

Shortest Subarray with Sum at Least K Python/Java solution

Most implementations follow the same pattern: compute prefix sums, maintain a deque of candidate indices, and update the shortest length whenever the current prefix minus the front prefix is at least K. The algorithm translates directly to Python, Java, C++, or JavaScript with O(n) time complexity.

How to solve Shortest Subarray with Sum at Least K in O(n)?

Compute prefix sums so any subarray sum becomes prefix[j] - prefix[i]. Maintain a deque of indices with increasing prefix values. While iterating, remove indices from the front if the difference with the current prefix is at least K, and remove larger prefix values from the back to preserve monotonic order. This guarantees a linear scan.

What is the best approach for Shortest Subarray with Sum at Least K?

The best approach uses prefix sums combined with a monotonic deque. Prefix sums allow constant-time subarray sum queries, while the deque keeps candidate indices in increasing prefix order. This structure ensures each index is processed at most once, resulting in O(n) time complexity and O(n) space.

Is Shortest Subarray with Sum at Least K asked at Google/Amazon/Meta?

This problem pattern appears in interviews at companies like Google, Amazon, and Meta because it combines prefix sums, monotonic queues, and subarray optimization. Interviewers often use it to evaluate whether candidates can optimize beyond brute force and reason about prefix-based transformations.

What data structure is used in Shortest Subarray with Sum at Least K?

The key data structure is a deque used as a monotonic queue. It stores indices of the prefix sum array while maintaining increasing prefix values. This allows efficient removal of useless candidates and fast detection of valid subarrays.

What is the time complexity of Shortest Subarray with Sum at Least K?

The optimal solution runs in O(n) time using a prefix sum array and a monotonic deque. Each index is added and removed from the deque at most once. A naive brute force approach checks every subarray and takes O(n²) time.

Description Solution Video 21:31

862. Shortest Subarray with Sum at Least K

Hard33.3% acceptance7 companies

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 there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

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

Example 3:

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

Constraints:

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

Asked at 7 companies

Goldman Sachs PhonePe

Google Amazon Microsoft Meta Bloomberg

Topics

Array Binary Search Heap (Priority Queue)Monotonic Queue Prefix Sum Queue Sliding Window

21:31

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

862. Shortest Subarray with Sum at Least K

Asked at 7 companies

Topics

Similar problems