Sliding Window…
Hello all! Still working my way through the wild world of algorithms and data structures. Lately I’ve been grinding on LeetCode almost everyday trying to solve easy level problems but even the easy problems can be very hard. Coming from a bootcamp, problem solving isn’t really something that’s fully taught but it’s kind of difficult to teach while also teaching how to build things. Through doing algorithmic problems is where I’m picking up the skill, very so slowly but making progress. One of the things I’m recognizing though is some problems can be solved with specific techniques. One of these techniques that I’m working on mastering is the sliding window. The way this technique works is moving through a subset of elements in a array or string, either expanding or shrinking that subset until a condition is satisfied.
I watched a Udemy video on this technique once but it wasn’t until I actually attempted a problem using the sliding window technique that it really started to become clear to me. This sliding window technique is a great option when you need keep track of elements in an array but specifically a contiguous sequence. Contiguous refers to two or more objects that adjacent to each other. In computing, contiguous data is data that is moved or stored in a solid uninterrupted block. In general, contiguous data can be accessed more quickly than data that is stored in fragments because fewer access operations will be required. Words such as contiguous, minimum, maximum, sum are usually hints that using the sliding window technique is optimal for your solution.
This is the first LeetCode problem where I was able to fully understand the sliding window technique. Idk about you but for me, I often don’t even understand the question and sometimes the explanation doesn’t help much either. This particular question is asking for the total of all the numbers that will return the highest sum. At first glance looking at example 1 compared to example 3, I was confused. Example 3 looks like it’s just adding the total of all integers but when implementing the sliding window technique, it’s not at all.
Line 312 & 313, I’ve set both variables to be at the first index of the array which is -2. Line 315 the loop is initialized to start at index 1 which is also the value of 1. Line 316 currentNum is set to the value at index 1 in the nums array which again is also 1. Line 318 is where maxValueSofar changes. The Math keyword is an object that allows you to perform mathematical tasks on numbers. The .max is one of several methods available to the Math object. This method is used to find the highest value in a list of arguments. During the first iteration, currentNum’s value is 1. The Math.max function is comparing -2 & -1, since maxValueSofar’s value is -2 + currentNum is 1, we get -1. Since -2 is smaller than 1, maxValueSofar is updated to 1. Line 320 is also updating the value of largestSum to 1. Since we haven’t reached the end of the array, our loop starts over again and now currentNum is In the second iteration, currentNum is now -3. The comparison will continue to happen until it reaches the end of the array but notice once it reaches the -5, that doesn’t help with increasing the sum. So this why in the explanation [4,-1,2,1] is the subset in the array that will give the largest sum of 6.
I hope this was helpful ! Happy coding!
