If you already have a subscription, you can sign in.

1.Loop Invariants

free

⏱️ 2:45

2.Longest Consecutive Character

free

⏱️ 3:47

3.FizzBuzz ... Moore

free

⏱️ 4:24

4.Bracket Matching

free

⏱️ 2:55

5.Swap Two Variables In-Place

free

⏱️ 2:09

6.Array Sorting in JavaScript

⏱️ 3:45

7.Create a Linked List

free

⏱️ 4:40

8.Classic Linked List

⏱️ 2:05

9.Doubly Linked List

⏱️ 4:54

10.Revese a Linked List In-Place

⏱️ 3:45

11.Random Integers

⏱️ 3:30

12.Perfect Shuffle an Array

⏱️ 4:58

13.Derangement

⏱️ 3:48

14.Tree Data Structure Math Simplified

⏱️ 8:01

15.Queue Data Structure

⏱️ 7:23

16.Find the Repeated Item

⏱️ 3:32

17.Remove all Duplicates

⏱️ 3:25

18.Two Sum

⏱️ 3:37

19.Two Sum Sorted

⏱️ 3:36

20.Three Sum

⏱️ 7:23

00:00 In our previous lesson, we looked at the twosome problem

00:02 as well as this general solution.

00:04 But what happens if the input

00:06 that we are provided is sorted?

00:07 Can we utilize this facts to our advantage?

00:09 And indeed we can. And that is the problem

00:12 and the solution that we will look at in this lesson.

00:14 And we will be able to get rid of the overhead

00:16 of hash maps in terms of their memory as well

00:18 as their optimistic linear time performance

00:21 and get more real world linear time performance.

00:24 And this will help you build intuition about using sorted

00:26 arrays to your advantage as well.

00:28 So let's go. Here's the problem statement.

00:31 In its entirety, we are given an array of numbers

00:34 and a target number that we are looking for

00:36 and we have to return the indices of the two numbers

00:38 that add up to the target.

00:40 This is the same as the Tucson problem,

00:42 except one key difference.

00:44 The numbers that are provided

00:45 to us are sorted in as sending order.

00:47 The assumptions are same as well

00:48 that the problem will have one solution

00:50 and we cannot use the same element and

00:52 therefore the same index twice.

00:54 And of course, just in case not

00:56 provided, you should always come up with

00:58 and walk through an example to make sure

01:00 that you understand the problem correctly.

01:02 Now, unlike twosome, you are going

01:04 to need some divine intuition in order

01:05 to solve this particular problem,

01:07 but once you see it, it is pretty easy to remember

01:09 and it does help with future problems as well.

01:12 That intuitive realization is the fact

01:14 that the target value is going to be the sum

01:16 of some small value from the left hand side of the array,

01:19 as well as some large value from the right

01:21 hand side of the array.

01:22 To understand this a bit more, let's run

01:25 through the example step by step.

01:26 We have left set to the smallest number, which is two

01:30 and right set to the largest number, which is 24.

01:32 And we compare the sum

01:34 of these two numbers against the target value of 22.

01:37 We get the onset 26, which is greater than 22, which means

01:41 that our large number is too big

01:43 and we need to go a bit smaller.

01:44 So to decrease the total sum,

01:46 we decrease our left from 24 down to 15,

01:49 and then we check the sum of two plus 15

01:51 and compare it against 22.

01:53 In this particular case, it is less than 22, which means

01:57 that we now have to increment our small value in the next

02:00 step we check seven instead of two,

02:02 and that combined with 15 gives us a desired value of 22 and

02:06 therefore the indices of seven

02:07 and 15 is the desired solution.

02:10 With this example explanation out of the way,

02:12 let's start quoting up our solution.

02:14 The first thing of course would be

02:15 to write the function signature that takes an array

02:17 of numbers and a target number value

02:19 and returns the top containing the indices

02:21 of the two numbers that add up to that target.

02:24 And just in case we end up in a situation

02:26 where we don't find a solution,

02:27 we will throw a simple error.

02:29 Now we will need two variables to store the indices

02:32 of the numbers that we are looking at.

02:33 One will be called left and we will initialize it to zero

02:36 and the other will be called right,

02:37 which you will initialize to the last index in the array.

02:40 And that's it for the gravy.

02:42 Let's jump into the meat and potatoes.

02:44 We are going to be incrementing left and decrementing right,

02:46 and we need to terminate if left becomes equal to right,

02:49 because that means we are looking at the same element twice,

02:52 which means that we didn't find a solution.

02:54 So our termination condition is going to be left,

02:57 should be less than right,

02:59 And in each iteration of the loop we will check the sum

03:02 of the left as well as the right number.

03:04 And if it is equal to the target, congratulations,

03:06 we have found a solution

03:07 and we can return the left and right indices.

03:10 Otherwise, if sum is less than the target, that means

03:13 that the left number is too small and we increment left.

03:16 Otherwise it means that the right number is too big

03:19 and we decrement right In terms of space complexity,

03:22 it is now constant

03:23 as we are only maintaining two simple

03:25 variables left and right.

03:27 And in terms of time complexity, it is O of N that is linear

03:30 because we are only looping through the input array.

03:33 Once.

1.Loop Invariants

free

⏱️ 2:45

2.Longest Consecutive Character

free

⏱️ 3:47

3.FizzBuzz ... Moore

free

⏱️ 4:24

4.Bracket Matching

free

⏱️ 2:55

5.Swap Two Variables In-Place

free

⏱️ 2:09

6.Array Sorting in JavaScript

⏱️ 3:45

7.Create a Linked List

free

⏱️ 4:40

8.Classic Linked List

⏱️ 2:05

9.Doubly Linked List

⏱️ 4:54

10.Revese a Linked List In-Place

⏱️ 3:45

11.Random Integers

⏱️ 3:30

12.Perfect Shuffle an Array

⏱️ 4:58

13.Derangement

⏱️ 3:48

14.Tree Data Structure Math Simplified

⏱️ 8:01

15.Queue Data Structure

⏱️ 7:23

16.Find the Repeated Item

⏱️ 3:32

17.Remove all Duplicates

⏱️ 3:25

18.Two Sum

⏱️ 3:37

19.Two Sum Sorted

⏱️ 3:36

20.Three Sum

⏱️ 7:23