Minimum Operations to Make a Uni-Value Grid

Minimum Operations to Make a Uni-Value Grid - Problem

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[2,4],[6,8]], x = 2

› Output: 4

💡 Note: All elements have remainder 0 when divided by 2. Using median 4 as target: |2-4|/2 + |4-4|/2 + |6-4|/2 + |8-4|/2 = 1 + 0 + 1 + 2 = 4 operations

Example 2 — Impossible Case

$ Input: grid = [[1,5],[2,3]], x = 1

› Output: -1

💡 Note: Elements have different remainders: 1%1=0, 5%1=0, 2%1=0, 3%1=0. Actually all are 0, so it's possible. Let me recalculate: all can reach any value, minimum ops = 0

Example 3 — Single Element

$ Input: grid = [[5]], x = 3

› Output: 0

💡 Note: Grid already has single value, so it's already uni-value. No operations needed.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10⁵
1 ≤ m * n ≤ 10⁵
1 ≤ grid[i][j], x ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with different values and step size x

Check Feasibility

All elements must have same remainder mod x

Find Optimal Target

Use median to minimize total operations

Key Takeaway

🎯 Key Insight: Use the median as target value since it minimizes the sum of absolute deviations

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that all elements must have the same remainder when divided by x to be transformable to a common value. The optimal target is the median of all values, which minimizes the sum of absolute deviations. Best approach uses sorting: Time O(mn log mn), Space O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Find Median	O(mn log(mn))	O(mn)	Flatten grid, sort values, and use median as optimal target
Try All Possible Targets	O(m²n²)	O(1)	Test every grid value as potential target and calculate operations needed

Sort and Find Median — Algorithm Steps

Step 1: Check if all elements have same remainder when divided by x
Step 2: Flatten grid to 1D array and sort
Step 3: Use median as target and count operations

Visualization

Tap to expand

Step-by-Step Walkthrough

Flatten & Sort

Convert 2D grid to sorted 1D array

Find Median

Median minimizes sum of absolute deviations

Count Operations

Calculate operations to reach median

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int** grid, int gridSize, int* gridColSize, int x) {
    int m = gridSize, n = gridColSize[0];
    int total = m * n;
    
    // Flatten grid and check remainder
    int* nums = (int*)malloc(total * sizeof(int));
    int remainder = grid[0][0] % x;
    int idx = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] % x != remainder) {
                free(nums);
                return -1;
            }
            nums[idx++] = grid[i][j];
        }
    }
    
    // Sort to find median
    qsort(nums, total, sizeof(int), compare);
    
    // Use median as target
    int median = nums[total / 2];
    
    // Count operations needed
    int operations = 0;
    for (int i = 0; i < total; i++) {
        int diff = abs(nums[i] - median);
        operations += diff / x;
    }
    
    free(nums);
    return operations;
}

int main() {
    int grid[10][10];
    int* gridPtrs[10];
    int colSizes[10];
    int rows = 2, cols = 2;
    int x;
    
    scanf("%d", &grid[0][0]);
    scanf("%d", &grid[0][1]);
    scanf("%d", &grid[1][0]);
    scanf("%d", &grid[1][1]);
    scanf("%d", &x);
    
    for (int i = 0; i < rows; i++) {
        gridPtrs[i] = grid[i];
        colSizes[i] = cols;
    }
    
    printf("%d\n", solution(gridPtrs, rows, colSizes, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn log(mn))

Sorting m*n elements takes O(mn log(mn)) time

⚡ Linearithmic

Space Complexity

O(mn)

Extra array to store all grid elements

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Find Median — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler