ELI5ing LeetCode : 최소 크기 하위 배열 합계

 
From LeetCode:

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 
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 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) {

};

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...
};

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++) {

    // ???...
  }
};

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)

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 
    }

    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...

  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;

   // 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
}

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 ...;