leetcode

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

maximum-number-of-moves-in-a-grid.dart (3032B)

      1 //Find the maximum number of moves that can be made for a grid starting from the first column where you can only move to the right and
      2 //either move up by one down by one or stay in the same position vertically. The time complexity of my code is (O(n) where n is the number of 
      3 //tiles in the matrix because each time a location is traversed then it's value is remembered thus not requiring revisitation.
      4 //Time: 575MS Beats: 100%
      5 //Memory: 192.7MB Beats: 100%
      6 class Solution {
      7   Map<String , int> memo = {};
      8   int maxMoves(List<List<int>> grid) {
      9     int max = 0;
     10     for(int i = 0 ; i < grid.length ; ++i){
     11       int current = maxFromPos(grid, [i , 0]);
     12       if(current - 1 > max){
     13         max = current - 1;
     14       }
     15     }
     16     return max;
     17   }
     18 
     19   int maxFromPos(List<List<int>> grid, List<int> current_position){
     20       if(current_position[1] == grid[0].length - 1){
     21           return 1;
     22       }
     23       String curr_str = current_position[0].toString() + " " + current_position[1].toString();
     24       if(memo.containsKey(curr_str)){
     25         int curr_val = (memo[curr_str] ?? 0);
     26         return curr_val;
     27       }
     28       int current_val = grid[current_position[0]][current_position[1]];
     29       int max = 0;
     30       if(current_position[0] == 0){
     31           List<int> right = [current_position[0], current_position[1] + 1]; 
     32           if(grid[right[0]][right[1]] > current_val){
     33             max = maxFromPos(grid, right);
     34           }
     35           List<int> down = [current_position[0] + 1, current_position[1] + 1];
     36           if(grid[down[0]][down[1]] > current_val){
     37             int down_val = maxFromPos(grid,down);
     38             if(down_val > max){
     39                 max = down_val;
     40             }
     41           }
     42       }
     43       else if(current_position[0] == grid.length - 1){
     44           List<int> up = [current_position[0] - 1, current_position[1] + 1];
     45           if(grid[up[0]][up[1]] > current_val){
     46             max = maxFromPos(grid, up);
     47           }
     48           List<int> right = [current_position[0], current_position[1] + 1]; 
     49           if(grid[right[0]][right[1]] > current_val){
     50             int right_val = maxFromPos(grid,right);
     51             if(right_val > max){
     52                 max = right_val;
     53             }
     54           }
     55       }
     56       else{
     57           List<int> up = [current_position[0] - 1, current_position[1] + 1];
     58           if(grid[up[0]][up[1]] > current_val){
     59             max = maxFromPos(grid, up);
     60           }
     61           List<int> right = [current_position[0], current_position[1] + 1]; 
     62           if(grid[right[0]][right[1]] > current_val){
     63             int right_val = maxFromPos(grid,right);
     64             if(right_val > max){
     65                 max = right_val;
     66             }
     67           }
     68             List<int> down = [current_position[0] + 1, current_position[1] + 1];
     69             if(grid[down[0]][down[1]] > current_val){
     70               int down_val = maxFromPos(grid,down);
     71               if(down_val > max){
     72                   max = down_val;
     73               }
     74             }
     75       }
     76       memo[curr_str] = max + 1;
     77       return max + 1;
     78   }
     79 }