This program finds the maximum element in each sliding window of size k for a given array. The sliding window moves one element at a time from left to right, and at each step, the program outputs the maximum element within that window.

Program Explanation

The program uses a deque (double-ended queue) to keep track of indices of useful elements in the current window of size k. The deque stores indices in a way that ensures the element at the front of the deque is always the maximum of the current window.

The process can be summarized as:

1. For each element in the array:
   • Remove elements from the front of the deque that are no longer part of the current window.
   • Remove elements from the back of the deque that are smaller than the current element since they will no longer be the maximum for any future window.
   • Add the current element index to the deque.
   • If the current index is greater than or equal to k - 1, print the maximum of the current window (the element at the front of the deque).

C Program Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 10000  // Max array size

// Deque structure to store indices of array elements
struct Deque {
    int arr[MAX];
    int front, rear;
};

// Initialize deque
void initDeque(struct Deque *dq) {
    dq->front = dq->rear = -1;
}

// Check if deque is empty
int isEmpty(struct Deque *dq) {
    return dq->front == -1;
}

// Push element at the rear of deque
void pushRear(struct Deque *dq, int value) {
    if (dq->rear == MAX - 1) {
        printf("Deque overflow\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = dq->rear = 0;
    } else {
        dq->rear++;
    }
    dq->arr[dq->rear] = value;
}

// Pop element from the front of deque
void popFront(struct Deque *dq) {
    if (isEmpty(dq)) return;
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->front++;
    }
}

// Get element at the front of deque
int getFront(struct Deque *dq) {
    if (isEmpty(dq)) return -1;
    return dq->arr[dq->front];
}

// Pop element from the rear of deque
void popRear(struct Deque *dq) {
    if (isEmpty(dq)) return;
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->rear--;
    }
}

// Get element at the rear of deque
int getRear(struct Deque *dq) {
    if (isEmpty(dq)) return -1;
    return dq->arr[dq->rear];
}

// Main function to find the maximum in each sliding window of size k
void findMaxInSlidingWindow(int arr[], int n, int k) {
    struct Deque dq;
    initDeque(&dq);

    for (int i = 0; i < n; i++) {
        // Remove elements not part of the current window
        if (!isEmpty(&dq) && getFront(&dq) <= i - k) {
            popFront(&dq);
        }

        // Remove elements from the rear of the deque that are smaller than current element
        while (!isEmpty(&dq) && arr[getRear(&dq)] <= arr[i]) { popRear(&dq); } // Add current element's index at the rear of the deque pushRear(&dq, i); // Print the maximum element of the window if (i >= k - 1) {
            printf("%d ", arr[getFront(&dq)]);
        }
    }
    printf("\n");
}

// Main driver function
int main() {
    int arr[] = {12, 1, 78, 90, 57, 89, 56};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    printf("Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\nSliding window maximums of size %d:\n", k);
    findMaxInSlidingWindow(arr, n, k);

    return 0;
}
    

Code Explanation

1. Deque Implementation: We implement a deque to store the indices of the elements in the array. The deque is a double-ended queue, which allows us to efficiently add and remove elements from both the front and the rear. This helps in keeping track of the maximum element of the sliding window.

2. Function findMaxInSlidingWindow: This function processes the array to find the maximum element in every window of size k. It uses the deque to store indices and updates the window by adding or removing indices based on the current sliding window.

3. Main Driver Function: The driver function defines an array and a window size k. It calls the function findMaxInSlidingWindow to compute the result.

Sample Output

Array: 12 1 78 90 57 89 56 
Sliding window maximums of size 3:
78 90 90 90 89 
    

Conclusion

This program effectively demonstrates the concept of finding the maximum value in each sliding window of size k using a deque. The use of a deque ensures that the program runs efficiently, avoiding the overhead of recalculating maximums from scratch for every new window.