leetcode

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

the-k-weakest-rows-in-a-matrix.dart (1530B)

      1 //Given a matrix return the k weakest rows where a row
      2 //is weaker if it has less 1's in it, or it is in front of another
      3 //row that has the same number of 1's in it. To do this
      4 //I first found the weakest rows with the least ones.
      5 //I then iterated through the list searching out the weakest
      6 //rows each time and returned the final list.
      7 //The time complexity is O(n^2).
      8 //Time: 265ms Beats: 92.86%
      9 //Memory: 144.5MB Beats: 92.86%
     10 
     11 class Solution {
     12   List<int> kWeakestRows(List<List<int>> mat, int k) {
     13       List<int> strengths = [];
     14       for(int i = 0 ; i < mat.length ; ++i){
     15           int current = 0;
     16           for(int x = 0 ; x < mat[i].length; ++x){
     17               if(mat[i][x] == 0){
     18                   break;
     19               }
     20               current += 1;
     21           }
     22           strengths.add(current);
     23       }
     24       List<int> ret_list = [];
     25       List<int> sorted = List.from(strengths);
     26       sorted.sort();
     27       int itr = 0;
     28       int curr_val = sorted[0];
     29       int sort_val = 0;
     30       while(sort_val < k){
     31           if(strengths[itr] == curr_val){
     32               ret_list.add(itr);
     33               sort_val += 1;
     34               if(sorted.length > sort_val){
     35                 curr_val = sorted[sort_val];
     36               }
     37               else{
     38                   break;
     39               }
     40               if(curr_val == strengths[itr]){
     41                   itr += 1;
     42                   continue;
     43               }
     44               itr = 0;
     45           }
     46           else{
     47               itr += 1;
     48           }
     49       }
     50       return ret_list;
     51   }
     52 }