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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Write the Letter Y on a Grid

Number: 3335

Difficulty: Medium

Paid? No

Companies: Uber, Capital One, Zeta

Problem Description

Given an odd-sized n x n grid (with 0-indexing) where each cell contains 0, 1, or 2, determine the minimum number of operations required to “write” the letter Y on the grid. The letter Y consists of:

  • The diagonal from the top-left to the center.
  • The diagonal from the top-right to the center.
  • The vertical line from the center to the bottom.
    The grid is valid if:
  • All cells that are part of the Y have the same value.
  • All cells not part of the Y have the same (but different) value. An operation consists of changing the value in any cell to 0, 1, or 2.

Key Insights

  • The grid is divided into two groups: the Y shape cells and the background cells.
  • The Y shape is defined by two diagonals (from the top-left and top-right converging at the center) and a vertical stem from the center to the bottom.
  • There are only 3 possible values and the Y and background must have different values. Thus, try all candidate pairs (letter, background) with letter ≠ background.
  • For each candidate pair, count the number of changes required in the Y cells (to match the candidate letter value) and in the non-Y cells (to match the candidate background value), then choose the minimum.
  • Since the grid size is relatively small (n ≤ 49), iterating over all cells for a constant number of candidate pairs is efficient.

Space and Time Complexity

Time Complexity: O(n^2) — We loop over all cells for a constant number (6) of candidate configurations. Space Complexity: O(n^2) in the worst case if we store a set or boolean matrix to mark the Y shape; however, this is acceptable given the constraints.

Solution

We start by identifying all cells that belong to the Y shape. The Y shape is formed by:

  1. The main diagonal from (0,0) to the center (n//2, n//2).
  2. The anti-diagonal from (0, n-1) to the center.
  3. The vertical line from the center to the bottom row. Next, for every possible pair of distinct values (letter and background) from {0, 1, 2}, we:
  • Count operations needed to change cells in the Y shape to the candidate letter value.
  • Count operations needed to change cells outside the Y shape to the candidate background value. Finally, we return the minimum operations among all candidate pairs.
    The key trick is correctly identifying the Y shape without double counting (using a set or boolean matrix) and then iterating over the grid for each of the 6 candidate pairs.

Code Solutions

def minOperations(grid):
    n = len(grid)
    center = n // 2
    # Use a set to mark all positions belonging to the letter Y
    y_positions = set()
    # Mark the main diagonal (top-left to center)
    for i in range(center + 1):
        y_positions.add((i, i))
    # Mark the anti-diagonal (top-right to center)
    for i in range(center + 1):
        y_positions.add((i, n - 1 - i))
    # Mark the vertical stem (center to bottom)
    for i in range(center, n):
        y_positions.add((i, center))
    
    min_ops = float('inf')
    # Try all candidate pairs for letter value and background value
    for letter_val in range(3):
        for back_val in range(3):
            if letter_val == back_val:
                continue
            ops = 0
            # Iterate over every cell in the grid
            for r in range(n):
                for c in range(n):
                    if (r, c) in y_positions:
                        # For cells in Y, the value must be letter_val
                        if grid[r][c] != letter_val:
                            ops += 1
                    else:
                        # For non-Y cells, the value must be back_val
                        if grid[r][c] != back_val:
                            ops += 1
            min_ops = min(min_ops, ops)
    return min_ops

# Example usage:
print(minOperations([[1,2,2],[1,1,0],[0,1,0]]))
← Back to All Questions