We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Write the Letter Y on a Grid

Difficulty: Medium

Problem Description

You are given a 0-indexed n x n grid where n is odd, and grid[r][c] is 0, 1, or 2. We say that a cell belongs to the Letter Y if it belongs to one of the following: the diagonal starting at the top-left cell and ending at the center cell of the grid, the diagonal starting at the top-right cell and ending at the center cell of the grid, or the vertical line starting at the center cell and ending at the bottom border of the grid. The Letter Y is written on the grid if and only if all values at cells belonging to the Y are equal, all values at cells not belonging to the Y are equal, and the values at cells belonging to the Y are different from the values at cells not belonging to the Y. Return the minimum number of operations needed to write the letter Y on the grid given that in one operation you can change the value at any cell to 0, 1, or 2.

Key Insights

  • The grid size is always odd, which simplifies the calculation of the center cell.
  • Cells belonging to the Y shape can be determined using their positions in relation to the center cell.
  • The problem can be divided into counting how many cells belong to the Y and how many do not.
  • We need to find the minimum changes required to make all Y cells the same value and all non-Y cells a different value.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will:

  1. Identify the positions of the cells that belong to the Letter Y based on the grid's dimensions.
  2. Count how many cells belong to the Y shape and how many do not, along with their respective values.
  3. Calculate the minimum operations needed to make all Y cells the same and all non-Y cells a different value.
  4. We can use a frequency count for each value (0, 1, 2) in both Y and non-Y cells to determine the best target values that minimize the number of operations.

Code Solutions

def min_operations_to_write_y(grid):
    n = len(grid)
    center = n // 2
    y_cells = []
    non_y_cells = []

    for r in range(n):
        for c in range(n):
            if r == c and r <= center:  # Top-left diagonal
                y_cells.append(grid[r][c])
            elif r + c == n - 1 and r <= center:  # Top-right diagonal
                y_cells.append(grid[r][c])
            elif c == center:  # Vertical line
                y_cells.append(grid[r][c])

    non_y_cells = [grid[r][c] for r in range(n) for c in range(n) if grid[r][c] not in y_cells]

    from collections import Counter
    y_count = Counter(y_cells)
    non_y_count = Counter(non_y_cells)

    # Get the most common values for y and non-y
    y_most_common = y_count.most_common()
    non_y_most_common = non_y_count.most_common()

    # Calculate the minimum operations needed
    min_operations = float('inf')

    for y_val, y_freq in y_most_common:
        for non_y_val, non_y_freq in non_y_most_common:
            if y_val != non_y_val:
                operations = (len(y_cells) - y_freq) + (len(non_y_cells) - non_y_freq)
                min_operations = min(min_operations, operations)

    return min_operations
← Back to All Questions