862. Shortest Subarray with Sum at Least K (contains negative numbers)
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 <= A.length <= 50000-10 ^ 5 <= A[i] <= 10 ^ 51 <= K <= 10 ^ 9
Thoughts:
- 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.
- Segment Tree:
- TreeMap.submap
- Binary Search
https://buptwc.github.io/2018/07/02/Leetcode-862-Shortest-Subarray-with-Sum-at-Least-K/
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;
}
}
}