LeetCode 3071.Minimum Operations to Write the letter Y...

Intuition

Store counts in Y zone and store counts of rest zone. Do a nested loop to populate the counts.

Find total y cell by summing up Y zone count and total rest counts.

Store min_operation and find min_operation by brute forcing all 6 possiblities.

Since the constraint states that 0,1,2, there can be 6 possibilities where

Y -> 0 Rest -> 1

Y -> 0 Rest -> 2

Y -> 1 Rest-> 0

Y -> 1 Rest-> 2

Y -> 2 Rest-> 0

Y -> 2 Rest-> 1

Optimal Solution

class Solution:
	def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
		n = len(grid)
		mid = n // 2
		y_counts = [0] * 3
		rest_counts = [0] * 3

		for r in range(n):
			for c in range(n):
				is_y = False
				if r <= mid and r == c:
					is_y = True
				elif r <= mid and r + c == n - 1:
					is_y = True
				elif r >= mid and c == mid:
					is_y = True

				if is_y:
					y_counts[grid[r][c]] += 1
				else:
					rest_counts[grid[r][c]] += 1

		total_y_cells = sum(y_counts)
		total_rest_cells = sum(rest_counts)
		min_opa = float('inf')

		for i in range(3):
			for j in range(3):
				if i == j:
					continue
				ops = (total_y_cells - y_counts[i]) + (total_rest_cells - rest_counts[j])
				min_ops = min(min_ops, ops)

		return min_ops

Time Complexity

O(N^2) Time Complexity

O(1) Space Complexity