Next Greatest Alphabet in an Array [Using Binary Search Algorithm]

Mishonda 0
Viewed 42

I am trying to solve a question on Leetcode

Find Smallest Letter Greater Than Target

Given a characters array letters that is sorted in non-decreasing order and a character target, return the smallest character in the array that is larger than target.

Note that the letters wrap around.

For example, if target == 'z' and letters == ['a', 'b'], the answer is 'a'.

Example 1:
Input: letters = ["c","f","j"], target = "a"
Output: "c"

Example 2:
Input: letters = ["c","f","j"], target = "c"
Output: "f"

Example 3: 
Input: letters = ["c","f","j"], target = "d"
Output: "f"

Constraints:

2 <= letters.length <= 104
letters[i] is a lowercase English letter.
letters is sorted in non-decreasing order.
letters contains at least two different characters.
target is a lowercase English letter.

My solution until now looks something like this:

function nextGreatestAlphabet(letters, target){
  let left = 0; 
  let right  = letters.length - 1;
  let res = -1; 
        while(left <= right) {
            let mid = Math.floor(left + (right - left) / 2);

            if (letters[mid] == target ) { console.log(1)
                res = letters[mid];
                left = mid  + 1;
            }
            if(letters[mid] > target){  console.log(2)
                right = mid -1;
                res = letters[mid];
            }
            if(letters[mid] < target ){  console.log(3)
              left = mid + 1;
            }
        }
        return res;
}

console.log(nextGreatestAlphabet(["c","f","j"],"c")); //c

But the correct result should be "f" as c is already present here and next greatest is f

binary-search algorithm javascript
2 Answers

I think that your

  if (letters[mid] == target ) { console.log(1)
                 res = letters[mid];
                 left = mid  + 1;
             }

sets the result to the target but you actually want to have the next one, so it should be sth. like

 res=letter[mid+1].

if

mid==letters.length - 1

holds then it is already the right end. then you can just put

res = letter[0];
Watermelon0

You should avoid setting res during the search, and certainly not set it when letters[mid] == target, as it is sure that is not the correct answer. Instead you should get the result after the loop has exited.

This then also means you don't need a separate case for letters[mid] == target, as the rest of the action is exactly what is done for letters[mid] < target. So you can make this a quite simple if (letters[mid] > target) ... else ... structure.

After the loop has exited, the left index points to the desired character. Then you need to deal with the boundary case where that index points beyond the array and map it to 0. This you can do with the remainder operator:

NB: I use here the name of the function as required by the LeetCode challenge:

function nextGreatestLetter(letters, target) {
    let left = 0; 
    let right  = letters.length - 1;

    while(left <= right) {
        let mid = Math.floor(left + (right - left) / 2);

        if(letters[mid] > target) {
            right = mid -1;
        } else {
            left = mid + 1;
        }
    }
    return letters[left % letters.length];
}

Personally, I prefer working with right being the index just after the range that is under consideration, and for deriving mid you can use the >> operator (Array sizes are limited in this challenge, so that is a safe operation):

function nextGreatestLetter(letters, target) {
    let left = 0; 
    let right = letters.length;
    while (left < right) {
        let mid = (left + right) >> 1;
        if (letters[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return letters[left % letters.length];
}
trincot0
Related