Shifted Sorted Array
I was recently asked this question in a coding interview, it was monitored live and I was constantly talking to my interviewer and trying to solve this on the go. I’ll be honest here, I initially found this problem pretty easy, but then it starts getting mixed up if you’re thinking on the wrong track. The problem might seem easy at first glance but there are lots of bends. After the interview, I tried to solve it with a fresh mind and I was able to do it within hardly 10–12 minutes, just because this approach was less confusing and easier to visualize.
I’ll discuss the question right away.
A sorted array of distinct integers is shifted to the left by an unknown offset and you don’t have a pre-shifted copy of it. For instance, the sequence 1, 2, 3, 4, 5 becomes 3, 4, 5, 1, 2, after shifting it twice to the left. You are given the shifted array and an integer, you have to return the index position of that item in the array, if not present return -1
The first thing that should come to your mind is the linear search which is of O(n) complexity. (Please refer this, if you don’t know what it means). But it is at the same time very obvious, that the interviewer is not expecting that.
So we need to improve it from linear time to a sub-linear time algorithm. This brings up the binary search algorithm, but wait, it needs a sorted array.
The array was sorted. Then it was shifted, which means that it is still sorted but the start point of the sorted array has shifted.
You had [1,2,3,4,5] which is sorted from index 0
You shifted it three places, [3,4,5,1,2]
If you start looking from index 3 and go sequentially in a circular fashion, you'll find that the array is still sorted.If you could come up to this point in your interview, be sure that your interviewer will have some faith in you and you have already earned some score. But, we are aiming to get it all right!
There are multiple approaches to solve this, you could modify the conditions of a traditional binary search and add extra conditions such that it covers all the possible cases. But there is no fun in that, I’ll discuss the approach I came up with and found easy to explain.
So right now, what if someone could tell me that the array has an offset of k. Would that be helpful? — Yes, it would nearly solve the problem (about 60%). So how do we get the offset?
Note that, the array is always non-decreasing. This is a very helpful characteristic that we need to exploit. Thus, whenever we see there is a decrease from the previous element to the next element, we are sure that it is the original starting element.
[4,5,1,2,3]
^ ^
This clearly shows that the array breaks here originally. Since 1 is not greater than or equal to 5.We can surely find this out in linear time. But again, we want a sub-linear solution here. You can probably take a pause here and think about some approach before continuing to read along.
Okay, I’ll share my approach now! Let’s consider you initially have two pointers low and high which are pointing to the leftmost and rightmost items of the shifted array respectively. There are a few conditions now. If the element on the left is smaller than the element on the right, that ensures that the array is in sorted order and is not shifted. Otherwise, just calculate the middle element and compare the value with the value on the left and the right, like this.
// Case 1
if(arr[low]>arr[mid] and arr[mid]<arr[high]):
Set high <- mid // Case 2
else if(arr[low]<arr[mid] and arr[mid]>arr[high]):
Set low <- mid // Case 3
else if(high-low == 1):
Return low+1
Let’s take an example and see how it works.
[7,8,9,1,2,3,4,5,6]
^ ^ ^
Following Case 1 ...
[7,8,9,1,2,3,4,5,6]
^ ^ ^
Following Case 2 ...
[7,8,9,1,2,3,4,5,6]
^ ^ ^
[7,8,9, 1, 2,3,4,5,6]
^ ^^
Return 3 ...You can see how the area under observation is being halved every time, very similar to binary search. Thus we can get the offset value using the above algorithm.
The next step is simple and I used the traditional binary search with a little bit of index adjustment magic to take into consideration the offset value.
As you can see, the overall time complexity is logarithmic O(log n) and is pretty easy to understand as well.
Please let me know if you find any test cases where my code gives a wrong output.
I won’t mind a few claps from you, as it takes considerable time and effort to write a post. :)
