NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊
Magic Index: A magic index in an array A[ 0 … n-1] is defined to be an index such that A[ i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
FOLLOW UP: What if the values are not distinct?
The description of this exercise is suspiciously similar to the binary search: we need to find some value in the sorted array. So, can we tell with 100% confidence looking at a random number in the array whether the magic index is on the left or on the right side of it? Then we would be able to apply the binary search algorithm. It actually looks like yes 🙌
Let's take a random array that satisfies the condition of being distinct & sorted (see an example below), and look at one of the numbers in it- for instance, 1. We know that all numbers before one are smaller than 1, and all numbers after one are bigger than 1 (array is sorted!). In this example, 1 is smaller than its index (it is 4th element => has an index of 3).
Given that the numbers before one are all distinct, the number with the index 2 will be less than 1 (or ≤ 0) - remember that array is sorted. Consequently, number at index 1 will be ≤ -1 - continuing the pattern of each next number being at least (previous number-1) . The indices are also decreasing by one, and thus in the best case scenario both indices and numbers in the array will decrease by one with every step, keeping the relation between 1 and its index: that number is less than the index. Thus, for the numbers before 1 index will never equal the number.
As a result, we should be fine cutting the part before 1 off - and continuing searching for the magic index in the part of the array to the right of 1. The same logic can be applied to the opposite situation: if the number is bigger than its index, the numbers to the right of it will always be bigger then their indices, so we can continue with just the left part. Below you can find the code that summarizes this logic:
function giveMeMagic(sortedArr) {
const endArray = sortedArr.length - 1;
function findMagic(arr, minIndex, maxIndex) {
const middleIndex = Math.ceil((minIndex + maxIndex) / 2);
const middleValue = arr[middleIndex];
if (middleValue === middleIndex) { return middleIndex; }
if (minIndex > maxIndex) { return -1; }
if (middleValue > middleIndex) {
return findMagic(arr, 0, middleIndex - 1)
}
if (middleValue < middleIndex) {
return findMagic(arr, middleIndex + 1, maxIndex)
}
}
return findMagic(sortedArr, 0, endArray)
}
Using the binary search approach, we'll always cut the array into 2 halves and check the middle number: if this number equals its index, we've found our magic number! If the number is bigger than its index, we'll continue with the left part - else we'll continue with the right part.
One more thing to mention is the stop condition: in the chunk of code above we're stopping when minIndex becomes bigger than maxIndex, why is that? From the code you can see that we're recalculating maxIndex every time we go for the left part, and minIndex when we go for the right one. If the magic index is not found, we'll always reach the step when maxIndex equals minIndex. The next step after that will either decrease maxIndex (if going to the left) or increase minIndex (if going to the right) - satisfying the minIndex > maxIndex condition. The sketch below should make it a bit more explicit (circled are the middle values on each step):
For the follow-up question, however, the right/left logic does not apply anymore. In the array below the numbers are still sorted, but 1 is duplicated. If we split an array at a circled 1 (the middle index), we can find now the Magic Index both lo the left (underscored 1) and to the right side of it (4) - although the middle value is smaller than the middle index.
So, the first thing that comes to mind is just using the brute force approach and check every number one by one. But can we maybe optimize it somehow?
We know that the middle number (1) is lower that its index (3). Can the number next to it to the right be equal to the next index (4)? Yes, there are no reasons for this not to work, and actually this is exactly the case that we can see in the example above.
However, can the same happen to the number to the left of middle 1? We know that the numbers are sorted, and the next index to the left is 2. Can the number at index 2 equal 2? No, because it has to be smaller or equal to 1 (numbers are sorted!). That means that the first possible index to the left that can have the magic number in it is the index 1. Following this logic, we can skip all indices that are bigger than the middle number (if the middle number is smaller than its index) and skip all indices that are smaller than the middle number (if the middle number is bigger than its index). I've implemented this in JS in the following way:
function giveMeMagic(sortedArr) {
const endArray = sortedArr.length - 1;
function findMagic(arr, minIndex, maxIndex) {
const middleIndex = Math.ceil((minIndex + maxIndex) / 2);
const middleValue = arr[middleIndex];
if (middleValue === middleIndex) { return middleIndex; }
if (minIndex > maxIndex) { return -1; }
const maxIndexLeft = middleValue < middleIndex ? middleValue : middleIndex - 1;
const left = findMagic(arr, 0, maxIndexLeft);
if (left >= 0) { return left; }
const minIndexRight = middleValue > middleIndex ? middleValue : middleIndex + 1;
const right = findMagic(arr, minIndexRight, maxIndex);
return right;
}
return findMagic(sortedArr, 0, endArray)
}
One important thing to notice here: on every step of recursion we're calculating and returning left side before doing any recursion for the right side. And only if left returns -1, we proceed with calculating right. This way if the Magic index is found on the left side, we can spare the right side calculations.
Top comments (0)