862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

 

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

 

Note:

  1. 1 <= A.length <= 50000
  2. -10 ^ 5 <= A[i] <= 10 ^ 5
  3. 1 <= K <= 10 ^ 9

Rust Solution

struct Solution;

use std::collections::VecDeque;

impl Solution {
    fn shortest_subarray(a: Vec<i32>, k: i32) -> i32 {
        let n = a.len();
        let mut queue: VecDeque<usize> = VecDeque::new();
        let mut prefix = vec![0; n + 1];
        queue.push_back(0);
        let mut res = std::usize::MAX;
        for i in 0..n {
            prefix[i + 1] = prefix[i] + a[i];
            while let Some(&j) = queue.front() {
                if prefix[i + 1] - prefix[j] >= k {
                    res = res.min(i + 1 - j);
                    queue.pop_front();
                } else {
                    break;
                }
            }
            while let Some(&j) = queue.back() {
                if prefix[i + 1] <= prefix[j] {
                    queue.pop_back();
                } else {
                    break;
                }
            }
            queue.push_back(i + 1);
        }
        if res == std::usize::MAX {
            -1
        } else {
            res as i32
        }
    }
}

#[test]
fn test() {
    let a = vec![1];
    let k = 1;
    let res = 1;
    assert_eq!(Solution::shortest_subarray(a, k), res);
    let a = vec![1, 2];
    let k = 4;
    let res = -1;
    assert_eq!(Solution::shortest_subarray(a, k), res);
    let a = vec![2, -1, 2];
    let k = 3;
    let res = 3;
    assert_eq!(Solution::shortest_subarray(a, k), res);
}

Having problems with this solution? Click here to submit an issue on github.