Advertisement
atulsingh7890

Largest Submatrix with Rearrangements

Jan 17th, 2021
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. //https://leetcode.com/problems/largest-submatrix-with-rearrangements/
  2.  
  3. class Solution {
  4.     bool CustomComparator(const std::vector<int> & a, const std::vector<int> & b) {
  5.         bool result = true;
  6.         for(int i = 0;  i < a.size(); ++i) {
  7.             if(a[i] > b[i]) {
  8.                 result = false;
  9.                 break;
  10.             }
  11.         }
  12.         return result;
  13.     }
  14. public:
  15.     int largestSubmatrix(vector<vector<int>>& matrix) {
  16.         for(int i = 0; i < matrix[0].size(); ++i) {
  17.             int sum = 0;
  18.             for(int j = 0; j < matrix.size(); ++j) {
  19.                 sum =  (matrix[j][i] == 0) ? 0  : (sum + 1);
  20.                 //std::cout << matrix[j][i] << ",";
  21.                 matrix[j][i] = sum;
  22.                 //std::cout << sum << "    ";
  23.             }
  24.             //std::cout << "\n";
  25.         }
  26.        
  27.         int ans = 0;
  28.         for(int i= 0; i < matrix.size(); ++i) {
  29.             // sort the current in descending order
  30.             std::sort(matrix[i].begin(), matrix[i].end() , std::greater<int>());
  31.            
  32.             for(int j = 0; j < matrix[i].size(); ++j) {
  33.                 ans = std::max(ans, matrix[i][j] * (j+1));
  34.             }
  35.         }
  36.        
  37.        
  38.         return ans;
  39.     }
  40. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement