Sliding Window Principle/Technique

Are you tired of solving the problems using nested loops? Here is an answer for you.

What is this?

It is a paradigm that could be assumed like processing over a size of k elements in an array/string at any instant. Here k could vary to any length. It is commonly used over linear data structures such as list, arrays and so on.

When it is used?

Don’t get confused sliding window principle could always conclude any array/string problem. But surely yes it could be used as one way to bring time complexity to linear time i.e ~O(n).

Majorly when u see which specifies find min/max, unique, repeated elements in a subarray with either subarray size specified or not. This technique will surely conclude with the solution.

It is good to know such a technique when it is very easy to understand.

Let’s try and understand a small problem using this technique.

Subarray with a maximum sum which is less than or equal to given number.

For e.g Consider an array {1,9,8,10 4} we need to find a subarray with sum 25.

If we observe this array {8,10,4} is the only subarray whose sum is close to 25 and maximum.

The simple and naive solution would be to use nested loops and consider every subarray sum which is less than or equal to the given sum.

Here Sliding Window Principle comes for great help.

Try to think for a while……………..

If you knock off the algorithm, Congratulations you saved computing memory of your system.

If not, Don’t be sad, your system won’t feel sad about this small computing.

Pseudo Code

function findMaxArraySum(Array array, Sum sum) {
variable currentSum =0th element of array.
variable startOfArray =0, variable maxSum =0.
loop_array(index:1……n)
if(currentSum is less than sum){
Assign maxSum to Maximum of currentSum and maxSum
}
loop(currentSum+array[index] > sum && startOfArray<index){
currentSum = currentSum — array[startOfArray]
startOfArray= startOfArray+1
}
currentSum = currentSum+array[index]
}
Assign maxSum to Maximum of currentSum and maxSum.

Here if you have observed carefully our startOfArray, index was moving like a window over an array to maximize the given sum.

Similar problems could be solved like this.

Code to the above problem could be found @
https://github.com/GyanTech877/algorithms/blob/master/slidingwindow/MaximizeSum.java

Happy Learning :).