leetcode

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

01-matrixV1.dart (2621B)

      1 //This solution is a bit faster as it uses BFS on all of the
      2 //tiles in the matrix to find the nearest 0. It also uses
      3 //memoization, and a more optimized implementation of a queue.
      4 //Still it is too slow because there is one matrix that has a single zero
      5 //in the bottom right corner which means each node has to search the entire list to 
      6 //find it. To finally complete this I will need to do bfs using each of the 0's.
      7 
      8 class Solution {
      9   List<List<int>> updateMatrix(List<List<int>> mat) {
     10       List<List<int>> answers = [];
     11       for(int i = 0 ; i < mat.length ; ++i){
     12           answers.add([]);
     13           for(int x = 0 ; x < mat[i].length ; ++x){
     14               answers[i].add(-1);
     15           }
     16       }
     17 
     18       for(int i = 0 ; i < answers.length ; ++i){
     19           for(int x = 0 ; x < answers[0].length ; ++x){
     20               answers[i][x] = find_nearest([i,x], mat, answers);
     21           }
     22       }
     23       return answers;
     24   }
     25   
     26   int find_nearest(List<int> find, List<List<int>> matrix, List<List<int>> memo){
     27 
     28       List<List<int>> to_visit = [];
     29       to_visit.add(find);
     30       Set<String> visited = {};
     31       int itr = 0;
     32       int itr_stop = -1;
     33 
     34       while(true){
     35           int init_length = to_visit.length;
     36           if(itr_stop != -1 && itr >= itr_stop){
     37               return itr_stop;
     38           }
     39           for(int i = 0 ; i < init_length ; ++i){
     40               List<int> current = to_visit[i];
     41               if(visited.contains(current[0].toString() + " " + current[1].toString())){
     42                   continue;
     43               }
     44               visited.add(current[0].toString() + " " + current[1].toString());
     45               int current_mem_val = memo[current[0]][current[1]];
     46               if(current_mem_val != -1){
     47                   if(itr_stop == -1 || itr_stop > itr + current_mem_val){
     48                       itr_stop = itr + current_mem_val;
     49                   }
     50                   continue;
     51               }
     52 
     53 
     54               if(matrix[current[0]][current[1]] == 0){
     55                   return itr;
     56               }
     57               if(current[0] > 0){
     58                   to_visit.add([current[0] -1, current[1]]);
     59               }
     60               if(current[1] > 0){
     61                   to_visit.add([current[0], current[1] - 1]);
     62               }
     63               if(current[0] < matrix.length - 1){
     64                   to_visit.add([current[0] + 1, current[1]]);
     65 
     66               }
     67               if(current[1] < matrix[0].length - 1){
     68                   to_visit.add([current[0], current[1] + 1]);
     69               }
     70           }
     71           to_visit = to_visit.sublist(init_length);
     72           itr += 1;
     73       }
     74       return 404;
     75   }
     76 
     77 }