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
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 = −1Answer 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#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> first_negatives(const vector<int>& nums, int k) {
deque<int> negative;
vector<int> answer;
for (int r = 0; r < (int)nums.size(); ++r) {
int left = r - k + 1;
while (!negative.empty() && negative.front() < left)
negative.pop_front();
if (nums[r] < 0) negative.push_back(r);
if (left >= 0)
answer.push_back(negative.empty() ? 0 : nums[negative.front()]);
}
return answer;
}