Code Logo

First Negative In Every Window

Published at16 Mar 2026
Created by
Easy 76 views
Like1

This one is about reading carefully and then following a clear rule. In First Negative In Every Window, you are trying to work toward the right list by following one clear idea.

Return the first negative number for every window of size k (or 0 if none). A good way to think about it is to first understand what goes in, then what rule you must follow, and finally what shape the answer should have.

For example, if the input is nums = [12,-1,-7,8,-15,30,16,28], k = 3, the answer is [-1,-1,-7,-15,-15,0]. Take the first negative in each size-3 window. Another example is nums = [1,2,3,4], k = 2, which gives [0,0,0]. No window has a negative number.

This is a friendly practice problem, but it still rewards careful reading. The key is understanding the rule clearly and then applying it carefully.

One helpful habit is to say the rule out loud in your own words before you start solving. If you can explain what counts, what changes, and what the final answer should look like, you are already much closer to the right solution.

Example Input & Output

Example 1
Input
nums = [12,-1,-7,8,-15,30,16,28], k = 3
Output
[-1,-1,-7,-15,-15,0]
Explanation

Take the first negative in each size-3 window.

Example 2
Input
nums = [1,2,3,4], k = 2
Output
[0,0,0]
Explanation

No window has a negative number.

Example 3
Input
nums = [-5,-2,-3], k = 2
Output
[-5,-2]
Explanation

Each window starts with a negative value.

Algorithm Flow

Recommendation Algorithm Flow for First Negative In Every Window

Solution Approach

This problem asks us to return, for every sliding window of size k, the first negative number in that window, or 0 if there is none. The efficient way to solve this is to keep only the indices of negative numbers in a queue, so we can quickly find the first negative inside the current window.

The key idea is a deque-style queue of negative indices. As the window slides, we remove indices that have fallen out of the window from the front, and add new negative indices at the back. The front of the queue always holds the first negative of the current window (if any).

Here is the implementation:

function first_negative_in_every_window(nums, k) {
    var n = nums.length;
    if (k <= 0 || k > n) return [];
    var q = [];
    var head = 0;
    var ans = [];
    for (var i = 0; i < n; i++) {
        if (nums[i] < 0) q.push(i);
        while (head < q.length && q[head] <= i - k) head++;
        if (i >= k - 1) ans.push(head < q.length ? nums[q[head]] : 0);
    }
    return ans;
}

We scan the array once. Whenever the current value is negative, we push its index onto the queue. Then we remove indices from the front that are no longer inside the window (those with index <= i - k). Once the window is fully formed (when i >= k - 1), the front of the queue is the first negative in the window, or we output 0 if the queue is empty.

Let us trace nums = [12,-1,-7,8,-15,30,16,28], k = 3. In the first window [12,-1,-7], the first negative is -1. In [-1,-7,8], it is -1. In [-7,8,-15], it is -7, and so on, giving [-1,-1,-7,-15,-15,0]. When no window has a negative, as in [1,2,3,4] with k = 2, the answer is all zeros.

The time complexity is O(n) because each index enters and leaves the queue once, and the space complexity is O(k).

Best Answers

java
import java.util.*;
class Solution {
    public int[] first_negative_in_every_window(int[] nums, int k) {
        int n = nums.length;
        if (k <= 0 || k > n) return new int[0];
        Deque<Integer> q = new ArrayDeque<>();
        int[] ans = new int[n - k + 1];
        int t = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) q.offerLast(i);
            while (!q.isEmpty() && q.peekFirst() <= i - k) q.pollFirst();
            if (i >= k - 1) ans[t++] = q.isEmpty() ? 0 : nums[q.peekFirst()];
        }
        return ans;
    }
}