Scale Engineer

Shortest Subarray with Sum at Least K

Hard
#0816Time: O(n^2), where n is the number of elements in `nums`. The prefix sum calculation takes O(n), but the nested loops to check every subarray dominate the runtime.Space: O(n) to store the prefix sum array.
Patterns
Sliding WindowPrefix Sum
Algorithms
Binary Search
Data structures
ArrayHeap (Priority Queue)QueueMonotonic Queue

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach involves pre-calculating prefix sums to quickly find the sum of any subarray. We then iterate through all possible start and end points of a subarray, check if its sum is at least k, and keep track of the minimum length found.

Algorithm

  1. Create a prefix sum array prefix of size n + 1. Use long to prevent integer overflow, as sums can be large.
  2. Populate the prefix array: prefix[i+1] = prefix[i] + nums[i] for i from 0 to n-1.
  3. Initialize minLength = n + 1 to store the result.
  4. Iterate with a start index i from 0 to n-1.
  5. Inside this loop, iterate with an end index j from i to n-1.
  6. Calculate the subarray sum: sum = prefix[j+1] - prefix[i].
  7. If sum >= k, update minLength = Math.min(minLength, j - i + 1).
  8. After the loops, if minLength is still n + 1, return -1. Otherwise, return minLength.

Walkthrough

This method improves upon a naive brute-force solution by optimizing the sum calculation for each subarray.

  1. Prefix Sum Calculation: First, we create a prefix sum array, prefix, of size n + 1, where n is the length of nums. prefix[i] stores the sum of elements from nums[0] to nums[i-1]. prefix[0] is initialized to 0. This allows us to calculate the sum of any subarray nums[i...j] in constant time using the formula prefix[j+1] - prefix[i]. This pre-computation step takes O(n) time.

  2. Iterating Subarrays: After computing the prefix sums, we use two nested loops to examine every possible non-empty subarray. The outer loop selects a starting index i from 0 to n-1, and the inner loop selects an ending index j from i to n-1.

  3. Checking Condition: For each subarray defined by (i, j), we calculate its sum prefix[j+1] - prefix[i]. If this sum is greater than or equal to k, we have found a valid subarray. We then update our minimum length found so far with min(minLength, j - i + 1).

  4. Result: We initialize minLength to a value larger than n (e.g., n + 1). If minLength remains this value after checking all subarrays, it means no solution exists, and we return -1. Otherwise, we return the final minLength.

class Solution {    public int shortestSubarray(int[] nums, int k) {        int n = nums.length;        long[] prefix = new long[n + 1];        for (int i = 0; i < n; i++) {            prefix[i + 1] = prefix[i] + nums[i];        }         int minLength = n + 1;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                long sum = prefix[j + 1] - prefix[i];                if (sum >= k) {                    minLength = Math.min(minLength, j - i + 1);                }            }        }         return minLength == n + 1 ? -1 : minLength;    }}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. The prefix sum calculation takes O(n), but the nested loops to check every subarray dominate the runtime.

Space

O(n) to store the prefix sum array.

Trade-offs

Pros

  • More efficient than a naive O(n^3) brute-force approach.

  • Relatively easy to understand the logic based on prefix sums.

Cons

  • The O(n^2) time complexity is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error.

Solutions

class Solution {public  int shortestSubarray(int[] nums, int k) {    int n = nums.length;    long[] s = new long[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + nums[i];    }    Deque<Integer> q = new ArrayDeque<>();    int ans = n + 1;    for (int i = 0; i <= n; ++i) {      while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {        ans = Math.min(ans, i - q.poll());      }      while (!q.isEmpty() && s[q.peekLast()] >= s[i]) {        q.pollLast();      }      q.offer(i);    }    return ans > n ? -1 : ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem