2033. Minimum Operations to Make a Uni-Value Grid


Problem Description

The problem presents us with a two-dimensional grid of integers and a single integer x. The operation that can be executed involves adding or subtracting x to any element in the grid. A uni-value grid is defined as a grid where all elements are equal. The goal is to determine the minimum number of such operations required to turn the input grid into a uni-value grid. If this objective is unattainable, the function should return -1.

The critical constraint to keep in mind is that all elements in the final uni-value grid must be equal, which implies that the difference between any two given elements in the original grid must be a multiple of x. Otherwise, it would be impossible to reach a common value through the given operation.

Intuition

To arrive at the minimum number of operations needed to achieve a uni-value grid, we need to find a target value that all elements in the grid will be equal to after the operations. Since adding or subtracting x continues to maintain the same remainder when any element is divided by x, all elements must share the same remainder mod when divided by x; otherwise, there's no legal operation that will create a uni-value grid.

Given that all elements can be modified to share the same remainder when divided by x, the next step is to decide on which value to set all elements to. A natural choice is the median of all values, as it minimizes the absolute deviation sum for a set of numbers. In other words, using the median value as a target implies the least total difference between each number and the median, hence requiring the fewest operations.

The solution approach follows these steps:

  1. Flatten the grid into a list nums, to work with a single-dimensional array of all the values.
  2. Check if all elements have the same remainder when divided by x. If not, return -1.
  3. Sort nums and find the median value.
  4. Sum the absolute division (//) of differences between each element in nums and the median by x. This represents the minimum number of operations to adjust each element to make the entire grid uni-value.

This solution is efficient as it minimally processes the elements by using their inherent properties (specifically, the remainder upon division) and statistical measures (median) to determine feasibility and achieve optimality for the problem.

Learn more about Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution approach for converting the grid to a uni-value grid with a minimum number of operations follows a simple but powerful statistical concept. Here is the breakdown of the implementation steps, referencing the provided Python code:

  1. Flatten the Grid: The first step involves transforming the two-dimensional grid into a one-dimensional array (list). This is achieved by defining an empty list nums and iterating over each row and within that, each value v, to append it to nums.

  2. Check Modulo Condition: Before proceeding, we need to guarantee that all elements can be adjusted to the same value using the given operation. For this purpose, we store the remainder of the first grid element (e.g., grid[0][0] % x) in mod and then check if v % x == mod for all elements in the grid. If any element doesn't satisfy this, it's impossible to reach a uni-value grid, and the function immediately returns -1.

  3. Sort and Find Median: Once we have a flat list nums of all values, we sort it to arrange the numbers in ascending order. Finding the median is straightforward from this sorted list; it's the middle value, which minimizes the total number of operations needed. If the list's length is even, either of the two middle values will work due to the way the median minimizes the sum of absolute deviations. The median is found using nums[len(nums) >> 1], which is an efficient way to calculate the median index (the same as len(nums) // 2).

  4. Calculate Total Operations: Finally, we calculate the total number of operations needed by summing the integer division of absolute differences between each element and the median, divided by x (i.e., sum(abs(v - mid) // x for v in nums)). This represents how many times we'd need to add or subtract x to/from each element to convert it into the median value.

  5. Return Result: The result of the sum is the minimum number of operations required to make the grid uni-value, which is what the function returns.

In terms of algorithms and patterns, the problem mainly relies on the properties of numbers (divisibility and modulo operation), and the use of sorting and median as a means to minimize absolute differences. No complex data structures are used beyond the one-dimensional list for sorting and iteration, and the algorithm overall exhibits a time complexity effectively determined by the sorting step, which is typically O(N log N) where N is the number of elements in the grid.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's consider a two-dimensional grid and an integer x with the following values:

1Grid: [[2, 4], [6, 8]]
2x: 2

We want to convert the given grid into a uni-value grid using the minimum number of operations where we can add or subtract x to any element.

Following the solution approach:

  1. Flatten the Grid: We transform our two-dimensional grid into a one-dimensional list nums. After flattening, nums will be [2, 4, 6, 8].

  2. Check Modulo Condition: We check if all elements have the same remainder when divided by x. For our grid, all elements (2 % 2, 4 % 2, 6 % 2, 8 % 2) have a remainder of 0 when divided by 2. Since they all have the same remainder, we can proceed.

  3. Sort and Find Median: We sort the list nums to get [2, 4, 6, 8]. The length of the list is 4 (even), so the median could be either of the two middle values, 4 or 6. Here we'll choose 4 as the median (nums[4 // 2]).

  4. Calculate Total Operations: We calculate the number of operations needed to transform each element into the median. For every element v in nums, we calculate abs(v - median) // x and sum these values up:

    • For 2: abs(2 - 4) // 2 equals 1 operation.
    • For 4: abs(4 - 4) // 2 equals 0 operations.
    • For 6: abs(6 - 4) // 2 equals 1 operation.
    • For 8: abs(8 - 4) // 2 equals 2 operations.

    Summing these up gives us 1 + 0 + 1 + 2 = 4 operations.

  5. Return Result: The minimum number of operations required to make the grid uni-value is 4. This is the final result we return.

Through these steps, we've used a statistical approach (median) alongside modulo operations to efficiently determine the required operations to reach a uni-value grid, ensuring that the chosen operations are valid and minimal.

Solution Implementation

1class Solution:
2    def minOperations(self, grid, x):
3        """
4        Determine the minimum number of operations required to make all elements in the grid equal,
5        where in one operation you can add or subtract `x` to any element in the grid.
6      
7        :param grid: List[List[int]]
8        :param x: int
9        :return: int, the minimum number of operations or -1 if it's not possible
10        """
11      
12        # Flatten the grid into a single sorted list to make it easier to handle
13        flattened_grid = []
14      
15        # Start by storing the remainder of the first element (for modulo comparison)
16        required_modulo = grid[0][0] % x
17      
18        # Iterate through the grid
19        for row in grid:
20            for value in row:
21              
22                # If the current value cannot be achieved by any number of operations,
23                # we return -1 because the whole grid cannot be equalized
24                if value % x != required_modulo:
25                    return -1
26              
27                # Otherwise, store the value in our flattened grid
28                flattened_grid.append(value)
29      
30        # Sort all values in our list to easily find the median
31        flattened_grid.sort()
32
33        # Find the median, which will be our target value
34        median = flattened_grid[len(flattened_grid) // 2]
35      
36        # Calculate the sum of operations required to make all values equal to the median
37        operations = sum(abs(value - median) // x for value in flattened_grid)
38      
39        # Return the total number of operations
40        return operations
41
42# Example usage:
43# solution = Solution()
44# grid = [[1, 5], [2, 3]]
45# x = 1
46# print(solution.minOperations(grid, x)) # Outputs the minimum number of operations required
47
1class Solution {
2    public int minOperations(int[][] grid, int x) {
3        // Get the number of rows
4        int rows = grid.length;
5        // Get the number of columns
6        int cols = grid[0].length;
7        // Initialize an array to store all elements in the grid
8        int[] flattenedGrid = new int[rows * cols];
9        // Modulo of the first element in the grid. All other elements should have the same modulo if a solution is possible
10        int initialMod = grid[0][0] % x;
11      
12        // Flatten the 2D grid into a 1D array while checking if operation is not possible
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < cols; ++j) {
15                // If any element has a different modulo than the first element, return -1 as it's not possible to make them all equal
16                if (grid[i][j] % x != initialMod) {
17                    return -1;
18                }
19                // Store elements of the grid in the flattened 1D array
20                flattenedGrid[i * cols + j] = grid[i][j];
21            }
22        }
23      
24        // Sort the flattened 1D array
25        Arrays.sort(flattenedGrid);
26        // Find the median element
27        int median = flattenedGrid[flattenedGrid.length / 2];
28        // Initialize operation count to 0
29        int operationCount = 0;
30      
31        // Calculate the total number of operations required to make all elements equal to the median
32        for (int value : flattenedGrid) {
33            // Increment the operation count by the number of operations needed for each element.
34            // The distance between the element and the median is divided by x 
35            // as that's the number of operations required to make them equal
36            operationCount += Math.abs(value - median) / x;
37        }
38      
39        // Return the total operation count
40        return operationCount;
41    }
42}
43
1class Solution {
2public:
3    int minOperations(vector<vector<int>>& grid, int x) {
4        // Calculate the dimensions of the grid
5        int rows = grid.size();
6        int cols = grid[0].size();
7      
8        // Determine the modulo of the first element as a reference
9        int referenceModulo = grid[0][0] % x;
10      
11        // Flatten the grid into a single vector for ease of manipulation
12        vector<int> flattenedGrid(rows * cols);
13      
14        // Process the grid while checking if it's possible to make all elements equal
15        for (int i = 0; i < rows; ++i) {
16            for (int j = 0; j < cols; ++j) {
17                // If an element's modulo isn't equal to the reference, it's not possible to make all elements equal
18                if (grid[i][j] % x != referenceModulo) {
19                    return -1;
20                }
21                // Populate the flattened grid
22                flattenedGrid[i * cols + j] = grid[i][j];
23            }
24        }
25      
26        // Sort the flattened grid to find the median
27        sort(flattenedGrid.begin(), flattenedGrid.end());
28      
29        // The median value is the target value for all elements to make them equal
30        int targetValue = flattenedGrid[(rows * cols) / 2];
31      
32        // Calculate the total number of operations needed
33        int totalOps = 0;
34        for (int value : flattenedGrid) {
35            // Add the required number of operations per element
36            totalOps += abs(value - targetValue) / x;
37        }
38      
39        // Return the total number of operations
40        return totalOps;
41    }
42};
43
1// Function to find the minimum number of operations needed to make all elements of a grid equal.
2function minOperations(grid: number[][], x: number): number {
3    // Calculate the dimensions of the grid
4    let rows = grid.length;
5    let cols = grid[0].length;
6
7    // Determine the modulo of the first element as a reference
8    let referenceModulo = grid[0][0] % x;
9
10    // Flatten the grid into a single array for ease of manipulation
11    let flattenedGrid: number[] = [];
12
13    // Process the grid while checking if it's possible to make all elements equal
14    for (let i = 0; i < rows; i++) {
15        for (let j = 0; j < cols; j++) {
16            // If an element's modulo isn't equal to the reference, it's not possible to make all elements equal
17            if (grid[i][j] % x !== referenceModulo) {
18                return -1;
19            }
20            // Populate the flattened grid
21            flattenedGrid.push(grid[i][j]);
22        }
23    }
24
25    // Sort the flattened grid to find the median
26    flattenedGrid.sort((a, b) => a - b);
27
28    // The median value is the target value for all elements to make them equal
29    let targetValue = flattenedGrid[Math.floor((rows * cols) / 2)];
30
31    // Calculate the total number of operations needed
32    let totalOps = 0;
33    for (let value of flattenedGrid) {
34        // Add the required number of operations per element
35        totalOps += Math.abs(value - targetValue) / x;
36    }
37
38    // Return the total number of operations
39    return totalOps;
40}
41
Not Sure What to Study? Take the 2-min Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

The given Python code is used to determine the minimum number of operations to make all elements in a grid equal if one can only add or subtract a value x from elements in the grid.

Time Complexity:

The time complexity of the code is analyzed as follows:

  1. Creating the nums list with a nested loop through the grid: This takes O(m*n), where m and n are the dimensions of the grid.
  2. Sorting the nums list: The sort operation has a time complexity of O(k*log(k)), where k is the total number of elements in the grid (k = m*n).
  3. Calculating the median and the number of operations: This involves a single pass through the sorted nums list, which takes O(k).

Combining these, the dominant term is the sorting step, therefore the overall time complexity is O(k*log(k)) which simplifies to O(m*n*log(m*n)) since k = m*n.

Space Complexity:

  1. Storing the nums list: Space complexity is O(k), which is O(m*n) where k is the total number of elements in the grid.
  2. Variables mod and mid: These are constant space and do not scale with the input, so they contribute O(1).

Thus, the overall space complexity is O(m*n) since the storage for the nums list dominates the space usage.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫