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

MediumArrayHash TableCountingMatrix
Leetcode Link

Problem Description

In this problem, we are provided with an odd-sized, 0-indexed n x n grid containing three possible values in each cell: 0, 1, or 2. We have to transform this grid such that it forms the letter 'Y'. A grid forms the letter 'Y' when:

  1. All cells that are part of the letter 'Y' (the two diagonals converging at the center cell from the top left and top right and the vertical line from the center down to the bottom) contain the same value.
  2. All cells that are not part of the letter 'Y' also contain the same value, which must be distinct from the value of the 'Y' cells.
  3. A cell's value can be changed to either 0, 1, or 2 in one operation.

Our goal is to find the minimum number of such operations needed to write the letter 'Y' on the grid according to these rules.

Intuition

The solution approach leverages the concept of counting and enumeration. Knowing that all cells of the 'Y' must share one value (let's call it 'i'), and all cells not a part of 'Y' must share a different value ('j'), there are limited possibilities since we have only three different values to choose from (0, 1, or 2). Moreover, when choosing a value for the 'Y' part and a different value for the non-'Y' part of the grid, these values can't be the same.

We build two count dictionaries: cnt1 keeps track of how many times each value appears within the cells that make up the letter 'Y', and cnt2 does the same for the cells outside of the letter 'Y'. Then, for each pair of values (i for the 'Y', j for the rest) we calculate the number of operations that would be needed if we chose this pair of values. This is done simply by subtracting the number of already correctly valued cells from the total cell count, which gives us the number of cells we need to change.

Eventually, we take the minimum of all possibilities where i does not equal j since, by definition, the cells that are part of 'Y' must have a different value than those that aren't. This gives us our desired minimum number of operations needed to write the letter 'Y'.

Solution Approach

The implementation of the solution follows a counting and enumeration approach as indicated in the Reference Solution Approach.

Firstly, two Counter objects from Python's collections module, cnt1 and cnt2, are used. They serve as the data structures to keep track of the frequency of each value in the cells that belong to the 'Y' (cnt1) and those that do not (cnt2).

The solution iterates over each cell in the grid using nested loops. For each cell at position (i, j), it determines if the cell belongs to the letter 'Y'. This classification is done using three conditions, indicating the cell is part of one of the three parts of the 'Y':

  • a = i == j and i <= n // 2: Checks if the cell is on the diagonal from the top-left to the center cell.
  • b = i + j == n - 1 and i <= n // 2: Checks if the cell is on the diagonal from the top-right to the center cell.
  • c = j == n // 2 and i >= n // 2: Checks if the cell is part of the vertical line from the center down.

Using logical OR (a or b or c), we can ascertain if a cell is part of the 'Y'. If it is, increment the count for the value in cnt1, otherwise in cnt2.

In the minimizing step, we generate permutations of two different values, i and j (with i != j), where i is a candidate value for 'Y' cells, and j is for the non-'Y' cells. We subtract the sum of the count of already correct 'Y' cells (cnt1[i]) and the count of already correct non-'Y' cells (cnt2[j]) from the total number of cells in the grid (n * n). This gives us the count of operations for this specific combination of values i and j.

As we want to minimize the number of operations, we take the minimum over all (i, j) pairs using a generator expression:

1min(
2    n * n - cnt1[i] - cnt2[j] for i in range(3) for j in range(3) if i != j
3)

By iterating over all value combinations and taking the minimum of the computed operations, we determine the least amount of changes needed to form the letter 'Y' on the grid according to the problem's conditions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's illustrate the solution approach using a small 3x3 grid example. Our grid looks like this:

11 0 1
20 2 0
31 0 1

Initially, we determine the 'Y' cells are located at indices (0,0), (0,2), (1,1), (2,1). The rest of the cells are not part of the 'Y'.

Now, following the solution approach:

  1. Counting Values: We use two Counter objects, cnt1 for the 'Y' and cnt2 for the non-'Y'.

    • For cnt1 ('Y' cells), the grid has:

      • Value 1 at indices (0,0) and (0,2), so cnt1[1] = 2.
      • Value 2 at index (1,1), so cnt1[2] = 1.
    • For cnt2 (non-'Y' cells), the grid has:

      • Value 0 at indices (0,1), (1,0), (1,2), and (2,0), (2,2), so cnt2[0] = 5.
      • No other values are present in the non-'Y' cells.
  2. Determining Operations: We enumerate the permutations of different values for 'Y' (i) and non-'Y' (j) from the set {0, 1, 2}, ensuring i != j. For each combination, we calculate the needed operations.

    • For i = 1 (value for 'Y') and j = 0 (value for non-'Y'):

      • Operations needed: 3 * 3 - cnt1[1] - cnt2[0] = 9 - 2 - 5 = 2.
    • Proceeding similarly for other combinations:

      • i = 1, j = 2: Operations = 9 - cnt1[1] - cnt2[2] = 9 - 2 - 0 = 7 (since cnt2[2] is not present).
      • i = 2, j = 0: Operations = 9 - cnt1[2] - cnt2[0] = 9 - 1 - 5 = 3.
      • i = 2, j = 1: Operations = 9 - cnt1[2] - cnt2[1] = 9 - 1 - 0 = 8 (since cnt2[1] is not present).
  3. Minimizing Operations: We take the smallest number of operations from the calculations. In this case, it is:

    • min(2, 7, 3, 8) = 2.

Therefore, the minimum number of operations needed to transform this 3x3 grid into the letter 'Y' is 2. We can achieve this by changing the middle element (1,1) from 2 to 1, and any of the non-'Y' elements from 0 to 1.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def minimumOperationsToWriteY(self, grid):
5        """
6        Calculate the minimum number of operations required to write the letter Y on the grid.
7      
8        Args:
9        grid (List[List[int]]): A square grid of integers.
10      
11        Returns:
12        int: The minimum number of operations needed.
13        """
14        # Get the size of the grid
15        n = len(grid)
16
17        # Initialize counters for each part of the "Y"
18        vert_horiz_counter = Counter()
19        non_Y_counter = Counter()
20
21        # Iterate over the grid to count the occurrences in the "Y" shape and elsewhere
22        for i, row in enumerate(grid):
23            for j, x in enumerate(row):
24                # Calculate which part of the grid is the 'Y' shape
25                is_vert_or_first_diag = i == j and i <= n // 2
26                is_second_diag = i + j == n - 1 and i <= n // 2
27                is_horiz_middle = j == n // 2 and i >= n // 2
28              
29                # Count the occurrences
30                if is_vert_or_first_diag or is_second_diag or is_horiz_middle:
31                    vert_horiz_counter[x] += 1
32                else:
33                    non_Y_counter[x] += 1
34
35        # Compute the minimum operations by finding max occurrence in 'Y' and outside 'Y', excluding the same number in both places
36        min_operations = min(
37            n * n - vert_horiz_counter[i] - non_Y_counter[j] 
38            for i in range(3) for j in range(3) if i != j
39        )
40
41        return min_operations
42
1class Solution {
2    // Method to calculate the minimum number of operations needed to write 'Y' on the grid
3    public int minimumOperationsToWriteY(int[][] grid) {
4        int gridSize = grid.length; // Dimension of the grid (since it's n x n)
5      
6        // Arrays to store the count of each number (0, 1, 2) in the regions that form 'Y'
7        int[] countRegionY = new int[3];
8        int[] countOutsideRegionY = new int[3];
9
10        // Loop through each cell in the grid to separate the cells that will form 'Y'
11        // and those that will not
12        for (int i = 0; i < gridSize; ++i) {
13            for (int j = 0; j < gridSize; ++j) {
14                // Conditions to detect cells that are part of 'Y'
15                boolean isDiagonalFromTopLeft = i == j && i <= gridSize / 2;
16                boolean isDiagonalFromTopRight = i + j == gridSize - 1 && i <= gridSize / 2;
17                boolean isVerticalMiddleLine = j == gridSize / 2 && i >= gridSize / 2;
18
19                if (isDiagonalFromTopLeft || isDiagonalFromTopRight || isVerticalMiddleLine) {
20                    // Increment the count for the region that forms 'Y'
21                    ++countRegionY[grid[i][j]];
22                } else {
23                    // Increment the count for the region outside 'Y'
24                    ++countOutsideRegionY[grid[i][j]];
25                }
26            }
27        }
28
29        // We'll assume the worst case where we need to change every cell initially
30        int minOperations = gridSize * gridSize;
31
32        // Evaluate all combinations where the number for region 'Y' and outside are different
33        for (int numberForY = 0; numberForY < 3; ++numberForY) {
34            for (int numberOutsideY = 0; numberOutsideY < 3; ++numberOutsideY) {
35                if (numberForY != numberOutsideY) {
36                    // Calculate the number of operations needed if these two numbers were used
37                    int operations = gridSize * gridSize - countRegionY[numberForY] - countOutsideRegionY[numberOutsideY];
38                    // Check if the current operation count is lower than the minimum found so far
39                    minOperations = Math.min(minOperations, operations);
40                }
41            }
42        }
43
44        // Return the minimum number of operations found
45        return minOperations;
46    }
47}
48
1class Solution {
2public:
3    int minimumOperationsToWriteY(vector<vector<int>>& grid) {
4        int gridSize = grid.size(); // total size of the grid (n x n)
5        int countGroupOne[3] = {0}; // frequency count of numbers in the first group (Y shape)
6        int countGroupTwo[3] = {0}; // frequency count of numbers in the second group (not Y shape)
7      
8        // Iterate through the grid and categorize elements
9        for (int i = 0; i < gridSize; ++i) {
10            for (int j = 0; j < gridSize; ++j) {
11                bool isDiagonalOne = (i == j) && (i <= gridSize / 2); // condition for main diagonal and upper half
12                bool isDiagonalTwo = (i + j == gridSize - 1) && (i <= gridSize / 2); // condition for anti-diagonal and upper half
13                bool isVerticalLine = (j == gridSize / 2) && (i >= gridSize / 2); // condition for the vertical middle line and lower half
14              
15                // Increase the correct frequency counter based on the booleans above
16                if (isDiagonalOne || isDiagonalTwo || isVerticalLine) {
17                    ++countGroupOne[grid[i][j]]; // for Y shape
18                } else {
19                    ++countGroupTwo[grid[i][j]]; // for non-Y shape
20                }
21            }
22        }
23      
24        int minimumOperations = gridSize * gridSize; // maximum number of operations (each cell made to write an element not already in the cell)
25
26        // Find the minimum number of operations by checking all combinations of colours between the groups
27        for (int i = 0; i < 3; ++i) { // iterate over possible colours for group one
28            for (int j = 0; j < 3; ++j) { // iterate over possible colours for group two
29                // Ensure we are not counting the same colour for both groups
30                if (i != j) {
31                    // Calculate operations needed to paint the current combination
32                    // And update minimumOperations if this count is lower
33                    minimumOperations = min(minimumOperations, gridSize * gridSize - countGroupOne[i] - countGroupTwo[j]);
34                }
35            }
36        }
37
38        return minimumOperations; // Return the minimum number of operations found
39    }
40};
41
1/**
2 * Calculates the minimum number of operations to write the integer 'Y'.
3 * 
4 * @param {number[][]} grid - A square grid of numbers.
5 * @return {number} The minimum number of operations to write 'Y'.
6 */
7function minimumOperationsToWriteY(grid: number[][]): number {
8    // Get the size of the grid.
9    const gridSize = grid.length;
10
11    // Initialize counters for the number collections.
12    const crossCounters: number[] = Array(3).fill(0);
13    const otherCounters: number[] = Array(3).fill(0);
14  
15    // Loop through the grid to count occurrences.
16    for (let i = 0; i < gridSize; ++i) {
17        for (let j = 0; j < gridSize; ++j) {
18            // Check if the current cell is part of the cross (Y shape).
19            const onFirstDiagonal = i === j && i <= gridSize >> 1;
20            const onSecondDiagonal = i + j === gridSize - 1 && i <= gridSize >> 1;
21            const onMiddleColumn = j === gridSize >> 1 && i >= gridSize >> 1;
22
23            // Update the corresponding counters based on the cell's position.
24            if (onFirstDiagonal || onSecondDiagonal || onMiddleColumn) {
25                ++crossCounters[grid[i][j]];
26            } else {
27                ++otherCounters[grid[i][j]];
28            }
29        }
30    }
31
32    // Initialize the answer with the maximum possible number of operations.
33    let minimumOperations = gridSize * gridSize;
34
35    // Determine the minimum operations required by trying all combinations of numbers.
36    for (let i = 0; i < 3; ++i) {
37        for (let j = 0; j < 3; ++j) {
38            // We want to use different numbers for the cross and the other cells.
39            if (i !== j) {
40                // Calculate the minimum operations by subtracting the already correct cells.
41                minimumOperations = Math.min(
42                    minimumOperations,
43                    gridSize * gridSize - crossCounters[i] - otherCounters[j]
44                );
45            }
46        }
47    }
48
49    // Return the calculated minimum operations.
50    return minimumOperations;
51}
52

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n^2). This is because the nested for-loops iterate over the entire grid, which is of size n x n. The operations inside the for-loops are constant time operations, causing the overall time to be proportional to the number of elements in the grid.

Space Complexity

The space complexity of the code is higher than O(1) mentioned in the reference answer. It actually depends on the range of the elements in the grid. The two counters cnt1 and cnt2 are used to count occurrences of elements that satisfy certain conditions. Because Python's Counter is essentially a hash map, the space used by these counters will increase with the variety of elements in the grid. Assuming the range of numbers in the grid is k, the space complexity would be O(k). If we were to consider k as being a constant because the problem might define a limit on the values of grid elements, then we could consider the space complexity to be O(1). Without such a constraint being specified, the space complexity is not strictly constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄