Stacks & QueuesProblem 33 of 38
First negative integer in every window of size k
Problem Statement
Given an array of integers and a positive integer k, find the first negative integer in every window (contiguous subarray) of size k. If a window does not contain a negative integer, print 0.
Example:
Input: arr = [12, -1, -7, 8, -15, 30, 16, 28], k = 3
Window 1: [12, -1, -7] → First negative: -1
Window 2: [-1, -7, 8] → First negative: -1
Window 3: [-7, 8, -15] → First negative: -7
Window 4: [8, -15, 30] → First negative: -15
Window 5: [-15, 30, 16] → First negative: -15
Window 6: [30, 16, 28] → First negative: 0 (no negative)
Output: [-1, -1, -7, -15, -15, 0]
Approach 1: Brute Force
Intuition
For each window, scan through all k elements to find the first negative integer. Simple but inefficient as we're doing redundant work.
Algorithm
- For each window starting position i from 0 to n-k:
- Scan elements from i to i+k-1
- Find the first negative number
- If not found, output 0
java
import java.util.*;
public class FirstNegative {
public static List<Integer> firstNegativeBruteForce(int[] arr, int k) {
int n = arr.length;
List<Integer> result = new ArrayList<>();
for (int i = 0; i <= n - k; i++) {
int firstNeg = 0;
for (int j = i; j < i + k; j++) {
if (arr[j] < 0) {
firstNeg = arr[j];
break;
}
}
result.add(firstNeg);
}
return result;
}
public static void main(String[] args) {
int[] arr = {12, -1, -7, 8, -15, 30, 16, 28};
int k = 3;
List<Integer> result = firstNegativeBruteForce(arr, k);
System.out.println("First negatives: " + result);
}
}Complexity Analysis
- Time Complexity: O(n*k) - for each of (n-k+1) windows, scan k elements
- Space Complexity: O(k) - auxiliary space (excluding output)
Approach 2: Optimal (Sliding Window with Deque)
Intuition
Use a deque to store indices of negative numbers in the current window. The front of the deque always contains the index of the first negative number in the current window.
Algorithm
- Process first window: add indices of all negatives to deque
- For each subsequent window:
- Remove indices that are outside the window from front
- Add new negative element's index to back
- Front of deque (if exists) is the answer
java
import java.util.*;
public class FirstNegative {
public static List<Integer> firstNegative(int[] arr, int k) {
int n = arr.length;
List<Integer> result = new ArrayList<>();
Deque<Integer> dq = new ArrayDeque<>(); // Stores indices
// Process first window
for (int i = 0; i < k; i++) {
if (arr[i] < 0) {
dq.addLast(i);
}
}
// Process first window result
if (!dq.isEmpty()) {
result.add(arr[dq.peekFirst()]);
} else {
result.add(0);
}
// Process remaining windows
for (int i = k; i < n; i++) {
// Remove elements outside the window
while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
dq.pollFirst();
}
// Add current element if negative
if (arr[i] < 0) {
dq.addLast(i);
}
// Add result
if (!dq.isEmpty()) {
result.add(arr[dq.peekFirst()]);
} else {
result.add(0);
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {12, -1, -7, 8, -15, 30, 16, 28};
int k = 3;
List<Integer> result = firstNegative(arr, k);
System.out.println("First negatives: " + result);
}
}Complexity Analysis
- Time Complexity: O(n) - each element added and removed from deque at most once
- Space Complexity: O(k) - deque holds at most k elements
Approach 3: Using Queue (Simplified)
Intuition
We only need to track negative numbers, and we always want the first one. A simple queue suffices - add negatives, remove from front when they exit the window.
Algorithm
- Use a queue to store negative numbers (indices or values)
- For each window slide:
- If outgoing element was the front negative, remove it
- If incoming element is negative, add to queue
- Answer is front of queue (or 0 if empty)
java
import java.util.*;
public class FirstNegative {
public static List<Integer> firstNegativeQueue(int[] arr, int k) {
int n = arr.length;
List<Integer> result = new ArrayList<>();
Queue<Integer> negatives = new LinkedList<>(); // Indices
// Process first window
for (int i = 0; i < k; i++) {
if (arr[i] < 0) {
negatives.offer(i);
}
}
// Process all windows
for (int i = k; i <= n; i++) {
// Get result for current window
if (!negatives.isEmpty()) {
result.add(arr[negatives.peek()]);
} else {
result.add(0);
}
// Slide window
if (i < n) {
// Remove element going out of window
if (!negatives.isEmpty() && negatives.peek() == i - k) {
negatives.poll();
}
// Add new element if negative
if (arr[i] < 0) {
negatives.offer(i);
}
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {12, -1, -7, 8, -15, 30, 16, 28};
int k = 3;
List<Integer> result = firstNegativeQueue(arr, k);
System.out.println("First negatives: " + result);
}
}Complexity Analysis
- Time Complexity: O(n) - single pass through array
- Space Complexity: O(k) - queue holds at most k indices
Key Takeaways
- Sliding Window Pattern: Classic sliding window problem with queue
- Store Indices: Store indices instead of values for easier window management
- Queue vs Deque: Queue suffices here since we only need front element
- Similar Problems: Maximum/Minimum of all subarrays of size k
- Amortized O(1): Each element enters and exits queue at most once
- Real-world use: Stream processing, moving window analytics