leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2711.cpp (1899B)

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