The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subarray

A subarray is a continuous part of an array. In other-words, a subarray is an array that is inside another array.

In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays.

For example, in the array [1, 2, 3, 4], there are 10 non-empty sub-arrays, which are:

[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4]

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable. This module of the full course deals only with fixed size windows. With fixed size window, the size of the last window can be less than the size of each of the previous windows.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an array A[] and a positive integer k, find the first negative integer for each window(contiguous subarray) of size k. If a window does not contain a negative, then print 0 for that window. Use an efficient algorithm. In your solution, make sure k is less than or equal to n, the number of elements in the array.

Example:

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

Illustration:

First negative integer for each window of size 3:

[ 12, -1, -7] = -1
[-1,-7, 8] = -1
[-7, 8, -15] = -7
[8, -15, 30] = -15
[-15, 30, 16] = -15
[30, 16, 28] = 0

Brute Force (Naive) Approach in (k x n) Time

The brute-force approach was not asked for. However, it is good to know it and its limitations before embarking on the O(n) time smart approach.

In the brute force approach, there are two loops: an outer and an inner-loop. The outer loop iterates over the whole array until index n-k. The inner loop iterates over each sub-array, looking for the first negative number.

Brute-Force Program

The brute-force program is (read through the code and comments):

#include <stdio.h>
#include <stdbool.h>

void firstNegIntBrute(int A[], int n, int k) {
    //k has to be less than or equal to n
    if (!(k <= n)) 
         return;    //the whole function stops executing at this point if !(k <= n)==true, with return nothing

    for (int i = 0; i <= n - k; i++) {    //i cannot exceed n - k
        int firstNeg = 0;
        bool found = false;    //found negative within k window
        for (int j = 0; j < k; j++) {    //next k elements
            if (A[i + j] < 0) {
                printf("%i, ", A[i + j]);
                found = true;
                break;   
            }
        }
        if (found == false)
            printf("%i, ", 0);
    }        
    printf("\n");
}

int main(int argc, char **argv) {
    int A[] = {12, -1, -7, 8, -15, 30, 16, 28};
    
    int k = 3;
    int n = sizeof(A) / sizeof(A[0]);
    
    firstNegIntBrute(A, n, k);

    return 0;
}

The output is:

    -1, -1, -7, -15, -15, 0, 

The time complexity is actually O(n-k x k) for the number of inner loop iterations multiplied by the number of outer loop iterations. Since it is the maximum of this quantity that has to be chosen, the official time complexity is O(n x k). The space complexity is O(n) for the same array in the calling and called functions.

Smart Approach in O(n) Time

A O(n) time smart approach needs structures like deque or queue, which have not been studied yet in this full course. They will be studied later in this full course, When they are studied, the student is advised to come back to this tutorial and attempt the problem, with their use.

Thanks for reading.