Find Smallest Letter Greater Than Target - Leetcode 744 - Python

This video talks about solving a leetcode problem which is called Find Smallest Letter Greater Than Target.

Like 👍
Share 📣
Comment 💬
Press the Bell icon🔔for updates

#python #leetcode #coding #programming

[techerror]

Hello Guys, DON'T FORGET To LIKE & Subscribe. Press the Bell icon🔔for notification :)

[PriyamF]

Approach
Prerequisite : You MUST know the concepts of finding the floor and ceil using Binary Search. Once done, problems like these are very easy. So now when you know how to find the ceil of an element, the only twist in this problem is, that we cannot return the same letter as target. Even if that letter exists in the array, we still need to return the ceil of it. Simple. The condition
if(letters[mid]==target){
return letters[mid];
}
will be commented out, and rest all will be same. Boom! you have the most efficient O(logn) solution.

Complexity
Time complexity:
O(logn)

Space complexity:
O(1)



class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int n = letters.length;
int low = 0;
int high = n-1;
char res=' ';

while(low<=high){

int mid = low+(high-low/2);

if(target>=letters[mid]){
low=mid+1;
}
else if(target<=letters[mid]){

res=letters[mid];
high=mid-1;
}

if(res==' ')
return letters[0];
}

return res;
}
}