Problem

Given an integer array a and an integer window size k, return the first negative integer in every contiguous subarray (window) of size k. If a window contains no negative numbers, return 0 for that window.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: a = [-5, 1, 2, -6, 9], k = 2
Output: [-5, 0, -6, -6]

Explanation:
Window [-5, 1] -> -5
Window [1, 2]  -> 0 (no negative)
Window [2, -6] -> -6
Window [-6, 9] -> -6

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: a = [10, -1, -5, 7, -15, 20, 18, 24], k = 3
Output: [-1, -1, -5, -15, -15, 0]

Explanation: sliding windows of size 3
[10, -1, -5] -> -1
[-1, -5, 7]  -> -1
[-5, 7, -15] -> -5
[7, -15, 20] -> -15
[-15, 20, 18]-> -15
[20, 18, 24] -> 0 (no negative)

Constraints and edge cases

  • 1 <= k <= len(a)
  • If k == 1, the answer is each element if negative otherwise 0.
  • If k > len(a) return an empty list (or no windows).

Solution

Method 1 - Brute Force

Intuition

For each starting index i, scan the next k elements to find the first negative number. This directly follows the problem statement but repeats work across overlapping windows.

Approach

  • For every i from 0 to n-k:
    • Inspect elements a[i] through a[i+k-1].
    • As soon as a negative element is found, append it to ans and stop scanning this window.
    • If no negative is found append 0.
  • Handle edge cases: if k > n return empty ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
 public:
  vector<long long> firstNegativeInWindow(const vector<long long>& a, int k) {
    int n = a.size();
    vector<long long> ans;
    if (k > n) return ans;
    for (int i = 0; i <= n - k; ++i) {
      long long first = 0;
      for (int j = i; j < i + k; ++j) {
        if (a[j] < 0) { first = a[j]; break; }
      }
      ans.push_back(first);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

// firstNegativeInWindow returns first negative number for each window of size k.
func firstNegativeInWindow(a []int, k int) []int {
  n := len(a)
  if k > n { return []int{} }
  ans := make([]int, 0, n-k+1)
  for i := 0; i <= n-k; i++ {
    first := 0
    for j := i; j < i+k; j++ {
      if a[j] < 0 { first = a[j]; break }
    }
    ans = append(ans, first)
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public long[] firstNegativeInWindow(long[] a, int k) {
        int n = a.length;
        if (k > n) return new long[0];
        long[] ans = new long[n - k + 1];
        int idx = 0;
        for (int i = 0; i <= n - k; i++) {
            long first = 0;
            for (int j = i; j < i + k; j++) {
                if (a[j] < 0) { first = a[j]; break; }
            }
            ans[idx++] = first;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def first_negative_in_window(self, a: list[int], k: int) -> list[int]:
        n = len(a)
        if k > n:
            return []
        ans: list[int] = []
        for i in range(0, n - k + 1):
            first = 0
            for j in range(i, i + k):
                if a[j] < 0:
                    first = a[j]
                    break
            ans.append(first)
        return ans

Complexity

  • ⏰ Time complexity: O(n*k), because for each of the O(n) window starts we may scan up to k elements.
  • 🧺 Space complexity: O(n-k+1) for the output ans (ignoring input).

Method 2 - Sliding Window (Queue of indices)

Intuition

Windows overlap heavily; we can avoid re-scanning the overlapping portion by maintaining the negative elements seen so far in a FIFO structure. Store indices of negative elements so we can efficiently check whether the stored negative is still inside the current window.

Approach

  • Initialize an empty queue q to hold indices of negative elements in the current window.
  • Iterate windowEnd from 0 to n-1:
    • If a[windowEnd] < 0, append windowEnd to q.
    • When window size reaches k (i.e., windowEnd - windowStart + 1 == k):
      • If q is empty, append 0 to ans.
      • Otherwise, the first negative is a[q[0]], append it to ans.
      • Before sliding the window, if q[0] == windowStart, pop it from q because it will leave the window.
      • Increment windowStart to slide.
  • Edge cases: if k > n return empty list; if no negatives ever appear append zeros accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <deque>

class Solution {
 public:
  vector<int> firstNegativeInWindow(const vector<int>& a, int k) {
    int n = a.size();
    vector<int> ans;
    if (k > n) return ans;
    deque<int> q; // store indices of negative numbers
    int start = 0;
    for (int end = 0; end < n; ++end) {
      if (a[end] < 0) q.push_back(end);
      if (end - start + 1 == k) {
        if (q.empty()) ans.push_back(0);
        else ans.push_back(a[q.front()]);
        if (!q.empty() && q.front() == start) q.pop_front();
        ++start;
      }
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

package main

// firstNegativeInWindow returns the first negative element in each window of size k.
func firstNegativeInWindow(a []int, k int) []int {
  n := len(a)
  if k > n { return []int{} }
  ans := make([]int, 0, n-k+1)
  q := make([]int, 0) // indices of negative numbers
  start := 0
  for end := 0; end < n; end++ {
    if a[end] < 0 { q = append(q, end) }
    if end-start+1 == k {
      if len(q) == 0 { ans = append(ans, 0) }
      else { ans = append(ans, a[q[0]]) }
      if len(q) > 0 && q[0] == start { q = q[1:] }
      start++
    }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] firstNegativeInWindow(int[] a, int k) {
        int n = a.length;
        if (k > n) return new int[0];
        int[] ans = new int[n - k + 1];
        Deque<Integer> q = new ArrayDeque<>(); // indices of negatives
        int start = 0, idx = 0;
        for (int end = 0; end < n; end++) {
            if (a[end] < 0) q.addLast(end);
            if (end - start + 1 == k) {
                if (q.isEmpty()) ans[idx++] = 0;
                else ans[idx++] = a[q.peekFirst()];
                if (!q.isEmpty() && q.peekFirst() == start) q.removeFirst();
                start++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from collections import deque

class Solution:
    def first_negative_in_window(self, a: list[int], k: int) -> list[int]:
        n = len(a)
        if k > n:
            return []
        ans: list[int] = []
        q: deque[int] = deque()  # indices of negative numbers
        start = 0
        for end in range(n):
            if a[end] < 0:
                q.append(end)
            if end - start + 1 == k:
                if not q:
                    ans.append(0)
                else:
                    ans.append(a[q[0]])
                if q and q[0] == start:
                    q.popleft()
                start += 1
        return ans

Complexity

  • ⏰ Time complexity: O(n), because each element is added and removed from the queue at most once.
  • 🧺 Space complexity: O(k) in the worst case (queue can hold at most k indices), plus O(n-k+1) for the output ans.