3888. Minimum Operations to Make All Grid Elements Equal 🔒

Description

You are given a 2D integer array grid of size m × n, and an integer k.

In one operation, you can:

Select any k x k submatrix of grid, and
Increment all elements inside that submatrix by 1.

Return the minimum number of operations required to make all elements in the grid equal. If it is not possible, return -1.

A submatrix (x1, y1, x2, y2) is a matrix that forms by choosing all cells matrix[x][y] where x1 <= x <= x2 and y1 <= y <= y2.

Example 1:

Input: grid = [[3,3,5],[3,3,5]], k = 2

Output: 2

Explanation:

Choose the left 2 x 2 submatrix (covering the first two columns) and apply the operation twice.

After 1 operation: [[4, 4, 5], [4, 4, 5]]
After 2 operations: [[5, 5, 5], [5, 5, 5]]

All elements become equal to 5. Thus, the minimum number of operations is 2.

Example 2:

Input: grid = [[1,2],[2,3]], k = 1

Output: 4

Explanation:

Since k = 1, each operation increments a single cell grid[i][j] by 1. To make all elements equal, the final value must be 3.

Increase grid[0][0] = 1 to 3, requiring 2 operations.
Increase grid[0][1] = 2 to 3, requiring 1 operation.
Increase grid[1][0] = 2 to 3, requiring 1 operation.

Thus, the minimum number of operations is 2 + 1 + 1 + 0 = 4.

Constraints:

1 <= m == grid.length <= 1000
1 <= n == grid[i].length <= 1000
-10⁵ <= grid[i][j] <= 10⁵
1 <= k <= min(m, n)

Solutions

Solution 1: 2D Difference Array + Greedy

Since the operation can only increase the value of elements, all elements in the final grid must be equal to some target value \(T\), and \(T \ge \max(\textit{grid})\).

Start traversing the grid from the top-left corner \((0, 0)\). For any position \((i, j)\), if its current value is less than \(T\), since subsequent operations (with a more rightward or downward position as the top-left corner) cannot cover \((i, j)\), it is necessary to perform \(T - \text{current\_val}\) operations at the current position, each using \((i, j)\) as the top-left corner of a \(k \times k\) increment operation.

If each operation traverses the \(k \times k\) region, the complexity will reach \(O(m \cdot n \cdot k^2)\). We can use a 2D difference array \(\textit{diff}\) to record the operations. By maintaining the 2D prefix sum of \(\textit{diff}\) in real time, we can obtain the cumulative increment at the current position in \(O(1)\) time, and update the future impact of a \(k \times k\) region in \(O(1)\) time.

In most cases, \(T = \max(\textit{grid})\) is sufficient. However, in some cases where \(k \times k\) regions overlap, a smaller \(T\) may cause the middle positions to be passively increased beyond \(T\). According to mathematical consistency, if both \(T = \max(\textit{grid})\) and \(T = \max(\textit{grid}) + 1\) are not feasible, then it is impossible to flatten the grid using \(k \times k\) operations.

The time complexity is \(O(m \times n)\) and the space complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the grid, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def minOperations(self, grid: list[list[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        mx = max(max(row) for row in grid)

        def check(target: int) -> int:
            diff = [[0] * (n + 2) for _ in range(m + 2)]
            total_ops = 0

            for i, row in enumerate(grid, 1):
                for j, val in enumerate(row, 1):
                    diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]

                    cur_val = val + diff[i][j]

                    if cur_val > target:
                        return -1

                    if cur_val < target:
                        if i + k - 1 > m or j + k - 1 > n:
                            return -1

                        needed = target - cur_val
                        total_ops += needed
                        diff[i][j] += needed
                        diff[i + k][j] -= needed
                        diff[i][j + k] -= needed
                        diff[i + k][j + k] += needed
            return total_ops

        for t in range(mx, mx + 2):
            res = check(t)
            if res != -1:
                return res

        return -1

class Solution {
    int[][] grid;
    int m, n, k;

    public long minOperations(int[][] grid, int k) {
        this.grid = grid;
        this.k = k;
        this.m = grid.length;
        this.n = grid[0].length;

        int mx = Integer.MIN_VALUE;
        for (int[] row : grid) {
            for (int v : row) {
                mx = Math.max(mx, v);
            }
        }

        for (int t = mx; t <= mx + 1; t++) {
            long res = check(t);
            if (res != -1) {
                return res;
            }
        }
        return -1;
    }

    private long check(int target) {
        long[][] diff = new long[m + 2][n + 2];
        long totalOps = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                long cur = grid[i - 1][j - 1] + diff[i][j];

                if (cur > target) {
                    return -1;
                }

                if (cur < target) {
                    if (i + k - 1 > m || j + k - 1 > n) {
                        return -1;
                    }

                    long need = target - cur;
                    totalOps += need;

                    diff[i][j] += need;
                    diff[i + k][j] -= need;
                    diff[i][j + k] -= need;
                    diff[i + k][j + k] += need;
                }
            }
        }
        return totalOps;
    }
}

class Solution {
public:
    long long minOperations(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int mx = grid[0][0];
        for (auto& row : grid) {
            for (int val : row) {
                mx = max(mx, val);
            }
        }

        auto check = [&](int target) -> long long {
            vector<vector<long long>> diff(m + 2, vector<long long>(n + 2, 0));
            long long total_ops = 0;

            for (int i = 1; i <= m; ++i) {
                for (int j = 1; j <= n; ++j) {
                    diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                    long long cur_val = grid[i - 1][j - 1] + diff[i][j];

                    if (cur_val > target) {
                        return -1;
                    }

                    if (cur_val < target) {
                        if (i + k - 1 > m || j + k - 1 > n) {
                            return -1;
                        }

                        long long needed = target - cur_val;
                        total_ops += needed;
                        diff[i][j] += needed;
                        diff[i + k][j] -= needed;
                        diff[i][j + k] -= needed;
                        diff[i + k][j + k] += needed;
                    }
                }
            }

            return total_ops;
        };

        for (int t = mx; t <= mx + 1; ++t) {
            long long res = check(t);
            if (res != -1) {
                return res;
            }
        }

        return -1;
    }
};

func minOperations(grid [][]int, k int) int64 {
    m, n := len(grid), len(grid[0])
    maxVal := grid[0][0]
    for _, row := range grid {
        maxVal = max(maxVal, slices.Max(row))
    }

    check := func(target int) int64 {
        diff := make([][]int64, m+2)
        for i := range diff {
            diff[i] = make([]int64, n+2)
        }
        var totalOps int64

        for i := 1; i <= m; i++ {
            for j := 1; j <= n; j++ {
                diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]
                curVal := int64(grid[i-1][j-1]) + diff[i][j]

                if curVal > int64(target) {
                    return -1
                }

                if curVal < int64(target) {
                    if i+k-1 > m || j+k-1 > n {
                        return -1
                    }
                    needed := int64(target) - curVal
                    totalOps += needed
                    diff[i][j] += needed
                    diff[i+k][j] -= needed
                    diff[i][j+k] -= needed
                    diff[i+k][j+k] += needed
                }
            }
        }
        return totalOps
    }

    for t := maxVal; t <= maxVal+1; t++ {
        if res := check(t); res != -1 {
            return res
        }
    }

    return -1
}

function minOperations(grid: number[][], k: number): number {
    const m = grid.length;
    const n = grid[0].length;
    let maxVal = grid[0][0];

    for (const row of grid) {
        for (const val of row) {
            maxVal = Math.max(maxVal, val);
        }
    }

    const check = (target: number): number => {
        const diff: number[][] = Array.from({ length: m + 2 }, () => Array(n + 2).fill(0));
        let totalOps = 0;

        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                const curVal = grid[i - 1][j - 1] + diff[i][j];

                if (curVal > target) return -1;

                if (curVal < target) {
                    if (i + k - 1 > m || j + k - 1 > n) return -1;

                    const needed = target - curVal;
                    totalOps += needed;
                    diff[i][j] += needed;
                    diff[i + k][j] -= needed;
                    diff[i][j + k] -= needed;
                    diff[i + k][j + k] += needed;
                }
            }
        }

        return totalOps;
    };

    for (let t = maxVal; t <= maxVal + 1; t++) {
        const res = check(t);
        if (res !== -1) return res;
    }

    return -1;
}

3888. Minimum Operations to Make All Grid Elements Equal 🔒

Description

Solutions

Solution 1: 2D Difference Array + Greedy

Comments