First Negative Integer in Every Window of Size K

Problem

For every window of size k, find the first negative number in it. If a window has none, output 0 for it.

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

Python Solution

from collections import deque

def first_negative_in_window(nums, k):
    negatives = deque()
    result = []
    for i, num in enumerate(nums):
        if num < 0:
            negatives.append(i)
        if i >= k - 1:
            while negatives and negatives[0] <= i - k:
                negatives.popleft()
            result.append(nums[negatives[0]] if negatives else 0)
    return result

C++ Solution

vector<int> firstNegativeInWindow(vector<int>& nums, int k) {
    deque<int> negatives;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] < 0) negatives.push_back(i);
        if (i >= k - 1) {
            while (!negatives.empty() && negatives.front() <= i - k) negatives.pop_front();
            result.push_back(negatives.empty() ? 0 : nums[negatives.front()]);
        }
    }
    return result;
}

Java Solution

class Solution {
    public List<Integer> firstNegativeInWindow(int[] nums, int k) {
        Deque<Integer> negatives = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) negatives.addLast(i);
            if (i >= k - 1) {
                while (!negatives.isEmpty() && negatives.peekFirst() <= i - k) negatives.pollFirst();
                result.add(negatives.isEmpty() ? 0 : nums[negatives.peekFirst()]);
            }
        }
        return result;
    }
}

Complexity

Time: O(n) — each index is pushed onto the deque at most once and popped at most once. Space: O(k) — the deque holds at most the negative indices within the current window.