I been reading, watching videos and experimenting with the Universal Windows Platform (UWP) and cpp/WinRT most of the day. On this final block I decided to take a break and make a post in my blog. I want to get some software done before the end of the day this Wednesday. Will let you know if I meet the deadline.
I noticed in my Gmail that JAVAAID had posted a video on YouTube titled “Sliding Windows Technique”. It called my attention because the Rabin-Karp algorithm is based on a sliding window technique. In the past few months I wrote a post on the subject and named it “Rabin-Karp Algorithm” (not too creative on my part).
I just took a break after my fourth 2-hour block of the day. I wake up at 05:00 AM so I can get on average 10 hours per working day and 4 hours on weekend days. Mondays is garbage collection day and this week we had regular garbage and recycling. Earlier today I brought in the garbage bin. A few 
minutes ago I went out to bring in the recycle bin. My neighbors to the right were stringing holiday light on their trees. The current temperature is about 43 degrees Fahrenheit but the wind is blowing. Combined the wind chill is 35 degrees. Both are wearing hats, gloves, jackets and seem to be quite cold. I guess they do have the holiday spirit.
Enough chitchat and let’s get to the subject at hand. The idea is to compute a value using a set of contiguous entries in an array. Then move the window in a specific direction updating the running value with the first and last elements in the window.
In this case the idea is to get the largest sum of a set of consecutive numbers in an integer array.
6 2 1 5 1 3 2 3 main <<< n: 6 main <<< arr: [2 1 5 1 3 2] main <<< k: 3 slidingWindow <<< maxSum: 8 slidingWindow <<< i: 0 j: 3 sum: 7 maxSum: 8 slidingWindow <<< i: 1 j: 4 sum: 9 maxSum: 9 slidingWindow <<< i: 2 j: 5 sum: 6 maxSum: 9 main <<< maxSum: 9 8 1 9 -1 -2 7 3 -1 2 4 main <<< n: 8 main <<< arr: [1 9 -1 -2 7 3 -1 2] main <<< k: 4 slidingWindow <<< maxSum: 7 slidingWindow <<< i: 0 j: 4 sum: 13 maxSum: 13 slidingWindow <<< i: 1 j: 5 sum: 7 maxSum: 13 slidingWindow <<< i: 2 j: 6 sum: 7 maxSum: 13 slidingWindow <<< i: 3 j: 7 sum: 11 maxSum: 13 main <<< maxSum: 13
I have captured two runs of the solution using the same sets of values (but in different order) used by JAVAAID. The reason for this being is that I wrote my code and then I watched the rest of the video once I had enough information to craft an approach.
The first number holds the number of entries in the array of integers that follows. The second line holds the values for the array. The third line contains the number of elements that need to be process per step. Put in other words, given an array of integers determine the value of the largest sum of three consecutive numbers.
The first set adds up to (2 + 1 + 5 == 8) eight. The second to 7, the third to 9 and the fourth and last to 6. The expected result is nine. It seems that the method returns the proper answer.
We repeat the test with a different set which also includes negative numbers. It seems that the expected result is 13 and that is what the algorithm returns.
There is a brute force approach which I skipped. If interested, you can see the implementation in the YouTube video by JAVAAID.
I am on a roll using Visual Studio Code. Interesting enough, last week I installed a licensed version of Visual Studio 2019 Enterprise edition in one of my development machines. I needed that version to get past an issue that I encountered while using Visual Studio 2017 Enterprise edition. Long story, but when you are working with tools that are evolving, you tend to encounter issues with things that are supposed to work on a new version but have not been implemented in an older one.
I am working with C++ on the project I mentioned earlier in this post, but for this post I went with Java and I used the Visual Studio Code IDE.
C:\>cd C:\Users\John\workspace6
C:\Users\John\workspace6>mkdir SlidingWindow
C:\Users\John\workspace6>dir
Volume in drive C is OS
Volume Serial Number is 26E8-87B0
Directory of C:\Users\John\workspace6
11/25/2019 12:56 PM <DIR> .
11/25/2019 12:56 PM <DIR> ..
10/23/2019 11:06 AM <DIR> .metadata
05/11/2019 07:13 AM <DIR> .recommenders
05/22/2019 08:05 AM <DIR> 10of50
05/11/2019 07:07 AM <DIR> AbsolutePermutation
10/17/2019 06:47 AM <DIR> AddWithoutPlus
06/12/2019 10:40 AM <DIR> ArraysLeftRotation
10/19/2019 06:50 AM <DIR> BabyNames
07/22/2019 02:09 PM <DIR> Boggle
05/13/2019 02:11 PM <DIR> Bomberman
10/16/2019 01:05 PM <DIR> BreakingRecords
09/14/2019 05:52 AM <DIR> BSTOperations
11/20/2019 04:12 PM <DIR> CatsAndMouse
10/09/2019 01:57 PM <DIR> CircularQUsingLinkedList
07/25/2019 12:47 PM <DIR> FindDamaged
11/09/2019 07:05 AM <DIR> GraphSearch
10/30/2019 11:53 AM <DIR> HashMapList
06/10/2019 02:19 PM <DIR> HashMapVSHashtable
08/24/2019 08:36 AM <DIR> IsUnique
08/26/2019 03:38 PM <DIR> LinkedLists
10/15/2019 05:27 AM <DIR> ListClass
06/17/2019 10:54 AM <DIR> ListsAndSets
10/23/2019 06:23 AM <DIR> Majority Element
10/18/2019 05:57 AM <DIR> MissingNumber
10/29/2019 09:38 AM <DIR> MissingTwo
06/10/2019 01:18 PM <DIR> OverridePrivate
10/15/2019 10:21 AM <DIR> PlaneRoutes
06/20/2019 10:07 AM <DIR> PrefixSum
08/10/2019 06:18 AM <DIR> RabinKarpAlgorithm
10/25/2019 05:43 AM <DIR> ReSpace
08/31/2019 05:30 AM <DIR> ReverseString
06/12/2019 09:53 AM <DIR> SimpleArraySum
11/25/2019 12:56 PM <DIR> SlidingWindow <===
09/03/2019 04:10 PM <DIR> Stack
09/03/2019 04:10 PM <DIR> StackAndQueue
08/31/2019 09:22 AM <DIR> StackArray
09/09/2019 03:37 PM <DIR> StackMin
11/17/2019 06:52 AM <DIR> StaticInitializer
09/16/2019 04:28 PM <DIR> TestInput
10/28/2019 01:08 PM <DIR> TheMasseuse
09/07/2019 05:40 AM <DIR> ThreeInOne
09/11/2019 03:02 PM <DIR> TreesAndGraphs
10/23/2019 06:56 AM <DIR> TriesHashMap
10/30/2019 06:45 AM <DIR> WordTransformer
0 File(s) 0 bytes
45 Dir(s) 548,106,178,560 bytes free
To start I created a folder in which I implemented the code for this post.
//
// Test scaffolding.
//
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read number of integers in array ****
int n = sc.nextInt();
// ???? ????
System.out.println("main <<< n: " + n);
// **** allocate array of integers ****
int[] arr = new int[n];
// **** read array of integers ****
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// ???? ????
System.out.print("main <<< arr: [");
for (int i = 0; i < arr.length; i++) {
if (i < (arr.length - 1))
System.out.print(arr[i] + " ");
else
System.out.print(arr[i]);
}
System.out.println("]");
// **** read k ****
int k = sc.nextInt();
// ???? ????
System.out.println("main <<< k: " + k);
// **** close scanner ****
sc.close();
// **** ****
System.out.println("main <<< maxSum: " + slidingWindow(arr, k));
}
The test scaffolding is implemented in the main function. As usual I tend to include debug statements in my code. Of course in this short code and most important, while using an IDE and you can single step, debug statements are of reduced value.
///
///
///
static int slidingWindow(int[] arr, int k) {
// **** compute the initial max sum (first k elements) ****
int maxSum = 0;
for (int i = 0; i < k; i++)
maxSum += arr[i];
// ???? ????
System.out.println("slidingWindow <<< maxSum: " + maxSum);
// **** loop updating the max sum ****
int sum = maxSum;
for (int i = k; i < arr.length; i++) { // **** update the sum **** sum += (-arr[i - k] + arr[i]); // ***** update the max sum (if needed) **** if (sum > maxSum)
maxSum = sum;
// ???? ????
System.out.println("slidingWindow <<< i: " + i + " sum: " + sum + " maxSum: " + maxSum);
}
// **** return the max sum ****
return maxSum;
}
We pass the array of integers and the number of integers to add at a time. We then compute the sum of the first k values in the array. At this point we are ready to start a loop to traverse the array computing the highest / maximum sum.
We loop and update a local sum that was initialized to the sum of the first k elements. On each loop we remove the value of the leftmost element from the set and include the next rightmost element. This implements a sliding window.
After we compute the new sum, we compare it against the running sum. If the new value is larger we replace the running value and keep on looping. As you can see the algorithm has a O(n) running time.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Follow me on Twitter: @john_canessa