I've been freelancing as a JS developer for a couple of years now, and while it's been fun, I've decided it's time to break into the industry. As part of my prep for the technical interview process, I'm breaking down LeetCode problem solutions into steps so simple your 5 year old self would stand a chance at the whiteboard.
I'm starting this series of mine with the Minimum Size Subarray Sum problem, with a solution that uses the [Sliding Window] technique (https://dev.to/procode/sliding-window-technique-from-o-n-to-o-n-3la3). It's a pattern often used to reduce the time complexity of an algorithm from quadratic to linear time. And as an added bonus, this solution also works in constant space!
Author's Note: This is intended to be an exhaustive look into each step of this solution, so much so that each iteration of the loops involved will be explained in full detail. If you came for something succinct, you can jump to the summarized version using the Table of Contents below.
Table Of Contents
- Challenge Description
- Solution Summary
- Variable Set-up
- The Loop
- Opening the Window
- Slide from the Left
- Slide to the Right
- Modeling the Window
- Return
- One more thing...
- Wrap-up
Let's get to it...
The Challenge Description
From LeetCode:
Given an array of positive integers
numsand a positive integertarget, return the minimal length of a contiguous subarray[numsl, numsl+1, ..., numsr-1, numsr]of which the sum is greater than or equal totarget. If there is no such subarray, return0instead.
If you're not used to looking at these problems, this might be tough to parse. In simpler terms, the prompt is saying that we are given two inputs:
-
nums: An array of whole numbers, all of them positive. -
target: A target number, also positive and whole.
With these two inputs, we need to write a function that can find the length of a segment of the array whose members all add up to equal or exceed the target. But, this array segment must be the shortest possible segment that achieves our target.
Fortunately, there's another condition which stipulates that the segment must be contiguous, so we don't have to worry about cases where the shortest possible array could be created by combining elements not directly touching each other. When our algorithm finishes execution it should return an output that is either:
- The length of our shortest possible array segment.
Or, if the target can't be reached by summing even the _entire _nums array:
- Return
0.
Example input/output from LeetCode:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3]
has the minimal length under the problem constraint.
The Solution: Sliding Window
The sliding window is one approach to solving algorithm problems that would otherwise require nested loops. It's function is basically just to take a segment of an array by looking at all the values between two points, hence the term "window". The algorithm then moves those two points based on some condition, hence "sliding window." Applied to our challenge, the basic flow of the algorithm can be thought of like this: first, we'll find a window that adds up to our target, then slide it closed by one index from the left and check if we still hit the target. If not, we slide the window open from the right by one and check it again. We repeat this sliding process until we've slide the window all the way through the input array, all the while keeping track of the smallest window opening that hit the target.
In explaining the code, we'll keep things relatively simple for the sake of ultra clarity. We'll walk through each step of the application of the sliding window using the following easy to understand and visualize target and nums inputs:
// target = 4
// nums = [1, 1, 1, 1, 2, 2, 4]
const minSubArrayLen = function(target, nums) {
};
Variable Setup
The first thing we'll do is set up the variables we'll need in order to track all the values we'll need to come to a confident solution.
The first of these will be curMinLength. This is where we'll track our current best answer as we slide through our input array, which means it's also the variable that will contain our final answer. This will also be the value that we return at the end of the function. So what value do we instantiate this variable with?
The answer is the largest possible number, for which we'll use the JS keyword Infinity. The reason we use Infinity here is that this variable must start with a value that is larger, or at least the same size as any potential input array length. We could just use nums.length + 1 here, but that's a little verbose in comparison to the simple and clean Infinity to.
const minSubArrayLen = function(target, nums) {
let curMinLength = Infinity;
// functionality goes here...
};
The next variables we need to create will be the components of our 'window'. Remember that a window is in reality just a set of two points that demarcate the edges of a subarray. So to start, we'll create a variable left, which will act as the trailing edge of the window. Since we'll be moving from left to right in this solution, we'll give left a value of 0, so that our window starts at the 0th index of the input array.
The second component is the other end of the window, so we'll call this variable right. However, we won't yet give this a value, since we don't have quite enough information to decide how large our window should be at this point.
The last component of our window will be called sum and it will hold the value equal to the sum of all elements in contained within the current window. We'll give this a starting value of 0 as well, so that we can add the sum of our first window when the time comes.
Here's our code so far:
const minSubArrayLen = function(target, nums) {
let curMinLen = Infinity
let left = 0
let right
let sum = 0
// functionality goes here...
};
Logic Step 1: The Loop
Now that we have our variables set up, it's time for the first bit of logic. We know that we need to traverse the input array, so we'll do this in the typical fashion by writing a for loop that starts at 0, and increments a counter by 1 while the counter is less than the length of the input array. Typical, right?
Here's where things get interesting.
Instead of the traditional i counter, our for loop will use our right variable as its incrementing value. This is the mechanism by which we will slide the right side of our window! So now we have all the components of our window set up, and our code looks like this:
const minSubArrayLen = function(target, nums) {
let curMinLen = Infinity
let left = 0
let right
let sum = 0
for (let right = 0; right < nums.length; right++) {
// ???...
}
};
Logic Step 2: The Opening the Window
This is the point at which our window will become recognizable as such - we're now going to establish its initial size, or "open" it. Our goal with this step will be to get an initial segment of the input array whose elements add together to reach the target input value. We'll do this by using our already written for loop to iterate through nums, and adding each value to our sum variable. That is, we allow the for loop to increment right until sum has reached the target value. In order to detect when this has happened, we we'll need a conditional of some sort. In this solution, we're going to use a while loop to track sum/target equality. We'll see just why we need a loop rather than a simple if/else here in just a bit... But for now, let's review the code once again:
const minSubArrayLen = function(target, nums) {
let curMinLen = Infinity
let left = 0
let right
let sum = 0
for (let right = 0; right < nums.length; right++) {
// collect num values
sum = sum + nums[right]
while (sum >= target) {
// do something....
}
}
};
So. Before we get inside the while loop, the outer for loop will go about its business incrementing the right variable, adding each input element's value to the sum on each pass. Eventually, we reach a point at which that sum is equal to the target.
Let's take a moment to envision our window at this point. It should have its left edge still at the start of the array, and its right edge at the index where adding to our sum finally brought it to the target. A written representation might look like this:
// indeces: 0, 1, 2, 3, 4, 5, 6
// arr: [1, 1, 1, 1, 2, 2, 4]
// pointers: L------->R
// window: [1, 1, 1, 1]
// sum: 1+ 1+ 1+ 1 = 4 (=== target: 4)
Logic Step 3: Slide from the Left
This next step is where we'll write the real meat of the algorithm - the part where we write the logic that governs the size and position of our window. Earlier, we set up a variable curMinLen to track our best (shortest) result. When we get inside our while loop, the first thing we do is to compare curMinLen to the length of our the subarray that allowed us into the loop. We then reset curMinLen with whichever is the lesser between the current curMinLen and the length of our current window. And since Infinity is real big, on our first pass through, the length of our subarray will be shorter, and so curMinLen will now take on that value. This is the mechanism by which we will always have our best answer stored in our code for return at the end of execution. Let's take a look at how this could be written in JS:
const minSubArrayLen = function(target, nums) {
let curMinLen = Infinity
let left = 0
let right
let sum = 0
for (let right = 0; right < nums.length; right++) {
// collect num values
sum = sum + nums[right]
while (sum >= target) {
curMinLen = Math.min(curMinLen, right - left + 1)
// next step...
}
}
};
The expression right - left + 1 might be a little confusing to look at, but it's really just the length value of our current window. Here's how it looks when we spell it out:
// arr: [1, 1, 1, 1, 2, 2, 4]
// indices: 0, 1, 2, 3, 4, 5, 6
// pointers: L R
0 3
R - L + 1
3 - 0 + 1 = 4
We're using the pointer indices to figure out the full length of the window. The + 1 is just there to compensate for the fact that arrays in JS are zero indexed; think of this as the inverse of getting the last index in an array by doing array.length - 1.
So now that we know what we're looking at with our curMinLen line, what we do next? This is where we perform step 1 of the slide, which will require two steps. First, remove the first element from our current sum; second, move our left pointer one position forward. Here's the mental model:
// start of while loop
[1, 1, 1, 1, 2, 2, 4]
L R
[1+ 1+ 1+ 1] = 4 // sum
// reduce window from left
[1, 1, 1, 1, 2, 2, 4]
L R
[1+ 1+ 1] = 3 // sum reduced by previous val. at L
The way we'll write these two steps in our code is as follows:
// ...previous code
while (sum >= target) {
curMinLen = Math.min(curMinLen, right - left + 1)
sum = sum - nums[left] // 1. reduce sum
left++ // 2. move left pointer up
}
Logic Step 4: Slide to the Right
You may not have realized it right away, but when we reduced our sum, it fell below the value of the target. If our sum is less than the target, then we no longer meet the condition for staying inside the while loop, which means we're back into the previous context, the for loop. And what do for loops do at the end of each cycle? They increment counters. In our case, that counter is the right pointer of our window. This is how we slide the window open. We perform the inverse of the steps we took to close the window from the left, by first moving the pointer, and then adding its value to our sum:
for (let right = 0; right < nums.length; right++) {
// ^ 1. Move pointer
sum = sum + nums[right] // 2. Add new val to sum
// ...subsequent code
}
};
Since we've also just completed one full cycle, let's check in with the mental model to see where we go next:
[1, 1, 1, 1, 2, 2, 4]
L R
1+ 1+ 1+ 2 = 5 // current sum
// prev curMinLen = 4
// length of cur window = 4
Now that our window includes the new value at right, the sum once again satisfies the condition to enter the while loop. We go through the same series of steps: first comparing the previous curMinLen to the length of our current window (remains the same at 4), next removing the value at the left pointer from our sum, and then moving that left pointer forward one array position.
[1, 1, 1, 1, 2, 2, 4]
L R
1+ 1+ 2 = 4 // current sum
But what's this? Our sum still hasn't gone below the target value of 4! This means we repeat the steps contained within the while loop, without incrementing the right pointer. This is the mechanism that allows us to shrink the window - we close it from one side without necessarily having to open it more on the othe. Let's revisit our mental model again to see what's happening here:
// sum = 4, equal target -> continue inside while loop
[1, 1, 1, 1, 2, 2, 4]
L R // new curMinLen of 3!
(reduce sum, move left pointer)
// sum = 3, less than target -> break out of while loop
[1, 1, 1, 1, 2, 2, 4]
L->L R
// continue back into for loop...
Logic Step 5: Modeling the Window
At this point, we don't have much more to add to the code, and we're really just understanding what's happening during each iteration of each loop, so it's really about the mental modeling from here until the final step. The remaining steps can be visualized thusly:
// back in for loop...
(move right pointer forward, add new val to sum)
[1, 1, 1,[1, 2, 2], 4]
L R->R
// sum = 5 -> enter while loop
(compare lengths, reduce sum, move left pointer)
[1, 1, 1, 1,[2, 2], 4]
L->L R
// sum = 4 -> continue inside while loop
(compare lengths, // new curMinLen of 2!
reduce sum, move left pointer)
[1, 1, 1, 1, 2, [2], 4]
L->L R // same index, sum is 2
// sum = 2 -> less than target, break out of while loop
// back in for loop...
(move right pointer forward, add new val to sum)
[1, 1, 1, 1, 2,[2, 4]]
L R->R
// sum = 6 -> enter while loop
(compare lengths, reduce sum, move left pointer)
[1, 1, 1, 1, 2, 2,[4]]
L->LR
// sum = 4 -> continue while loop
(compare lengths, // new curMinLen of 1!
reduce sum, move left pointer)
// sum = 0 -> less than target, break out of while loop
// continue back into for loop for finale...
Logic Step 6: The Return
As we can see in our mental model of the pointer movements, the pointers have reached the end of the input array. This means we've traversed the entirety of our input, and exhausted all the subarrays that satisfied the target along the way. Additionally, we've kept track of the value of the shortest satisfactory subarray by storing it in curMinLen. So all we have left to do is to return that value.
let curMinLen = Infinity
let left = 0
let right
let sum = 0
for (let right = 0; right < nums.length; right++) {
sum = sum + nums[right]
while (sum >= target) {
curMinLen = Math.min(curMinLen, right - left + 1)
sum -= nums[left]
left++
}
}
return curMinLen; // last line!
Hang on a sec - what would happen in that case where we never found a subarray that summed to the target? If that was the case, then our curMinLen would still be set to its initial value of Infinity. The prompt stipulates that we should return 0 if no satisfactory array is found. To accomplish this we can add in a ternary that will substitute 0 if curMinLen has not been updated. Looks like this:
// rest of code...
}
return curMinLen == Infinity ? 0 : curMinLen;
Logic Addendum: One More Thing...
I ended up adding a little optional line to this solution after I had a realization. The shortest possible array length can only ever be 1 - even if we find another subarray that is also only one element in length, we still won't ever have reason to update our curMinLen value. This means that we have no reason to continue execution in the case that we've updated curMinLen with a value of 1.
// code...
for (let right = 0; right < nums.length; right++) {
if (curMinLen === 1) return 1;
// code...
}
Imagining a case where we have an input array that is 1,000,000 elements long, and we come across a single value at index 0 of the input array. This single line just saved the executing machine from a minimum of 999,999 unnecessary executions. It doesn't technically reduce your time complexity, but in a real world setting it could result in some considerable savings.
All that said, here's what the algorithm looks like in its final form:
const minSubArraylen = (nums, target) => {
let curMinLen = Infinity
let left = 0
let right
let sum = 0
for (let right = 0; right < nums.length; right++) {
if (curMinLen === 1) return 1
sum += nums[right]
while (sum >= target) {
curMinLen = Math.min(curMinLen, right - left + 1)
sum -= nums[left]
left++
}
}
return curMinLen == Infinity ? 0 : curMinLen
}
The Functional Wrap-up
To finish things up let's go over the compressed version of everything we've talked about so far. Below is an annotated version of the solution code that describes the function of each piece, followed by an essentialized version of the mental model I used throughout the article:
Annotated Solution:
const minSubArraylen = (nums, target) => {
let curMinLen = Infinity
/* ^ Holds final answer. Will be reset whenever a new shortest
satisfactory subarray is found. Starts at Infinity so that
it is always greater than the initial input array.*/
let left = 0
let right
let sum = 0
/* ^ These 3 variables are the components of the window. Left
side, right side, and sum of values between (and inclusive
of) the pointers. */
for (let right = 0; right < nums.length; right++) {
/* ^ Loop through array, incrementing the right pointer at each
the end of each loop. First set of iterations before while
loop is triggered will form our initial window size. */
if (curMinLen === 1) return 1
// ^ short circuit if we find subarray of length 1.
sum += nums[right]
/* ^ accumulate current nums value into sum each time right
pointer moves. */
while (sum >= target) {
// ^ If/while sum reaches target, perform the following steps:
curMinLen = Math.min(curMinLen, right - left + 1)
// check cur window length against current shortest length
sum -= nums[left]
left++
/* ^ Remove value at left pointer from sum, then move left
pointer forward. Effective is to reduce the window size from
the left. */
}
}
return curMinLen == Infinity ? 0 : curMinLen
/* ^ Final return; checks if curMinLen was never reset.
If never reset, no viable subarray was found. Return 0. */
}
Mental Model:
// target = 4
// initial window
[1, 1, 1, 1, 2, 2, 4]
LR
('for loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values sum to target
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // sum less than target
('for loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values sum to target
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values STILL sum to target
// new curMinLen of 3!
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // sum less than target
('for loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values sum to target
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values STILL sum to target
// new curMinLen of 2!
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
LR // sum less than target
('for loop executes...')
[1, 1, 1, 1, 2, 2, 4]
L R // values sum to target
('while loop executes...')
[1, 1, 1, 1, 2, 2, 4]
LR // values sum to target
// new curMinLen of 1!
('LAST for loop executes...')
return ...;
The Conceptual Wrap-up
To close things out, let's put away the microscope and look at the algorithm's overall function from a more conceptual perspective. In short, the algorithm just keeps track of two pointer locations. After computing the value between those pointers once, it can then perform a significantly smaller number of calculations to assess the slightly transposed window's value. For my money, this is the essential feature of the algorithm - we're taking advantage of the fact that we've already done the work of calculating the values within the window, and reusing that work to assume something about the next window. Imagine a version of this where instead of 4 elements that sum to target, it's 5000. Rather than redoing all 5000 of those calculations and comparing it to the next set of 5000 calculations, we just say, "this window is identical to the previous window - it's just missing the first element, and has one additional element at the end."
This particular challenge isn't the most difficult by a long shot, but this solution is (at least for me) one of those that feels satisfying to think about once you get a grip on what's actually happening. Also, I think taking the time to develop a very comprehensive understanding of these more basic techniques is essential for moving forward. Really assimilating these techniques feels like acquiring new tools that are forever at the ready once you've got them "under your belt".
If you made it all the way to the end, thanks so much for reading; I hope it was of some benefit. In the next one, I'll try to tackle something involving everyone's favorite -recursion!
Top comments (0)