Shortest Subarray With Sum At Least K
JavaScript
Hard
3 views
Problem Description
Given array (can have negatives) and value K, find the length of shortest subarray with sum >= K. If not found, print -1.
Input Format
Line1: n K. Line2: n integers.
Output Format
One integer length.
Official Solution
const fs=require('fs');const raw=fs.readFileSync(0,'utf8').trim();if(!raw)process.exit(0);const a=raw.split(/\\s+/).map(Number);let i=0;const n=a[i++];const K=a[i++];let pref=new Array(n+1);pref[0]=0;for(let j=0;j<n;j++)pref[j+1]=pref[j]+a[i++];let dq=[];let head=0;let best=Infinity;for(let j=0;j<=n;j++){while(dq.length>head && pref[j]-pref[dq[head]]>=K){best=Math.min(best,j-dq[head]);head++;}while(dq.length>head && pref[j]<=pref[dq[dq.length-1]])dq.pop();dq.push(j);}process.stdout.write(best===Infinity?'-1':String(best));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!