2711.cpp (1899B)
1 2 // Solution idea 3 class Solution { 4 public: 5 vector<vector<int>> differenceOfDistinctValues(vector<vector<int>> &grid) { 6 const int n = grid.size(), m = grid[0].size(), l = n - 1; 7 vector<unordered_set<int>> vus(m + n - 1); 8 vector<vector<int>> res(n, vector(m, 0)); 9 10 for (int i = 0; i < n; i++) { 11 for (int j = 0; j < m; j++) { 12 res[i][j] = vus[j - i + l].size(); 13 vus[j - i + l].insert(grid[i][j]); 14 } 15 } 16 17 for (int i = 0; i < m + n - 1; i++) 18 vus[i].clear(); 19 20 for (int i = n - 1; i >= 0; i--) { 21 for (int j = m - 1; j >= 0; j--) { 22 res[i][j] = abs((int)(res[i][j] - vus[j - i + l].size())); 23 vus[j - i + l].insert(grid[i][j]); 24 } 25 } 26 27 return res; 28 } 29 }; 30 31 // Optimized solution 32 class Solution { 33 public: 34 vector<vector<int>> differenceOfDistinctValues(vector<vector<int>> &grid) { 35 int vus[101][51] = {0}, count[101] = {0}; 36 const int n = grid.size(), m = grid[0].size(), l = n - 1; 37 vector<vector<int>> res(n, vector(m, 0)); 38 39 for (int i = 0; i < n; i++) { 40 for (int j = 0; j < m; j++) { 41 res[i][j] = count[j - i + l]; 42 if (vus[j - i + l][grid[i][j]] != 1) { 43 vus[j - i + l][grid[i][j]] = 1; 44 count[j - i + l]++; 45 } 46 } 47 } 48 49 for (int i = 0; i < m + n - 1; i++) 50 count[i] = 0; 51 52 for (int i = n - 1; i >= 0; i--) { 53 for (int j = m - 1; j >= 0; j--) { 54 res[i][j] = abs(res[i][j] - count[j - i + l]); 55 if (vus[j - i + l][grid[i][j]] != 2) { 56 vus[j - i + l][grid[i][j]] = 2; 57 count[j - i + l]++; 58 } 59 } 60 } 61 62 return res; 63 } 64 };