leetcode

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

search-a-2d-matrixV2.dart (1670B)

      1 //Given an input matrix of sorted elements return true if 
      2 //the matrix contains the target number.
      3 
      4 //To solve this I first did a binary search on the rows of the matrix
      5 //to find the row that target may be in. Then from there I called the searchRow
      6 //function which searches the input list and returns true if it contains the target integer.
      7 //Time complexity of this is O(log(m*n))
      8 
      9 //Time: 273ms Beats: 81.25%
     10 //Memory: 142.8MB Beats: 96.88%
     11 
     12 class Solution {
     13   bool searchMatrix(List<List<int>> matrix, int target) {
     14     int left = 0;
     15     int right = matrix.length - 1;
     16     while(left < right - 1){
     17         int midpoint = ((left + right).toInt() / 2 ).toInt();
     18         if(matrix[midpoint][0] > target){
     19             right = midpoint;
     20             continue;
     21         }
     22         else if(matrix[midpoint][matrix[midpoint].length - 1] < target){
     23             left = midpoint;
     24             continue;
     25         }
     26         return searchRow(matrix[midpoint], target);
     27     }
     28     if(searchRow(matrix[left], target) || searchRow(matrix[right], target)){
     29         return true;
     30     }
     31     return false;
     32   }
     33   bool searchRow(List<int> values, int target){
     34       int left = 0;
     35       int right = values.length - 1;
     36       while(left < right - 1){
     37           int midpoint = ((left + right).toInt() / 2).toInt();
     38           if(values[midpoint] > target){
     39               right = midpoint;
     40               continue;
     41           }
     42           else if(values[midpoint] < target){
     43               left = midpoint;
     44               continue;
     45           }
     46           return true;
     47           
     48       }
     49 
     50       if(values[left] == target || values[right] == target){
     51           return true;
     52       }
     53       return false;
     54   }
     55 }