862. Shortest Subarray with Sum at Least K
Shortest Subarray with Sum at Least K (LeetCode 862) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Monotonic Queue for Max/Min subpattern.
How to solve Shortest Subarray with Sum at Least K
Shortest Subarray with Sum at Least K is a Monotonic Queue for Sliding Window Maximum/Minimum problem, part of Sliding Window. Master monotonic queue (deque) to find maximum or minimum in sliding windows efficiently in O(n) time.
Work towards the solution in these steps:
- Consider using prefix sums to transform the problem of finding subarrays with sums at least k into a problem involving differences between prefix sums.
- Think about how a sliding window approach can help identify candidate subarrays efficiently, but be mindful that the array can contain negative numbers, which complicates typical window adjustments.
- Explore the idea of maintaining a data structure that helps you quickly find the smallest prefix sum index where the difference is at least k, enabling constant-time queries as you iterate.
The reference solution runs in O(n) time and O(n) space.
The Shortest Subarray with Sum at Least K solution and editorial walks through the full approach with reference code.
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 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 <= 105
- -105 <= nums[i] <= 105
- 1 <= k <= 109
Topics and companies
Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue.
Reported in interviews at Goldman Sachs.
How to practise Shortest Subarray with Sum at Least K on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Shortest Subarray with Sum at Least K in the code editor, or read the Shortest Subarray with Sum at Least K editorial for a worked solution with its approach and complexity analysis.
Where Shortest Subarray with Sum at Least K sits in the DSA pattern sheet
Problems related to Shortest Subarray with Sum at Least K
Other problems that use the same Monotonic Queue for Max/Min and Sliding Window techniques:
- Jump Game VI — Medium, same subpattern
- Sliding Window Maximum — Hard, same subpattern
- Calculate Compressed Mean — Easy, same pattern
- Contains Duplicate II — Easy, same pattern
- Continuous Subarrays — Medium, same pattern
- Find All Anagrams in a String — Medium, same pattern
Shortest Subarray with Sum at Least K FAQ
What is the LeetCode number of Shortest Subarray with Sum at Least K?
Shortest Subarray with Sum at Least K is LeetCode problem 862, rated Hard.
What pattern is used to solve Shortest Subarray with Sum at Least K?
Shortest Subarray with Sum at Least K is a Monotonic Queue for Sliding Window Maximum/Minimum problem. It belongs to the Sliding Window pattern, in the Monotonic Queue for Max/Min subpattern.
What is the time complexity of Shortest Subarray with Sum at Least K?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Shortest Subarray with Sum at Least K?
Shortest Subarray with Sum at Least K has been reported in interviews at Goldman Sachs.