C Program For Sliding Window Algorithm using Array
Learn How To Implement Sliding Window Algorithm in C Programming Language. The Sliding Window Problem can be solved using Arrays, Queues and Linked Lists. We have demonstrated both the ways of finding the solution to Sliding Window Problem. The Sliding Window Problem is an implementation of Dynamic Programming Algorithm which is one of the several types of algorithms used in Programming. This problem is also famously known as Ascending Minima Algorithm.
What is Sliding Window Algorithm?
The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.
Consider the following problem:
A large buffer array array[] is given. A sliding window of size k is moving from Left to Right in Array. At any given point of time, you can only see the k elements through the window for every one right movement of the slider.
There are different types of Data Structures used in Sliding Problem Algorithm such as Heap, Double Ended Queue or Linked Lists. A Double Ended Queue would be a good data structure for Window Sliding Problem as it allows data to be inserted and deleted from both front and rear ends in a queue.
Must Read: C Program For Queue Implementation using Arrays
Sliding Window Algorithm Analysis
A brute force solution to this problem will give a runtime complexity of O(nw) which is not efficient. Implementation of Sliding Window Protocol Problem using Heap Data Structure will give a runtime complexity of O(n Log w). If a Queue is used to solve obtain solution to Sliding Window Problem, O(n) runtime complexity can be achieved.
Example of Sliding Window Problem
Buffer = {3, 2, 4, 5, 7, 4, 9, 10, 11, 13, 57}
Value of k = 4
- Partition the Buffer in blocks of size 4 (Since, k = 4). The last block may have elements less than k. The partitioned blocks will be as:
Block 1: 3, 2, 4, 5
Block 2: 7, 4, 9, 10
Block 3: 11, 13, 57 - Traverse the List from Start to End and Find the Minimum value. Reset the Minimum value to 0 after each block of 4 Elements.
Left_minimum_value[] = 3, 2, 2, 2 | 7, 4, 4, 4 | 11, 11, 11 - Traverse the List from End to Start and Find Minimum Value.
Right_minimum_value[] = 2, 2, 4, 3 | 4, 4, 9, 10 | 11, 13, 57 - Now, Minimum value at each position i in Current Window Slide can be found by the formula
sliding_minimum(i) = minimum {right_min[i], left_min[i + w – 1]}
sliding_minimum = 2, 2, 4, 4, 4, 4, 9, …
Must Read: Singly Linked List Implementation in C Programming
Method 1: C Program For Sliding Window Algorithm using Queue
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | void WindowSlidingMaximum(int Array[], int n, int size, int Buffer[]) { deque<int> Q; for(int count = 0; count < size; count++) { while(!Q.empty() && Array[count] >= Array[Q.rear()]) { Q.pop_rear(); } Q.push_rear(count); } for(int count = size; count < n; count++) { Buffer[count - size] = Array[Q.front()]; while(!Q.empty() && Array[count] >= Array[Q.rear()]) { Q.pop_rear(); } while(!Q.empty() && Q.front() <= count - size) { Q.pop_front(); } Q.push_rear(count); } Buffer[n - size] = Array[Q.front()]; } |
Method 2: C Program For Sliding Window Protocol Algorithm using Arrays
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <stdio.h> void sliding_window(int array[], int size, int k) { int j, maximum; for(int i = 0; i <= size - k; i++) { maximum = array[i]; for(j = 1; j < k; j++) { if(array[i + j] > maximum) { maximum = array[i + j]; } } printf("%d ", maximum); } } int main() { int array[10], count; int size = sizeof(array) / sizeof(array[0]); int k = 3; printf("\nEnter 10 Elements in the Buffer:\n"); for(count = 0; count < 10; count++) { scanf("%d", &array[count]); } printf("\nSliding Window Problem Solution\n"); sliding_window(array, size, k); printf("\n"); return 0; } |
Method 3: C Program For Sliding Window Algorithm using Linked List
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <stdio.h> #include <math.h> #include <stdlib.h> typedef struct node { struct node * left_node_link; struct node * right_node_link; int info; }heapNode; int leftChild(int i) { int result = 2 * i + 1; return result; } int right_child_node(int i) { int result = 2 * i + 2; return result; } void swapPtr(heapNode *a[], int count, int maximum) { heapNode *temp = a[count]; a[count] = a[maximum]; a[maximum] = temp; } void max_heapify_ptr(heapNode *a[], int count, int len) { int maximum = count; int left_node_link, right_node_link; left_node_link = leftChild(count); right_node_link = right_child_node(count); if(left_node_link <= len && a[count]->info < a[left_node_link]->info) { maximum = left_node_link; } if(right_node_link <= len && a[maximum]->info < a[right_node_link]->info) { maximum = right_node_link; } if(maximum != count) { swapPtr(a, count, maximum); max_heapify_ptr(a, maximum, len); } } void build_max_heap_ptr(heapNode *a[], int len) { int count = len / 2 + 1; while(count >= 0) { max_heapify_ptr(a, count, len); count--; } } heapNode * create_node(int info) { heapNode *node = (heapNode *)(malloc)(sizeof(heapNode)); if(node) { node->info = info; } return node; } void sliding_window(int array[], int window_size, int K, int array_len) { int i = 0, j = 0, s; heapNode *max_heap[K + 1]; int num = K; for(j = 0; j + window_size < array_len; j++) { printf("\nCurrent Window:\n"); for(s = j; s < j + window_size; s++) { printf("%d ", array[s]); } printf("\n"); for(i = 0; i < K; i++) { if(max_heap[i]) { max_heap[i]->info = array[i + j]; } else { max_heap[i] = create_node(array[i + j]); } } build_max_heap_ptr(max_heap, K - 1); for(i = K + j; i < window_size + j; i++) { heapNode * root = max_heap[0]; if(array[i] < root->info) { root->info = array[i]; max_heapify_ptr(max_heap, 0, K - 1); } } printf("K Minimum Elements in this Sliding Window\n"); for(int x = 0; x < K; x++) { printf("%d ", max_heap[x]->info); } } } int main() { int array[10]; int count, K = 3; int window_size = 4; int size = sizeof(array) / sizeof(array[0]); printf("\nEnter 10 Elements in the Buffer:\n"); for(count = 0; count < 10; count++) { scanf("%d", &array[count]); } sliding_window(array, window_size, K, size); return 0; } |
Ouput
In case you get any Compilation Errors or any doubts in this C Program To Implement Sliding Window Algorithm, let us know about it in the Comment Section below. For more information about Sliding Window Algorithm, check out Wikipedia.
I am not able to execute this Program. There is some problem with math header file. Please help
Compile this code using the command: gcc testfile.c -lm
This is amazing. The sliding window problem explanation was much needed. Understanding the code becomes so easy once the problem is understood.
I wanted the Linked List Implementation of Sliding Window Problem in C Programming! thank you so much.
What is the first Sliding Algorithm Code with Queues about? I didn’t get it.
Thank you very much. This code is fantastic.
Is this the sliding window protocol program?
Yes. It is one and the same.
Using a linked list would be a better approach here because of the amazing advantages that a linked list has to offer in comparison to static Arrays and Queues.