Find Smallest Letter Greater Than Target | Binary Search | Leetcode - 744 | LinkedIn | Explanation

This is the 3rd Video on our Playlist "Solving only using C++ STLs/JAVA JCF" where we solve any problem only using C++ STLs or JAVA Collection Framework just to learn and practice them.
In this video we will try to solve an easy but good "Find Smallest Letter Greater Than Target" (Leetcode-744).

We will solve this using :
1. Brute Force
2. Binary Search (own function)
3. C++ STL - std::upper_bound

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Find Smallest Letter Greater Than Target
Company Tags : LinkedIn

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[floatingpoint]

thanks for the explanation. i noticed some people simply return left or right instead of storing the answer in position and rest of the algo is the same. i was wondering maybe you can explain why it works. personally i like you approach as it is easier to understand.

[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;
}
}

[JJ-tpdd]

Java Implementation:
class Solution {
public int bSearch(char[] l, char k) {
int n = l.length;
int s = 0;
int e = n-1;
int mid = s + (e-s)/2;
int ans = -1;
while(s<=e) {
mid = s+(e-s)/2;
if(l[mid] > k) {
ans = mid;
e=mid-1;
}
else {
s=mid+1;
}
}
return ans;
}
public char nextGreatestLetter(char[] letters, char target) {
int idx = bSearch(letters, target);

return idx==-1? letters[0] : letters[idx];

}
}

[NikhilRaj-wvnf]

Mik, can you please make a playlist on Trees

[udaykumarchetla]

Bro can u pls make a video on custom comparator, lambda function and its usage.

[anushkathakur]

minus begin(letters) karna kyon zaroori hai?