862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray ofAwith sum at leastK.

If there is no non-empty subarray with sum at leastK, 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

Thoughts:

1. Using Deque + keeping increasing order: only larger index in the queue can have larger sum value. We use cumulative sum and priority queue that maintains minimal value within the window of a given length. We then iterate over all possible ends of windows and check, what is the maximal possible sum across all windows of length l <= L that end at this element.

2. Segment Tree:

3. TreeMap.submap

4. Binary Search

https://buptwc.github.io/2018/07/02/Leetcode-862-Shortest-Subarray-with-Sum-at-Least-K/

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C++JavaPython-O(N)-Using-Deque

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/151169/my-solution-O(nlgn)-use-segment-tree

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/144291/Java-TreeMap.submap-Solution

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143828/Java-binary-search-O(NlogN\

Code: Deque. O(n)

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int N = A.size(), res = N + 1;
        vector<int> S (N + 1, 0);
        for(int i = 0; i < N; i++) S[i + 1] = S[i] + A[i];
        deque<int> d;
        for(int i = 0; i < N + 1; i++){
            while(d.size() > 0 && S[i] - S[d.front()] >= K){
                res = min(res, i - d.front()); 
                d.pop_front();
            }
            // keep the INCREASING order to keep the optimal result (index larger should have larger(equal) value in the queue)
            while(d.size() > 0 && S[i] <= S[d.back()]){
                d.pop_back();
            }
            d.push_back(i);
        }

        return res == N + 1? -1: res;
    }
};

Code: Python

class Solution:
    def shortestSubarray(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """

        dp = [0] * (len(A) + 1)

        for i in range(1, len(dp)):
            dp[i] = dp[i - 1] + A[i - 1]

        res = len(A) + 1
        #
        Q = collections.deque()

        for i in range(len(dp)):
            while Q and dp[i] - dp[Q[0]] >= K:
                res = min(res, i - Q.popleft())
            while Q and dp[i] < dp[Q[-1]]:
                Q.pop() # pop right
            Q.append(i)

        return res if res != len(A)+1 else -1

Code: Java

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int N = A.length, res = N + 1;
        int[] S  = new int[N+ 1];
        for(int i = 0; i < N; i++) S[i + 1] = S[i] + A[i];
        Deque<Integer> d = new LinkedList();
        for(int i = 0; i < N + 1; i++){
            while(d.size() > 0 && S[i] - S[d.peekFirst()] >= K){
                res = Math.min(res, i - d.pollFirst()); 
            }
            // keep the INCREASING order to keep the optimal result (index larger should have larger(equal) value in the queue)
            while(d.size() > 0 && S[i] <= S[d.peekLast()]){
                d.pollLast();
            }
            d.offerLast(i);
        }

        return res == N + 1? -1: res;
    }
}

Code: Segment Tree:

class Solution {
    struct node{
        int s,e;
        long long m; //min
        node *left, *right;
        node(int s, int e, long long m): s(s), e(e), m(m), left(0), right(0){}
        ~node(){
            if(left) delete left;
            if(right) delete right;
        }
    };

    node* build(vector<long long> &sums, int l, int r){
        node *root = new node(l,r, sums[l]);
        if(l == r) return root;
        root->left = build(A, l, (l+r)/2);
        root->right = build(A, (l + r)/2 + 1, r);
        root-> m = min(root->left->m, root->right-> m);

        return root;
    }

    int query(node* root, int l, int r, int k){
        if(l > r) return -1;
      //It is possible to make such a check in linear time.
      //We use cumulative sum and priority queue that maintains minimal value within 
      //the window of a given length. We then iterate over all possible ends of windows and check, 
      //what is the maximal possible sum across all windows of lenght <= L that end at this element.      
        if(root -> s > r || root-> e < l || root-> m >k) return -1;
        if(root-> s == root ->e && root->m <=k) return root->s;
        int rr = query(root-> right, l, r, k);
        if(rr == -1) return query(root->left, l, r, k);

        return rr;
    }
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size();
        vector<long long> sum(n);
        sum[0] = A[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + A[i];
        node * root = build(sum, 0, n - 1);
        int ans= n +1;
        for (int i = 0; i < n; i++){
            if(sum[i] >=K) ans = min(ans, i + 1);
            int p = query(root, 0, i - 1, sum[i] -K); // find sum[p]
            if(p!= -1) ans = min(ans, i- p);
        }
        return ans == n+ 1? -1: ans;
    }
};

Code: Java subMap

   public int shortestSubarray(int[] A, int K) {
        if (A.length == 0) return -1;
        TreeMap<Long, Integer> map = new TreeMap();
        map.put(0L, -1); // pay attention to the initial state
        long cumSum = 0; // sum of range[0-->i]
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < A.length; i++) {
            // get cur cumSum
            cumSum += A[i];
            // find all candidates and update res (firstKey() will throw exception if map is empty)
            Long lowestKey = map.firstKey(), floorKey = map.floorKey(cumSum - K);
            if (lowestKey != null && floorKey != null) {
                Map<Long, Integer> subMap = new HashMap(map.subMap(lowestKey, true, floorKey, true));
                for (Long key: subMap.keySet()) {
                    int curLen = i - subMap.get(key);
                    if (minLen > curLen) minLen = curLen;  // update res
                    else map.remove(key);                  // prune bad candidate
                }
            }
            // put new cumSum to tree
            map.put(cumSum, i);
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }

Code: Java Binary Search

class Solution {
    public int shortestSubarray(int[] A, int K) {
        int N = A.length;

        // Compute cumulative sum
        int[] cumSum = new int[N];
        for (int i = 0; i < N; ++i) {
            cumSum[i] = i > 0 ? cumSum[i-1] + A[i] : A[i];
        }

        if (!existsSolution(cumSum, K, N)) return -1;

        // Binary search over all possible lengths
        int l = 1, r = N;
        while (l < r) {
            int m = l + (r-l) / 2;
            if (existsSolution(cumSum, K, m)) {
                r = m;
            } else {
                l = m+1;
            }
        }

        return l;
    }

    boolean existsSolution(int[] cumSum, int K, int len) {
        // Priority queue that maintains minimal value within the window of size 'len'
        PriorityQueue<VI> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        pq.add(new VI(0, -1));

        for (int i = 0; i < cumSum.length; ++i) {
            // Clean up minimal elements that are outside of the window
            while (!pq.isEmpty() && pq.peek().pos < i-len) {
                pq.poll();
            }
            int windowMin = !pq.isEmpty() ? pq.peek().val : 0;
            if (cumSum[i] - windowMin >= K) {
                return true;
            } 
            pq.add(new VI(cumSum[i], i));
        }

        return false;
    }

    public static class VI {
        public int val, pos;

        public VI(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
    } 
}