First negative integer in every window of size k

The problem, simply

You get an array and a number k. Look at every block of k numbers in a row: the first k, then shift one step right, and so on. For each block, give the first negative number in it, reading left to right. If a block has no negative number, give 0.

There are n - k + 1 blocks, so the answer has that many numbers.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each window start i, look at the k numbers from i and stop at the first negative.

1. For i from 0 to n - k, set the answer to 0.
2. Scan j from i to i + k - 1. At the first arr[j] < 0, take it and stop.

class Solution {
    public int[] firstNegative(int[] arr, int k) {
        int n = arr.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            for (int j = i; j < i + k; j++) {
                if (arr[j] < 0) {          // first negative wins
                    ans[i] = arr[j];
                    break;
                }
            }                              // stays 0 if none was found
        }
        return ans;
    }
}

How long it takes: up to k checks for each of about n windows, O(n * k). Extra room: O(1) besides the answer.

Way 2: the clever way

Keep a waiting line, a queue, of the indices of negative numbers, in the order they appear.

1. Move the right end r from 0 to n - 1.
2. If arr[r] is negative, add r to the back of the line.
3. Once the window is full (r >= k - 1), its left end is l = r - k + 1. Remove indices smaller than l from the front, since they slid out.
4. The answer for this window is arr[front] if the line is not empty, else 0.

The line keeps left to right order, so its front is always the first negative in the window.

class Solution {
    public int[] firstNegative(int[] arr, int k) {
        int n = arr.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> line = new ArrayDeque<>();        // indices of negatives
        for (int r = 0; r < n; r++) {
            if (arr[r] < 0) line.addLast(r);             // join at the back
            int l = r - k + 1;                           // left end of the window
            if (l < 0) continue;                         // window not full yet
            while (!line.isEmpty() && line.peekFirst() < l) {
                line.pollFirst();                        // slid out on the left
            }
            ans[l] = line.isEmpty() ? 0 : arr[line.peekFirst()];
        }
        return ans;
    }
}

How long it takes: each index joins the line at most once and leaves at most once, O(n). Extra room: the line only holds indices inside the window, at most k, so O(k).

Watch out for

• Remove from the front only while the front index is less than l. An if instead of while works here because the window moves one step at a time, but while is the safe habit.
• The answer array has n - k + 1 entries. Write to ans[l], not ans[r].
• If k > n, there are no windows. Check that first to avoid a negative array size.
• "First" means leftmost, not smallest. Do not use a heap or a minimum here.

What interviewers ask next

• Can you do it in O(1) extra room? Yes. Keep one index p. For each window, set p = max(p, l), then move p right while p <= r and arr[p] is not negative. If p <= r, the answer is arr[p], else 0. p never moves back, so it is still O(n).
• Maximum of every window of size k. Use a deque that keeps values in decreasing order, and drop smaller values from the back. That is the "sliding window maximum" pattern.
• Count the negatives in every window instead. Keep a running count: add one when a negative enters, take one away when it leaves.
• What if the numbers arrive as a stream and you cannot look back? This method already works on a stream, because it only remembers the indices in the line.

Remember this

Grown-up words: the picture frame is a sliding window, the line of burnt cookies is a queue (or a deque used as one), and "each index joins once and leaves once" is why the whole thing is O(n).