Sliding Window Algorithm C Program

By | September 9, 2016

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

  1. 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
  2. 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
  3. 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
  4. 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

 

Method 2: C Program For Sliding Window Protocol Algorithm using Arrays

Method 3: C Program For Sliding Window Algorithm using Linked List

Ouput

Sliding Window Algorithm in C Programming using Array and Linked List

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.

9 thoughts on “Sliding Window Algorithm C Program

  1. Akash Goel

    I am not able to execute this Program. There is some problem with math header file. Please help

    Reply
  2. Sumeet Singh

    This is amazing. The sliding window problem explanation was much needed. Understanding the code becomes so easy once the problem is understood.

    Reply
  3. Vikrant Thakur

    I wanted the Linked List Implementation of Sliding Window Problem in C Programming! thank you so much.

    Reply
  4. Akshay Pawar

    What is the first Sliding Algorithm Code with Queues about? I didn’t get it.

    Reply
  5. Vishal Upadhyay

    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.

    Reply

Let's Discuss