[BUG] - One of the tests broke

LeetCode Username

november-yankee

Problem Number, Title, and Link

Minimum Number of Operations to Satisfy Conditions https://leetcode.com/problems/minimum-number-of-operations-to-satisfy-conditions

Bug Category

Incorrect test case (Output of test case is incorrect as per the problem statement)

Bug Description

Test case 629 broke (my solution used to pass for it)

If the grid satisfied the conditions, columns would alternate between 0 and 1

I've created counters for each column. The minimum number of operations is 495, not the 474 the test is expecting

Language Used for Code

None

Code used for Submit/Run operation

# Note that both `mo` and `minimum_operations` return `495`

from collections import Counter
from typing import Any, Callable, List, Tuple

Column = List
Row = List
Grid = Column[Row[int]]

max_ops = 1000 ** 2

def memoize(function: Callable):
    memo = {}

    def wrapper(*args: List[Any]):
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper

class Solution:
    col_num_counters: List[Counter]
    n_rows: int

    def __init__(self):
        self.col_num_counters = []

    def minimum_operations(self, col: int, exclude_num: int = -1) -> int:
        result = max_ops

        col_num_counter = self.col_num_counters[col]

        min_ops = lambda _: 0
        if col < len(self.col_num_counters) - 1:
            min_ops = lambda _exclude_num: self.minimum_operations(col + 1, _exclude_num)

        for num in col_num_counter:
            if num != exclude_num:
                result = min(
                    result,
                    self.n_rows - col_num_counter[num] + min_ops(num))
            elif col_num_counter[num] == self.n_rows:
                result = self.n_rows + min_ops(num)

        return result

    @memoize
    def count_not_equals(self, column: Tuple, num: int) -> int:
        result = 0

        for n in column:
            if n != num:
                result += 1

        return result

    @memoize
    def mo(self, transposed_grid: Tuple[Tuple], exclude_num: int = -1) -> int:
        result = max_ops

        column = transposed_grid[0]

        min_ops = lambda _: 0
        if len(transposed_grid) > 1:
            min_ops = lambda _exclude_num: self.mo(transposed_grid[1:], _exclude_num)

        for num in column:
            if num != exclude_num:
                result = min(
                    result,
                    self.count_not_equals(column, num) + min_ops(num)
                )
            elif self.count_not_equals(column, num) == 0:
                result = self.n_rows + min_ops(num)

        return result

    def minimumOperations(self, grid: Grid) -> int:
        self.n_rows = len(grid)
        n_cols = len(grid[0])

        transposed_grid = tuple(zip(*grid))

        # return self.mo(transposed_grid)

        self.col_num_counters = []

        for col in range(n_cols):
            self.col_num_counters.append(Counter([grid[row][col] for row in range(len(grid))]))

        r = 0
        for i, cnc in enumerate(self.col_num_counters):
            r += cnc[i % 2]
        print(f"{r}\n")

        r = 0
        for i, cnc in enumerate(self.col_num_counters):
            r += cnc[(i + 1) % 2]
        print(f"{r}\n")

        return self.minimum_operations(0)

Expected behavior

Test passes with both mo and minimum_operations implementations

Screenshots

Screenshot 2024-11-29 at 17 32 22

Additional context

No response

LeetCode-Feedback / LeetCode-Feedback

[BUG] - One of the tests broke #25606