Shortest Subarray with Sum at Least K in C++

Suppose we have an array A. We have to find the length of the shortest, non-empty, contiguous subarray of A whose sum is at least K. If there is no such subarray, then return -1.

So, if the input is like [5,3,-2,2,1] and k = 6, then the output will be 2, as we can see (5+3) >= 6

To solve this, we will follow these steps −

• n := size of A

• ans := n + 1, j := 0, sum := 0

• Define one deque dq

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • if i > 0, then −

    • A[i] := A[i] + A[i - 1]

  • if A[i] >= K, then −

    • ans := minimum of ans and i + 1

  • while (not dq is empty and of A[i] - first element A[dq] >= K), do −

    • ans := minimum of ans and first element of i - dq

    • delete front element from dq

  • while (not dq is empty and A[i] <= last element of A[dq], do −

    • delete last element from dq

  • insert i at the end of dq

• return (if ans is same as n + 1, then -1, otherwise ans)

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int shortestSubarray(vector<int> &A, int K) {       int n = A.size();       int ans = n + 1;       int j = 0;       int sum = 0;       deque<int> dq;       for (int i = 0; i < n; i++) {          if (i > 0)          A[i] += A[i - 1];          if (A[i] >= K) {             ans = min(ans, i + 1);          }          while (!dq.empty() && A[i] - A[dq.front()] >= K) {             ans = min(ans, i - dq.front());             dq.pop_front();          }          while (!dq.empty() && A[i] <= A[dq.back()])          dq.pop_back();          dq.push_back(i);       }       return ans == n + 1 ? -1 : ans;    } }; main(){    Solution ob;    vector<int> v = {5,3,-2,2,1};    cout << (ob.shortestSubarray(v, 6)); }

Input

{5,3,-2,2,1}, 6

Output

2