Skip to content

3071. Minimum Operations to Write the Letter Y on a Grid 👍

  • Time: $O(n^2)$
  • Space: $O(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
26
27
class Solution {
 public:
  int minimumOperationsToWriteY(vector<vector<int>>& grid) {
    return min({getOperations(grid, 0, 1), getOperations(grid, 0, 2),
                getOperations(grid, 1, 0), getOperations(grid, 1, 2),
                getOperations(grid, 2, 0), getOperations(grid, 2, 1)});
  }

 private:
  // Returns the number of operations to turn Y into a and non-Y into b.
  int getOperations(const vector<vector<int>>& grid, int a, int b) {
    const int n = grid.size();
    const int mid = n / 2;
    int operations = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        // For the 'Y' pattern, before the midpoint, check the diagonal and
        // anti-diagonal. After the midpoint, check the middle column.
        if ((i < mid && (i == j || i + j == n - 1)) || (i >= mid && j == mid)) {
          if (grid[i][j] != a)
            ++operations;
        } else if (grid[i][j] != b) {
          ++operations;
        }
    return operations;
  };
};

 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(int[][] grid) {
    return Math.min(Math.min(Math.min(getOperations(grid, 0, 1), getOperations(grid, 0, 2)),
                             Math.min(getOperations(grid, 1, 0), getOperations(grid, 1, 2))),
                    Math.min(getOperations(grid, 2, 0), getOperations(grid, 2, 1)));
  }

  // Returns the number of operations to turn Y into a and non-Y into b.
  private int getOperations(int[][] grid, int a, int b) {
    final int n = grid.length;
    final int mid = n / 2;
    int operations = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        // For the 'Y' pattern, before the midpoint, check the diagonal and
        // anti-diagonal. After the midpoint, check the middle column.
        if ((i < mid && (i == j || i + j == n - 1)) || (i >= mid && j == mid)) {
          if (grid[i][j] != a)
            ++operations;
        } else if (grid[i][j] != b) {
          ++operations;
        }
    return operations;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def minimumOperationsToWriteY(self, grid: list[list[int]]) -> int:
    n = len(grid)
    mid = n // 2

    def getOperations(a: int, b: int) -> int:
      """Returns the number of operations to turn Y into a and non-Y into b."""
      operations = 0
      for i, row in enumerate(grid):
        for j, num in enumerate(row):
          # For the 'Y' pattern, before the midpoint, check the diagonal and
          # anti-diagonal. After the midpoint, check the middle column.
          if (i < mid and (i == j or i + j == n - 1)) or i >= mid and j == mid:
            if num != a:
              operations += 1
          elif num != b:
            operations += 1
      return operations

    return min(getOperations(0, 1), getOperations(0, 2),
               getOperations(1, 0), getOperations(1, 2),
               getOperations(2, 0), getOperations(2, 1))