The first negative number in every window

Given a list of numbers and a size k, report the first negative number in each window of k consecutive numbers. If a window has no negative number, report 0 for it.

Worked example#

For [12, -1, -7, 8, -15, 30, 16, 28] with k = 3:

So the answer is [-1, -1, -7, -15, -15, 0].

The idea#

Scanning each window for its first negative is n times k again. The thing to notice is what carries over: the first negative of the previous window is usually still the first negative of this one.

So keep a queue of the positions of negative numbers currently inside the window, in the order they appear. Then:

• when the window moves right, any new number that is negative joins the back of the queue;
• anything at the front that has now fallen out of the window on the left is removed;
• the front of the queue, if there is one, is the answer.

A queue rather than a stack, because you want the earliest negative still in range, not the most recent. That is the whole reason the structure differs from the monotonic stack problems, and it is worth sitting with: the question decides the end you take things from.

Every position joins the queue at most once and leaves at most once, so this is one pass.

Constraints#

• 1 <= k <= n <= 100000
• -1000000 <= nums[i] <= 1000000