leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

find-smallest-letter-greater-than-target.dart (994B)

      1 //Given a list of letters return the first
      2 //string that is less than the target. If there are 
      3 //no strings less than the target return index 0.
      4 
      5 //My solution first makes sure to see the last index is greater than target
      6 //if not it returns the first val. Then it goes through
      7 //a binary search to find the next value that is greater than the target.
      8 
      9 //Time: 275ms Beats: 50%
     10 //Memory: 143.9MB Beats: 54.44%
     11 
     12 class Solution {
     13   String nextGreatestLetter(List<String> letters, String target) {
     14       if(letters[letters.length - 1].compareTo(target) <=0){
     15           return letters[0];
     16       }
     17       int end = letters.length - 1;
     18       int start = 0;
     19       while(end - start > 1){
     20           int mid = (end + start) ~/ 2;
     21           if(letters[mid].compareTo(target) >= 1){
     22               end = mid;
     23           }
     24           else{
     25               start = mid;
     26           }
     27       }
     28       if(letters[start].compareTo(target) > 0){
     29           return letters[start];
     30       }
     31       return letters[end];
     32   }
     33 }