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

# @lc code=start
using LeetCode

function shortest_subarray(A::Vector{Int}, K::Int)
    dq = Deque{Int}()
    prex = fill(0, length(A) + 1)
    cumsum!(@view(prex[2:end]), A)
    res = typemax(Int)
    for i in 1:length(prex)
        while !isempty(dq) && prex[i] - prex[first(dq)] ≥ K
            res = min(res, i - first(dq))
            popfirst!(dq)
        end
        while !isempty(dq) && prex[i] ≤ prex[last(dq)]
            pop!(dq)
        end
        push!(dq, i)
    end
    res == typemax(Int) ? -1 : res
end
# @lc code=end

shortest_subarray (generic function with 1 method)

This page was generated using DemoCards.jl and Literate.jl.