Shortest subarray with sum at least k

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

32.6% acceptance

Feb 22, 2026

5168

143

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/*
 * 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
 */

use std::collections::VecDeque;
impl Solution {
  pub fn shortest_subarray(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as i64;
    let n = nums.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] + nums[i] as i64; }
    let mut ans = i32::MAX;
    let mut deque: VecDeque<usize> = VecDeque::new();
    for i in 0..=n {
      while !deque.is_empty() && prefix[i] - prefix[*deque.front().unwrap()] >= k {
        ans = ans.min((i - deque.pop_front().unwrap()) as i32);
      }
      while !deque.is_empty() && prefix[i] <= prefix[*deque.back().unwrap()] {
        deque.pop_back();
      }
      deque.push_back(i);
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}