1. Introduction
This is an in-depth article related to the Sliding Window Algorithm. This algorithm cuts down the necessity of nested loops by having one loop. This brings down the complexity in time.
2. Sliding Window Algorithm
2.1 Prerequisites
Java 7 or 8 is required on the Linux, windows, or mac operating systems. Maven 3.6.1 is required for building the spring and hibernate application.
2.2 Download
You can download Java 8 can be downloaded from the Oracle website. Apache Maven 3.6.1 can be downloaded from the Apache site. Spring framework’s latest releases are available from the spring website.
2.3 Setup
You can set the environment variables for JAVA_HOME and PATH. They can be set as shown below:
Setup
JAVA_HOME="/desktop/jdk1.8.0_73" export JAVA_HOME PATH=$JAVA_HOME/bin:$PATH export PATH
The environment variables for maven are set as below:
Maven Environment
JAVA_HOME=”/jboss/jdk1.8.0_73″ export M2_HOME=/users/bhagvan.kommadi/Desktop/apache-maven-3.6.1 export M2=$M2_HOME/bin export PATH=$M2:$PATH
2.4 The Idea Behind the Algorithm
The basic idea is to have one loop instead of multiple nested loops. The time complexity comes down to the order of n instead of order of square of n. Given an array, if you are asked to find the max or min of the range of elements in the array. This algorithm is used on sorted elements in a given array. The technique starts from both ends, left and right. The values of the elements for a given range are calculated from both ends. We need to remove the elements as movement happens from the left to right range.
2.5 Fixed-Size Sliding Window Example
If the length of the ranges is fixed, the algorithm is called fixed-size sliding window algorithm. You can see the implementation of the algorithm in java as shown in the code below.
Fixed Size Sliding Window
import java.util.LinkedList;
import java.util.Scanner;
public class FixedSizeSlidingWindow {
static int[] sarr;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] arr = new int[scanner.nextInt()];
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
System.out.print("arr[]: {");
for (int i = 0; i < arr.length; i++) {
System.out.print(" "+arr[i]);
}
System.out.println(" }");
int slidingWindow = scanner.nextInt();
algo(arr, slidingWindow);
}
public static void algo(int[] arr, int k) {
LinkedList linkedList = new LinkedList();
for (int i = 0; i < arr.length; i++) {
while (!linkedList.isEmpty() && arr[linkedList.getLast()] <= arr[i]) {
linkedList.removeLast();
}
while (!linkedList.isEmpty() && linkedList.getFirst() = k-1)
{
System.out.print(" "+arr[linkedList.getFirst()]);
}
}
}
}
Let us look at the output of the code when executed.
Fixed Size Sliding Window Output
(base) apples-MacBook-Air:slidingwindow bhagvan.kommadi$ javac FixedSizeSlidingWindow.java
(base) apples-MacBook-Air:slidingwindow bhagvan.kommadi$ java FixedSizeSlidingWindow
6
4
5
-3
5
1
4
arr[]: { 4 5 -3 5 1 4 }
3
5 5 5 5
2.6 Flexible-Size Sliding Window Example
Now let us look at the variable length of the ranges, the algorithm is called flexible size sliding window algorithm. If you have n elements in an array, we need to select x elements whose sum of the value is p. This is an example where a flexible size sliding window algorithm is applicable. We try to solve LeetCode’s Longest Substring without repeating characters in the code below.
Flexible Size Sliding Window
public class FlexibleSlidingWindow {
public static void main(String[] args)
{
FlexibleSlidingWindow algo = new FlexibleSlidingWindow();
int longStringLength = algo.lengthSubstring("sentence");
System.out.println(longStringLength);
}
public int lengthSubstring(String str) {
if (str == null || str.length() == 0)
return 0;
if (str.length() == 1)
return 1;
int maxSubstringLength = Integer.MIN_VALUE;
int[] characterIndex = new int[128];
int startWindowIdx = 0;
for (int endWindowIdx = 0; endWindowIdx < str.length(); endWindowIdx++) {
startWindowIdx = Math.max(startWindowIdx, characterIndex[str.charAt(endWindowIdx)]);
maxSubstringLength = Math.max(endWindowIdx - startWindowIdx + 1, maxSubstringLength);
characterIndex[str.charAt(endWindowIdx)] = endWindowIdx + 1;
}
return maxSubstringLength;
}
}
Let us look at the output of the code when executed.
Flexible Size Sliding Window Output
(base) apples-MacBook-Air:slidingwindow bhagvan.kommadi$ java FlexibleSlidingWindow 4
3. Download the Source Code
You can download the full source code of this example here: Sliding Window Algorithm in Java
The linkedList is never been added to!?