Sliding Window Algorithm C Program

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


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.

Tushar Soni

I am Tushar Soni, Co - Founder of CodingAlpha. I am a computer science student from India and passionate about Web Development and Programming. Connect with me on Facebook | LinkedIn | Google Plus

8 thoughts on “Sliding Window Algorithm C Program

  • September 9, 2016 at 1:20 pm

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

  • September 10, 2016 at 2:49 am

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

  • September 12, 2016 at 8:12 pm

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

  • September 13, 2016 at 1:56 am

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

  • September 13, 2016 at 10:26 am

    Thank you very much. This code is fantastic.

  • October 14, 2016 at 9:57 am

    Is this the sliding window protocol program?

    • October 16, 2016 at 12:29 am

      Yes. It is one and the same.


Join The Discussion