manzaloros/monotonic-queue-translated.md

Created June 15, 2021 19:01

Star (0) You must be signed in to star a gist
Fork (0) You must be signed in to fork a gist

Select an option

Learn more about clone URLs
Clone this repository at <script src="https://gist.github.com/manzaloros/2ca245c40076f726bb1664e27afb0d64.js"></script>
Save manzaloros/2ca245c40076f726bb1664e27afb0d64 to your computer and use it in GitHub Desktop.

Download ZIP

Translated description of LC862. Shortest Subarray with Sum at Least K explanation

Raw

monotonic-queue-translated.md

K is a sum you want to equal or be greater than in your window.

If you make an array of prefix sums, B, then you're looking for B[left] <= B[right] - K which means that the sum of the window in your original array A has to be >= K.

Given B[right], you're looking for B[left] such that B[left] <= B[right] - K.

You need to use an increasing monotonic queue because with each new B[i], the larger elements on the left won't work as candidates to make some future element B[j] >= B[i] + K where j > i.

manzaloros/monotonic-queue-translated.md

Select an option

No results found

Select an option

No results found