In our previous lesson, we looked at the twosome problem as well as this general solution. But what happens if the input that we are provided is sorted? Can we utilize this facts to our advantage? And indeed we can. And that is the problem and the solution that we will look at in this lesson. And we will be able to get rid of the overhead of hash maps in terms of their memory as well as their optimistic linear time performance and get more real world linear time performance. And this will help you build intuition about using sorted arrays to your advantage as well. So let's go. Here's the problem statement. In its entirety, we are given an array of numbers

and a target number that we are looking for and we have to return the indices of the two numbers that add up to the target. This is the same as the Tucson problem, except one key difference. The numbers that are provided to us are sorted in as sending order. The assumptions are same as well that the problem will have one solution and we cannot use the same element and therefore the same index twice. And of course, just in case not provided, you should always come up with and walk through an example to make sure that you understand the problem correctly. Now, unlike twosome, you are going to need some divine intuition in order

to solve this particular problem, but once you see it, it is pretty easy to remember and it does help with future problems as well. That intuitive realization is the fact that the target value is going to be the sum of some small value from the left hand side of the array, as well as some large value from the right hand side of the array. To understand this a bit more, let's run through the example step by step. We have left set to the smallest number, which is two and right set to the largest number, which is 24. And we compare the sum of these two numbers against the target value of 22. We get the onset 26, which is greater than 22, which means

that our large number is too big and we need to go a bit smaller. So to decrease the total sum, we decrease our left from 24 down to 15, and then we check the sum of two plus 15 and compare it against 22. In this particular case, it is less than 22, which means that we now have to increment our small value in the next step we check seven instead of two, and that combined with 15 gives us a desired value of 22 and therefore the indices of seven and 15 is the desired solution. With this example explanation out of the way, let's start quoting up our solution.

The first thing of course would be to write the function signature that takes an array of numbers and a target number value and returns the top containing the indices of the two numbers that add up to that target. And just in case we end up in a situation where we don't find a solution, we will throw a simple error. Now we will need two variables to store the indices of the numbers that we are looking at. One will be called left and we will initialize it to zero and the other will be called right, which you will initialize to the last index in the array. And that's it for the gravy. Let's jump into the meat and potatoes. We are going to be incrementing left and decrementing right,

and we need to terminate if left becomes equal to right, because that means we are looking at the same element twice, which means that we didn't find a solution. So our termination condition is going to be left, should be less than right, And in each iteration of the loop we will check the sum of the left as well as the right number. And if it is equal to the target, congratulations, we have found a solution and we can return the left and right indices. Otherwise, if sum is less than the target, that means that the left number is too small and we increment left. Otherwise it means that the right number is too big

and we decrement right In terms of space complexity, it is now constant as we are only maintaining two simple variables left and right. And in terms of time complexity, it is O of N that is linear because we are only looping through the input array. Once.