First negative number in every window of size k

Problem statement

Given an array of integers a, and a positive integer k, find the first negative integer for each and every window (contiguous subarray) of size k. If a window does not contain a negative integer, then print 0 for that window.

Example 1

Input: a[] = {-5, 1, 2, -6, 9}, k = 2
Output : -5 0 -6 -6

Explanation: First negative integer in every window of size 2
{-5, 1} = -5
{1, 2} = 0 (does not contain a negative integer)
{2, -6} = -6
{-6, 9} = -6

Example 2

Input : a[] = {10, -1, -5, 7, -15, 20, 18, 24} , k = 3
Output : -1 -1 -5 -15 -15 0
Explanation: First negative integer in every window of size 3
{10, -1, -5} = -1
{-1, -5, 7} = -1
{-5, 7, -15} = -5
{7, -15, 20} = -15
{-15, 20, 18} = -15
{20, 18, 24} = 0 (does not contain a negative integer)

Solution

Brute force

The naive brute force approach is to run two for loops to find the first negative number in every subarray of size k.

The outer loop runs for every index i of the array and the inner loop explores the next k elements to find the first negative number in the subarray (i to i+k).

The time complexity for this algorithm is O(n*k).

import java.util.Scanner;

class FirstNegativeNumber {
    private static int[] findFirstNegativeNumberInSubarrayOfSizeK_BruteForce(int[] a, int k) {
        int n = a.length;
        int[] firstNegativeNumbers = new int[n - k + 1];
        int idx = 0;

        for(int i = 0; i <= n-k; i++) {
            int firstNegativeNum = 0;
            for(int j = i; j < i+k; j++) {
                if(a[j] < 0) {
                    firstNegativeNum = a[j];
                    break;
                }
            }
            firstNegativeNumbers[idx++] = firstNegativeNum;
        }

        return firstNegativeNumbers;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        int k = keyboard.nextInt();

        keyboard.close();

        int[] firstNegativeNumbers = findFirstNegativeNumberInSubarrayOfSizeK_BruteForce(a, k);
        for (int i = 0; i < firstNegativeNumbers.length; i++) {
            System.out.print(firstNegativeNumbers[i] + " ");
        }
        System.out.println();
    }
}

Sliding Window

If you closely observe the way we calculate the first negative number in each subarray of size k in the brute force algorithm, you will realize that we are doing repetitive work. Let’s consider the first example:

Input: a[] = {10, -1, -5, 7, -15, 20, 18, 24}, k = 3

In the brute force approach, we first find the first negative number in the subarray {10, -1, -5}, then we move to the next subarray and find the first negative number in the subarray {-1, -5, 7}. Notice that there is an overlap between both the subarrays:

10 -1 -5
   -1 -5 7

So, we’re exploring the overlapping part ({-1, -5}) twice. Can we explore the overlapping subarray only once and reduce the repetitive work? Yes, and this hints us towards using the Sliding window pattern.

Sliding window pattern

Consider each subarray of size k as a sliding window.
Initialize two variables windowStart and windowEnd pointing to the first element of the array. These variables define the bounds of our sliding window. The initial window size is 1.
Initialize a FIFO queue that stores the negative numbers in the current window in a First-in-First-Out order.
Iterate over the array moving windowEnd forward by one element in each iteration.
- If the new element pointed by windowEnd is negative, then add it to the queue.
- If the window size hits to k (windowEnd-windowStart+1 == k), then
  - Find the first negative number in the current window by getting the first element from the queue and store it in the result.
  - If the queue is empty, that means the current window (current subarray) did not have any negative number, so store 0 in the result.
  - Now we need to slide the window ahead. So we need to discard the element at windowStart out of the window. To do this -
    - Check if the first element in the queue is equal to the element at windowStart, if yes then remove it from the queue since it is going out of the window.
    - Increment windowStart to slide the window ahead.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class FirstNegativeNumber {
    private static int[] findFirstNegativeNumberInSubarrayOfSizeK(int[] a, int k) {
        int n = a.length;
        int[] firstNegativeNumbers = new int[n - k + 1];
        int idx = 0;

        Queue<Integer> q = new LinkedList<>();

        int windowStart = 0;
        for (int windowEnd = 0; windowEnd < n; windowEnd++) {
            if (a[windowEnd] < 0) {
                q.add(a[windowEnd]);
            }

            if (windowEnd - windowStart + 1 == k) { // Calculate result and Slide the window
                if (q.isEmpty()) {
                    firstNegativeNumbers[idx++] = 0;
                } else {
                    int num = q.peek();
                    firstNegativeNumbers[idx++] = num;

                    // Remove a[windowStart] from the queue since we need to slide the window now.
                    // But only if it was added to the queue previously
                    if (num == a[windowStart]) {
                        q.remove();
                    }
                }
                windowStart++; // Slide the window ahead
            }
        }

        return firstNegativeNumbers;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = keyboard.nextInt();
        }

        int k = keyboard.nextInt();

        keyboard.close();

        int[] firstNegativeNumbers = findFirstNegativeNumberInSubarrayOfSizeK(a, k);
        for (int i = 0; i < firstNegativeNumbers.length; i++) {
            System.out.print(firstNegativeNumbers[i] + " ");
        }
        System.out.println();
    }
}

Sliding Window

Problem statement

Solution

Brute force

Sliding Window

Share on social media