leetcode

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

search-a-2d-matrix.dart (1348B)

      1 //Given a 2d matrix where each column contains sorted elements
      2 //and each value from one column to the next is also in order
      3 //return true if the target is contained in the matrix or false if
      4 //not. 
      5 //This solution is bad because I could just check if matrix[i][x] == target
      6 //instead of putting them all in a sorted list and using a binary search.
      7 //I will do this again this time doing a binary search on the matrix.
      8 
      9 //Time: 282ms Beats: 59.38%
     10 //Memory: 145.6MB Beats: 53.13%
     11 
     12 class Solution {
     13   bool searchMatrix(List<List<int>> matrix, int target) {
     14       List<int> values = [];
     15       for(int i = 0 ; i < matrix.length ; ++i){
     16           for(int nums in matrix[i]){
     17               values.add(nums);
     18           }
     19       }
     20     return searchFor(values, target);
     21   }
     22   bool searchFor(List<int> values, int target){
     23       int left = 0;
     24       int right = values.length - 1;
     25       while(left < right - 1){
     26           int midpoint = ((left + right).toInt() / 2).toInt();
     27           if(values[midpoint] > target){
     28               right = midpoint;
     29               continue;
     30           }
     31           else if(values[midpoint] < target){
     32               left = midpoint;
     33               continue;
     34           }
     35           return true;
     36           
     37       }
     38 
     39       if(values[left] == target || values[right] == target){
     40           return true;
     41       }
     42       return false;
     43   }
     44 }