Introduction

The First Negative Number in Every Window of Size K problem involves finding the first negative number present in every contiguous subarray (window) of size k.

Given an array arr[] 0f size n and an integer k, the task is to print the first negative number in every window of size k. If a window does not contain a negative number, print 0.

This is an important Sliding Window problem that helps in understanding window processing, queue-based optimization, and efficient traversal techniques.

Example

Input: arr[] = [2, -1, -3, 4, 5, -2, 6]k = 3
Output: [-1, -1, -3, -2, -2]
Explanation:
Window [2, -1, -3] → First Negative = -1
Window [-1, -3, 4] → First Negative = -1
Window [-3, 4, 5] → First Negative = -3
Window [4, 5, -2] → First Negative = -2
Window [5, -2, 6] → First Negative = -2
Input: arr[] = [1, 2, 3, 4]
k = 2
Output: [0, 0, 0]
Explanation:
No negative numbers are present in any window.

Constraints

   1 <= n <= 10^5       1 <= k <= n
-10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate every window of size k
  2. Traverse each window
  3. Find the first negative number

If no negative number exists in a window, print 0.

This approach is simple but repeatedly traversing every window increases time complexity.

Steps

  1. Traverse all possible windows.
  2. For every window:
    • traverse all k elements
  3. Find the first negative number.
  4. If no negative number exists:
    • print 0

Dry Run

Input Array: [2, -1, -3, 4, 5, -2, 6]k = 3
Window [2, -1, -3]:
First Negative = -1
Window [-1, -3, 4]:
First Negative = -1
Window [-3, 4, 5]:
First Negative = -3
Window [4, 5, -2]:
First Negative = -2
Window [5, -2, 6]:
First Negative = -2
Final Result:
[-1, -1, -3, -2, -2]

Brute Force Code 

Complexity Analysis

Time Complexity: O(n * k)Explanation:
Every window is traversed separately.

Space Complexity: O(1)
Explanation:
No extra data structures are used apart from result storage.

Approach 2 : Optimized Solution (Sliding Window + Queue)

Explanation

Instead of traversing every window again and again, we can use:

  1. Sliding Window Technique
  2. Queue to store negative numbers

The idea is:

  • Store indices of negative numbers
  • Remove elements that go outside the window
  • The front of the queue always gives the first negative number

This avoids repeated traversals and improves efficiency.

Steps

  1. Create a queue to store indices of negative numbers.
  2. Traverse the array.
  3. Add negative elements into the queue.
  4. Remove elements outside the current window.
  5. Once window size becomes k:
    • front of queue gives first negative number
    • if queue is empty, print 0

Dry Run

Input Array: [2, -1, -3, 4, 5, -2, 6]k = 3
Window [2, -1, -3]:
Negative elements = [-1, -3]
First Negative = -1
Slide Window:
Remove 2
Add 4
Window [-1, -3, 4]
First Negative = -1
Slide Window Again:
Remove -1
Add 5
Window [-3, 4, 5]
First Negative = -3
Slide Window Again:
Remove -3
Add -2
Window [4, 5, -2]
First Negative = -2
Final Result:
[-1, -1, -3, -2, -2]

Optimized Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element enters and leaves the queue at most once.

Space Complexity: O(k)
Explanation:
Queue stores negative elements inside the current window.
Edge Cases
  1. No negative numbers present
  2. All elements are negative
  3. Window size equals array size
  4. Window size is 1

Why This Problem is Important

This problem helps in understanding:

  1. Sliding Window Technique
  2. Queue-based optimization
  3. Window processing
  4. Efficient traversal
  5. Subarray problems

It is one of the most important Sliding Window interview problems.

Real-World Applications

Sliding Window problems are used in:

  1. Stream processing
  2. Network monitoring
  3. Sensor analysis
  4. Financial systems
  5. Real-time analytics

Common Mistakes

  1. Incorrect window boundaries
  2. Forgetting to remove old elements
  3. Storing values instead of indices
  4. Incorrect queue handling

Interview Tips

Interviewers often expect:

  1. Sliding Window optimization
  2. Proper queue usage
  3. O(n) solution

Always explain why using a queue avoids repeated traversals.

Related Questions

  1. Maximum Sum Subarray of Size K
  2. Sliding Window Maximum
  3. Longest Substring Without Repeating Characters
  4. Minimum Window Substring
  5. Longest Subarray with Sum K

Final Takeaway

The First Negative Number in Every Window of Size K problem is an important Sliding Window problem that teaches queue-based optimization and efficient window processing techniques. Understanding this problem builds a strong foundation for advanced Sliding Window and queue-related interview problem.