leetcode

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

first-and-last.dart (2761B)

      1 //Find the first and last indexes of the target value in the sorted list of nums.
      2 //The time complexity of my code is O(log(n)) with a worst case of O(n) where all elements are the target value
      3 //My solution uses a binary search to find an instance of the target number.
      4 //It then finds the upper and lower bounds of the value and returns the range.
      5 //If there are only one or two instances of the value then it gets sent to a special function to deal with short 
      6 //lists that are length <= 2.
      7 //Time: 278ms Beats: 78.26%
      8 //Memory: 145.4MB Beats: 43.48%
      9 
     10 
     11 class Solution {
     12   List<int> searchRange(List<int> nums, int target) {
     13 
     14       if(nums.length <= 2){
     15           return (solve_short(nums, target, 0));
     16       }
     17       int lower_bound = 0;
     18       int upper_bound = nums.length - 1;
     19       int found_index = 0;
     20       while(true){
     21           int median = ((lower_bound + upper_bound) / 2).toInt();
     22           if(upper_bound - lower_bound == 1){
     23               return(solve_short([nums[lower_bound] , nums[upper_bound]] , target, lower_bound));
     24           }
     25           if(nums[median] > target){
     26               upper_bound = median;
     27           }
     28           else if(nums[median] < target){
     29               lower_bound = median;
     30           }
     31           else{
     32               found_index = median;
     33               break;
     34           }
     35       }
     36       int start = 0;
     37       int end = 0;
     38       int i = found_index;
     39       while(true){
     40         if(nums.length == i){
     41             end = nums.length - 1;
     42             break;
     43         }
     44         if(nums[i] != target){
     45             end = i - 1;
     46             break;
     47         }
     48         i += 1;
     49       }
     50       i = found_index;
     51       while(true){
     52         if(i < 0){
     53             start = 0;
     54             break;
     55         }
     56         if(nums[i] != target){
     57             start = i + 1;
     58             break;
     59         }
     60         i -= 1;
     61       }
     62       return[start, end];
     63   }
     64 
     65     List<int> solve_short(List<int> nums, int target, int offset){
     66         offset = offset;
     67       if(nums.length == 0){
     68           return [-1 , -1];
     69       }
     70       if(nums.length == 1){
     71           if(nums[0] == target){
     72               return [offset, offset];
     73           }
     74           else{
     75               return[-1,-1];
     76           }
     77       }
     78       if(nums.length == 2){
     79           bool first = false;
     80           bool second = false;
     81           if(nums[0] == target){
     82               first = true;
     83           }
     84           if(nums[1] == target){
     85               second = true;
     86           }
     87           if(second == true && first == true){
     88               return [offset,1 + offset];
     89           }
     90           if(second == true){
     91               return[1 + offset,1 + offset];
     92           }
     93           if(first == true){
     94               return [offset,offset];
     95           }
     96           return [-1,-1];
     97       }
     98       return [-1,-1];
     99     }
    100 }