Skip to content

Instantly share code, notes, and snippets.

@manzaloros

manzaloros/monotonic-queue-translated.md

Created June 15, 2021 19:01
Show Gist options
  • Save manzaloros/2ca245c40076f726bb1664e27afb0d64 to your computer and use it in GitHub Desktop.
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment