Skip to content

Minimum Operations to Write the Letter Y on a Grid⚓︎

Link

Solution⚓︎

Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minimumOperationsToWriteY(vector<vector<int>>& grid) {
        int num0 = 0, num1 = 0, num2 = 0, num0Y = 0, num1Y = 0, num2Y = 0;
        int n = grid.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == j && i <= n / 2) || (i + j == n - 1 && i <= n / 2) || (i >= n / 2 && j == n / 2)) {
                    if (grid[i][j] == 0) num0Y++;
                    else if (grid[i][j] == 1) num1Y++;
                    else num2Y++;
                } else {
                    if (grid[i][j] == 0) num0++;
                    else if (grid[i][j] == 1) num1++;
                    else num2++;
                }
            }
        }

        int change0 = num1Y + num2Y + min(num0 + num2, num0 + num1);
        int change1 = num0Y + num2Y + min(num1 + num2, num0 + num1);
        int change2 = num0Y + num1Y + min(num1 + num2, num0 + num2);
        return min({change0, change1, change2});
    }
};

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minimumOperationsToWriteY(vector<vector<int>>& grid) {
        array<int, 3> countY{0}, countOut{0};

        int m = grid.size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if ((i == j && i <= m / 2) 
                || (i + j == m - 1 && i <= m / 2) 
                || (i > m / 2 && j == m / 2)) {
                    countY[grid[i][j]]++;
                } else countOut[grid[i][j]]++;
            }
        }

        int maxNotChange = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j)
                    maxNotChange = max(maxNotChange, countY[i] + countOut[j]);
            }
        }

        return m * m - maxNotChange;
    }
};
  • Time complexity: \(O(m^2 + k^2)\), where \(k=3\);
  • Space complexity: \(O(k)\).