Sliding Window Maximum Using Deque (C Program)
C
Medium
5 views
Problem Description
Tracking the maximum element in a sliding window of size k - Efficient approach to updating the max as the window slides?
Official Solution
#include <stdio.h>
int main() {
int arr[100], n, k;
int deque[100]; // Stores indices
int front = 0, rear = -1;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter array elements:n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter window size k: ");
scanf("%d", &k);
printf("Maximum elements in each sliding window:n");
for (int i = 0; i < n; i++) {
// Remove indices outside the window
if (front <= rear && deque[front] <= i - k) {
front++;
}
// Remove smaller elements from rear
while (front <= rear && arr[deque[rear]] <= arr[i]) {
rear--;
}
// Add current index
deque[++rear] = i;
// Print max for current window
if (i >= k - 1) {
printf("%d ", arr[deque[front]]);
}
}
return 0;
}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!