leetcode

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 };