Minimum Operations to Write the Letter Y on a Grid

Minimum Operations to Write the Letter Y on a Grid - Problem

You are given a 0-indexed n × 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
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
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.

Input & Output

Example 1 — Basic 3x3 Grid

$ Input: grid = [[1,2,2],[1,1,0],[0,1,0]]

› Output: 3

💡 Note: Y cells are at positions (0,0), (0,2), (1,1), (2,1). To minimize operations, set Y=1 and non-Y=0. Need to change 3 non-Y cells: (0,1) from 2→0, (1,0) from 1→0, (1,2) from 0→0 (no change), (2,0) from 0→0, (2,2) from 0→0. Actually need to change (0,1) and (1,0) and (1,2), total 3 operations.

Example 2 — Uniform Values

$ Input: grid = [[2,1,0],[1,0,1],[0,1,2]]

› Output: 6

💡 Note: Y cells: (0,0)=2, (0,2)=0, (1,1)=0, (2,1)=1. Non-Y cells: (0,1)=1, (1,0)=1, (1,2)=1, (2,0)=0, (2,2)=2. Best assignment requires changing most cells to achieve uniform regions.

Example 3 — Already Optimal

$ Input: grid = [[0,1,0],[1,0,1],[1,0,1]]

› Output: 1

💡 Note: Y cells: (0,0)=0, (0,2)=0, (1,1)=0, (2,1)=0. Non-Y: (0,1)=1, (1,0)=1, (1,2)=1, (2,0)=1, (2,2)=1. Y=0, Non-Y=1 is already mostly correct, need only 1 change.

Constraints

n == grid.length == grid[i].length
3 ≤ n ≤ 49
n is odd
grid[i][j] is either 0, 1, or 2

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3×3 grid with values 0, 1, 2

Identify Y

Mark cells forming Y pattern

Optimize Assignment

Find best color combo for minimum operations

Key Takeaway

🎯 Key Insight: With only 3 possible values, we can exhaustively try all valid Y vs non-Y color combinations in constant time

Asked in

G Google 12 f Meta 8 a Amazon 6

The key insight is that we only have 3 possible values (0,1,2) and need Y cells to have one value while non-Y cells have a different value. We can try all 6 valid combinations (Y_val ≠ non_Y_val) and count operations for each. Best approach uses frequency counting to optimize the calculation. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Try All Color Combinations	O(n²)	O(n²)	Try all 9 possible combinations of Y-color vs non-Y-color
Frequency Counting Optimization	O(n²)	O(1)	Count frequencies of values in Y and non-Y regions, then find optimal assignment

Try All Color Combinations — Algorithm Steps

Step 1: Identify all cells that belong to the Y pattern
Step 2: Try all 9 combinations of (Y_value, non_Y_value) where Y_value ≠ non_Y_value
Step 3: For each combination, count operations needed to convert all Y cells to Y_value and all non-Y cells to non_Y_value

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Y Pattern

Mark cells belonging to Y (diagonals + vertical)

Try Combinations

Test all 6 valid (Y_color, non_Y_color) pairs

Count Operations

Find minimum operations needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** grid, int n) {
    int center = n / 2;
    
    // Mark cells that belong to Y
    int** isY = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        isY[i] = (int*)calloc(n, sizeof(int));
    }
    
    // Top-left to center diagonal
    for (int i = 0; i <= center; i++) {
        isY[i][i] = 1;
    }
    
    // Top-right to center diagonal
    for (int i = 0; i <= center; i++) {
        isY[i][n - 1 - i] = 1;
    }
    
    // Center to bottom vertical line
    for (int i = center; i < n; i++) {
        isY[i][center] = 1;
    }
    
    int minOps = INT_MAX;
    
    // Try all combinations of Y value and non-Y value
    for (int yVal = 0; yVal < 3; yVal++) {
        for (int nonYVal = 0; nonYVal < 3; nonYVal++) {
            if (yVal == nonYVal) continue;
            
            int ops = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (isY[i][j]) {
                        if (grid[i][j] != yVal) ops++;
                    } else {
                        if (grid[i][j] != nonYVal) ops++;
                    }
                }
            }
            
            if (ops < minOps) {
                minOps = ops;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(isY[i]);
    }
    free(isY);
    
    return minOps;
}

int main() {
    // Simple parsing for this problem - assume small grid
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Count dimensions
    int n = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && line[i+1] != '[') n++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Simple parsing - extract numbers
    int nums[100], numCount = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] >= '0' && line[i] <= '2') {
            nums[numCount++] = line[i] - '0';
        }
    }
    
    int idx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = nums[idx++];
        }
    }
    
    int result = solution(grid, n);
    printf("%d\n", result);
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We iterate through the n×n grid to identify Y cells once, then 9 times to count operations for each combination

⚠ Quadratic Growth

Space Complexity

O(n²)

We store boolean flags for each cell to mark if it belongs to Y pattern

⚠ Quadratic Space

8.9K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Color Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler