Workspace

Problem workspace

3 day streakD

First Negative in Every Window

EasySliding WindowFixed windows

The challenge

Return the first negative number in each consecutive window of k elements. Return 0 for a window with no negative numbers.

Use 1 ≤ k ≤ n. Values may be negative. Indices are zero-based.

Example

[12, −1, −7, 8, −15, 30, 16, 28], k = 3 → [−1, −1, −7, −15, −15, 0].

Use the walkthrough below to inspect the input and each state change.

See First negative, step by step

Expand, shrink, and inspect the window state.

8 elements · zero-based indicesk = 3
Sliding window over 8 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1120-11-7283-154305166287
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 16

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

[]
View exact input

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

Current window is empty.

Put it into code

Store only the indices of negative numbers, in input order. The first unexpired index identifies the answer.

Indices are zero-based. C++ uses C++17 or later.

from collections import deque


def first_negatives(nums, k):
    negative = deque()  # Indices in increasing order.
    answer = []
    for right, value in enumerate(nums):
        left = right - k + 1
        while negative and negative[0] < left:
            negative.popleft()
        if value < 0:
            negative.append(right)
        if left >= 0:
            answer.append(nums[negative[0]] if negative else 0)
    return answer

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap