[Solution]Problem 16: Last index of value[Amazon]

Medium, Searching, Indexes, Arrays

Problem

This problem was asked by Amazon.

You are given a sorted array and a value i. Find the last index where the value appears.

For example, given

arr=[1,1,1,3,3,4,5,5,5]
and i= 1 

your solution should return 2. Don’t use any external library functions.

HINT/Spoiler: This problem has a lot of nuances that you should think about

Step 1: Clarifying Constraints

This is an overlooked first step in coding interviews. Remember the hint? You will see why I chose to give that here instead of in a “harder” question. Questions like this seem obvious on the surface, which can make it easy to overlook the nuances.

Some questions/observations that you verbalize to the interviewers:

1. Seems the arrays have repeating values. Is there an upper limit to the number of repetitions?

2. What do I do if the array is empty? Should I return -1/something special?

3. What if the value doesn’t exist in the array?

None of these questions are strictly game-changing. But it is good practice to help you ask good questions in your interviews.

Step 1.5

This question is interesting because there is a clear way to split this question into separate parts and solve them. We can break this question into two parts:

1. Find an index where the value exists.

2. Using this, find the last index.

Since the array is sorted, we know that all the identical values will be bunched up together.

Step 2: Solution to part 1

I will not mention linear search as a solution. You should immediately be able to identify binary search as a valid way to find the value and its index in the array. With questions involving finding values in sorted arrays, binary search is your go-to. Following is a quick refresher on how binary search looks.

With it, we can discover an index of i. Now that we have one index of i, how do we do part 2 of our solution?

Step 3: Solution to part 2

How can we find the last index, being given a starting point? Easy we traverse using the current index. But how do we traverse the array?

This is where the nuance of the questions comes in. If the repetitions are guaranteed to be logarithmic or a constant number, we can traverse the array linearly from our current starting point. This would still not increase our logarithmic run time.

However, if the upper bound on repetitions is a linear function of n (it can’t be more than n), then our solution becomes O(n). And all the hard work of implementing binary search will go to waste. So what do we do?

Step 4: Getting Creative

How do we work through this challenge? We need a solution that is at most logarithmic. We have a sorted array. If we could find a value to search for, we can binary search.

And that’s where we tweak the parameters a bit. Binary Search is log because of how it bisects the search space in half every iteration. We can do the same. But instead of stopping when we find an i value, we store the index and move our low bound to the next value. This will allow us to keep bisecting the search space. And if since we keep updating the latest index of the value, we won’t miss anything.

def last(arr, i):
     
    low = 0
    high = len(arr) - 1
    idx = -1 #handle case where it doesn't exist
     
    while(low <= high):
         
        # Normal Binary Search Logic
        mid = (low + high) // 2
         
        if arr[mid] > x:
            high = mid - 1
        elif arr[mid] < x:
            low = mid + 1
             
        # If arr[mid] is same as x, we
        # update index and move to the Right
        # half.
        else:
            res = mid
            low = mid + 1
 
    return idx

We always bisect our search space in half. So we have a log base 2 run time. And we have a few constant variables. So we use constant extra space. Remember, the data structures given to you in a question don’t count in the space analysis.

Final: O(log n) Time and O(1) space

Bonuses/Promotion (Get Free Stuff)

Have anything to say to me? Use the links below.

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75