Loop Invariants

Sample Problem

/**
* Find the min in an array of numbers
*/
export function min(array: number[]): number {

}

Solution(s)

/**
* Find the min in an array of numbers
*/
export function min(array: number[]): number {
let minimum = Infinity;
for (const item of array) {
if (item < minimum) {
minimum = item;
}
}
return minimum;
}

/**
* Find the min in an array of numbers
*/
export function minNative(array: number[]): number {
return Math.min(...array);
}

Transcript

00:00 If there is one programming concept that I could pick

00:02 that will help you ace your coding interview, that will have

00:04 to be loop in variance.

00:06 In this lesson, we will demonstrate that with an example

00:08 that is not particularly algorithmically complex,

00:11 but will help solidify the concept in your mind

00:13 so you can talk to it easily in more challenging scenarios.

00:16 So let's take a look.

00:22 Now, the programming challenge in question is

00:24 to find the minimum number in an

00:26 array of JavaScript numbers.

00:28 So we've coded up this skeleton function

00:29 where we take an input array of numbers

00:31 and return the minimum number.

00:33 Now, the concept of lu in variance is

00:35 that at any point looping through an input array, we want

00:38 to maintain some fact about a particular variable.

00:41 Now, maintaining this invariant

00:42 or unchanging fact allows us to ensure

00:45 that once we have gone through all the input elements,

00:48 we can effectively answer a given question

00:49 about the entire array.

00:51 In our particular case, the question that we want

00:53 to answer is that which number is the minimum?

00:56 So if you haven't seen any numbers yet,

00:58 we can effectively assume that the minimum number

01:00 that we have essentially seen is infinity.

01:02 And if just in case our input array contains no elements,

01:06 this is a wise value to return as well.

01:08 Now the next step is to start looping

01:10 through the input array, which we can do in JavaScript

01:12 with a simple four of loop.

01:15 Now, in each iteration of the loop, our objective is

01:18 to maintain the invariant that the minimum variable points

01:21 to the minimum value that we have seen so far.

01:24 So after we see any value,

01:25 we should check if it is less than the current

01:28 minimum that we have stored.

01:29 And if so, we need to update our minimum to this new value.

01:33 This ensures that the invariant,

01:34 that the minimum variable is pointing to the lowest value

01:37 that we have seen so far continues to hold true

01:40 as we see more and more items within the input array.

01:42 Therefore, when we have gone

01:44 through all the items in the array, by definition,

01:46 minimum is pointing

01:47 to the least value within the input array

01:50 and thus our correct answer.

01:52 In terms of challenging programming questions,

01:54 this was a pretty simple example,

01:55 but my objective is always

01:57 to explain the programming concepts in

01:59 the easiest way possible.

02:00 Now, just as an added bonus, I will also demonstrate

02:02 how you would find math admin using

02:04 JavaScript native functionality.

02:06 So let's jump back in real World code.

02:09 If you have to find the minimum of an array

02:11 of numbers within JavaScript,

02:12 you would actually use the built-in function

02:14 called math Do Min.

02:16 That takes the various numbers as arguments.

02:18 Now, in case you want to pass in an array of numbers,

02:21 you can actually use the JavaScript spread operator to turn

02:24 that array into positional arguments.

02:26 And in our particular case,

02:28 we have this array being passed in.

02:30 So I'll replace this local array that I created for a demo

02:33 and just use that one.

02:34 An interesting side note is

02:36 that the built-in JavaScript Math Min function also returns

02:39 infinity if you give it an empty array, which is similar

02:41 to the functionality that we wrote ourself.