3404. Minimum Number of Operations to Satisfy Conditions

My accepted Python solution to LeetCode problem 3404, Minimum Number of Operations to Satisfy Conditions, running in 171ms.

Medium

Python

Runtime 171ms

Memory 53.4MB

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 171ms, memory 53.4MB, accepted 2026-01-01.

python

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # Count frequency of each value (0-9) in each column
        count = [[0] * 10 for _ in range(n)]
        for j in range(n):
            for i in range(m):
                count[j][grid[i][j]] += 1
        
        # dp[j][v] = min operations to make columns 0..j valid with column j having value v
        INF = float('inf')
        
        # For single column, no adjacent constraint
        if n == 1:
            return m - max(count[0])
        
        # Initialize dp for first column
        dp = [[INF] * 10 for _ in range(n)]
        for v in range(10):
            dp[0][v] = m - count[0][v]
        
        # Fill dp for remaining columns
        for j in range(1, n):
            # Find minimum and second minimum from previous column
            prev_vals = [(dp[j-1][v], v) for v in range(10)]
            prev_vals.sort()
            min1_cost, min1_val = prev_vals[0]
            min2_cost, _ = prev_vals[1]
            
            for v in range(10):
                cost_to_make_v = m - count[j][v]
                # If v is different from min1_val, use min1_cost
                if v != min1_val:
                    dp[j][v] = min1_cost + cost_to_make_v
                else:
                    # Use second minimum
                    dp[j][v] = min2_cost + cost_to_make_v
        
        return min(dp[n-1])

Python#

Source#

Python

Source