3071. Minimum Operations to Write the Letter Y on a Grid (Array, Hash Table, Matrix, Counting)

링크 - https://leetcode.com/problems/minimum-operations-to-write-the-letter-y-on-a-grid/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

 

Code

class Solution:
    def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
        n = len(grid)
        
        y_area = 2* (n//2) + (n//2 + 1)
        others_area = n*n - y_area
        counter_y = defaultdict(int)
        counter_others = defaultdict(int)

        for i in range(n):
            for j in range(n):
                counter_others[grid[i][j]] += 1

        # The diagoanl starting at the top-left cell
        for i in range(n//2):
            counter_y[grid[i][i]] += 1
            counter_others[grid[i][i]] -= 1

        # The diagoanl starting at the top-right cell
        for i in range(n//2):
            counter_y[grid[i][n-i-1]] += 1
            counter_others[grid[i][n-i-1]] -= 1

        # The vertical line starting at the center cell
        for i in range(n//2, n):
            counter_y[grid[i][n//2]] += 1
            counter_others[grid[i][n//2]] -= 1

        ans = float('inf')
        for y in [0,1,2]:
            for o in [0,1,2]:
                if y == o:
                    continue
                y_to_change = y_area - counter_y[y]
                others_to_change = others_area - counter_others[o]
                ans = min(ans, y_to_change + others_to_change)

        return ans

Complexity

Time Complexity: O(N^2)

Space Complexity: O(1)