Two Sum Sorted

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

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

Two Sum Sorted

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

Problem

/**
* Given
* @param nums array of numbers that sorted in ascending order
* @param target number
*
* @returns indices of the two numbers that add up to target
*
* You may assume:
* - each input would have exactly one solution
* - and you may not use the same element twice
*
* @example
* twoSumSorted([2, 7, 10, 15, 24], 22) => ([1,3])
*/
export function twoSumSorted(nums: number[], target: number): [number, number] {

}

Solution

/**
* Given
* @param nums array of numbers that sorted in ascending order
* @param target number
*
* @returns indices of the two numbers that add up to target
*
* You may assume:
* - each input would have exactly one solution
* - and you may not use the same element twice
*
* @example
* twoSumSorted([2, 7, 10, 15, 24], 22) => ([1,3])
*/
export function twoSumSorted(nums: number[], target: number): [number, number] {
let left = 0;
let right = nums.length - 1;

while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) {
return [left, right];
} else if (sum < target) {
left++;
} else {
right--;
}
}

throw new Error('Invalid Input: No match found');
}

Origin

Original Problem Statement

Transcript

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.