Minimizing Max-Min with K Operations in Matrix
Given a matrix mat[][] of size M x N, and a positive integer K. The task is to find the minimum value of D, where D >= 0. Here, D is defined as the difference between the maximum value and minimum value of the matrix. You can perform at least K operations in the given matrix such that In each operation, you can select any cells in the matrix and decrease the value of the cell by 1.
Examples:
Input: { { 1, 4, 7 }, { 3, 2, 6 }, { 11, 4, 12 } }, K = 3
Output: 9
Explanation: Decrement 12 two times and 11 one time then the maximum element will be 10 and the minimum element will be 1.Input: {{1, 10}}, K = 10
Output: 0
Explanation: 10 can be decremented 9 times so that it becomes 1, so the minimum difference is zero.
Minimizing Max-Min with K Operations in Matrix Using Binary search on the answer:
The idea is to use Binary search on answer here to efficiently find the minimum value (the maximum value to minimize) by iteratively limiting down the range of possible values. We start with the range between the minimum and maximum values in the matrix and repeatedly check if the midpoint is possible within K operations. If it is, we update our result and reduce the upper bound; if not, we adjust the lower bound. This process continues until we’ve identified the minimum possible value.
Step-by-step approach:
- Create variables start and end to find the initial range for the binary search. Set the end to the maximum value in the matrix.
- Create a result variable to end since initially, the maximum value is the upper bound of the possible range.
- Use the binary search until start <= end.
- Calculate the mid between the start and end.
- Use the isValid() function to check if mid can be achieved within K operations. If it can, update the result to mid and contract the search range by setting the end to mid-1.
- If mid is not achievable within K operations, adjust the search range by setting start to mid + 1.
- The final result will be the minimum achievable value within K operations.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int m, n; // Function to check if it's possible to achieve a value // 'val' within 'K' operations bool isValid( int val, int K, vector<vector< int > >& mat) { int operationRequire = 0; // Iterate through the matrix elements for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (mat[i][j] > val) operationRequire += mat[i][j] - val; // If operations required exceed 'K', it's not // possible if (operationRequire > K) return false ; } } // It's possible to achieve 'val' within 'K' operations return true ; } // Function to minimize the maximum value by adjusting the // matrix int minimizeMax( int K, vector<vector< int > >& mat) { int start = 0, end = 0, minn = INT_MAX; // Find the maximum value in the matrix initially for ( auto i : mat) { end = max(end, *max_element(i.begin(), i.end())); minn = min(minn, *min_element(i.begin(), i.end())); } int result = end; // Binary search to find the minimum value that can be // achieved while (start <= end) { int mid = (start + end) / 2; // Check if 'mid' is achievable within 'K' // operations if (isValid(mid, K, mat)) { result = mid; end = mid - 1; } else { start = mid + 1; } } // Return the difference between minimum possible // maximum value and mininmum value return max(result - minn, 0); } int main() { // Example input matrix vector<vector< int > > mat = { { 1, 4, 7 }, { 3, 2, 6 }, { 11, 4, 12 } }; m = mat.size(); n = mat[0].size(); int K = 3; // Find the minimized maximum value int maxValue = minimizeMax(K, mat); // Print the result cout << "The minimized maximum value is: " << maxValue; return 0; } |
Java
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Main { static int m, n; // Function to check if it's possible to achieve a value // 'val' within 'K' operations static boolean isValid( int val, int K, List<List<Integer> > mat) { int operationRequire = 0 ; // Iterate through the matrix elements for ( int i = 0 ; i < m; i++) { for ( int j = 0 ; j < n; j++) { if (mat.get(i).get(j) > val) operationRequire += mat.get(i).get(j) - val; // If operations required exceed 'K', it's // not possible if (operationRequire > K) return false ; } } // It's possible to achieve 'val' within 'K' // operations return true ; } // Function to minimize the maximum value by adjusting // the matrix static int minimizeMax( int K, List<List<Integer> > mat) { int start = 0 , end = 0 , minn = Integer.MAX_VALUE; // Find the maximum value in the matrix initially for (List<Integer> i : mat) { end = Math.max(end, Collections.max(i)); minn = Math.min(minn, Collections.min(i)); } int result = end; // Binary search to find the minimum value that can // be achieved while (start <= end) { int mid = (start + end) / 2 ; // Check if 'mid' is achievable within 'K' // operations if (isValid(mid, K, mat)) { result = mid; end = mid - 1 ; } else { start = mid + 1 ; } } // Return the difference between the minimum // possible maximum value and minimum value return Math.max(result - minn, 0 ); } public static void main(String[] args) { // Example input matrix List<List<Integer> > mat = new ArrayList<>(); mat.add(List.of( 1 , 4 , 7 )); mat.add(List.of( 3 , 2 , 6 )); mat.add(List.of( 11 , 4 , 12 )); m = mat.size(); n = mat.get( 0 ).size(); int K = 3 ; // Find the minimized maximum value int maxValue = minimizeMax(K, mat); // Print the result System.out.println( "The minimized maximum value is: " + maxValue); } } |
Python3
import sys m, n = 0 , 0 # Function to check if it's possible to achieve a value # 'val' within 'K' operations def is_valid(val, K, mat): operation_require = 0 # Iterate through the matrix elements for i in range (m): for j in range (n): if mat[i][j] > val: operation_require + = mat[i][j] - val # If operations required exceed 'K', it's not possible if operation_require > K: return False # It's possible to achieve 'val' within 'K' operations return True # Function to minimize the maximum value by adjusting the matrix def minimize_max(K, mat): global m, n start, end, minn = 0 , 0 , sys.maxsize # Find the maximum value in the matrix initially for i in mat: end = max (end, max (i)) minn = min (minn, min (i)) result = end # Binary search to find the minimum value that can be achieved while start < = end: mid = (start + end) / / 2 # Check if 'mid' is achievable within 'K' operations if is_valid(mid, K, mat): result = mid end = mid - 1 else : start = mid + 1 # Return the difference between the minimum possible # maximum value and minimum value return max (result - minn, 0 ) if __name__ = = "__main__" : # Example input matrix mat = [[ 1 , 4 , 7 ], [ 3 , 2 , 6 ], [ 11 , 4 , 12 ]] m = len (mat) n = len (mat[ 0 ]) K = 3 # Find the minimized maximum value max_value = minimize_max(K, mat) # Print the result print ( "The minimized maximum value is:" , max_value) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int m, n; // Function to check if it's possible to achieve a value // 'val' within 'K' operations static bool IsValid( int val, int K, List<List< int >> mat) { int operationRequire = 0; // Iterate through the matrix elements for ( int i = 0; i < m; i++) { for ( int j = 0; j < n; j++) { if (mat[i][j] > val) operationRequire += mat[i][j] - val; // If operations required exceed 'K', it's not possible if (operationRequire > K) return false ; } } // It's possible to achieve 'val' within 'K' operations return true ; } // Function to minimize the maximum value by adjusting the matrix static int MinimizeMax( int K, List<List< int >> mat) { int start = 0, end = 0, minn = int .MaxValue; // Find the maximum value in the matrix initially foreach ( var row in mat) { end = Math.Max(end, row.Max()); minn = Math.Min(minn, row.Min()); } int result = end; // Binary search to find the minimum value that can be achieved while (start <= end) { int mid = (start + end) / 2; // Check if 'mid' is achievable within 'K' operations if (IsValid(mid, K, mat)) { result = mid; end = mid - 1; } else { start = mid + 1; } } // Return the difference between the minimum possible maximum value and minimum value return Math.Max(result - minn, 0); } static void Main() { // Example input matrix List<List< int >> mat = new List<List< int >> { new List< int > { 1, 4, 7 }, new List< int > { 3, 2, 6 }, new List< int > { 11, 4, 12 } }; m = mat.Count; n = mat[0].Count; int K = 3; // Find the minimized maximum value int maxValue = MinimizeMax(K, mat); // Print the result Console.WriteLine( "The minimized maximum value is: " + maxValue); } } |
Javascript
<script> // Function to check if it's possible to achieve a value // 'val' within 'K' operations function isValid(val, K, mat) { let operationRequire = 0; // Iterate through the matrix elements for (let i = 0; i < mat.length; i++) { for (let j = 0; j < mat[i].length; j++) { if (mat[i][j] > val) { operationRequire += mat[i][j] - val; } // If operations required exceed 'K', it's not possible if (operationRequire > K) { return false ; } } } // It's possible to achieve 'val' within 'K' operations return true ; } // Function to minimize the maximum value by adjusting the matrix function minimizeMax(K, mat) { let start = 0, end = 0, minn = Number.MAX_SAFE_INTEGER; // Find the maximum value in the matrix initially for (let i = 0; i < mat.length; i++) { end = Math.max(end, Math.max(...mat[i])); minn = Math.min(minn, Math.min(...mat[i])); } let result = end; // Binary search to find the minimum value that can be achieved while (start <= end) { let mid = Math.floor((start + end) / 2); // Check if 'mid' is achievable within 'K' operations if (isValid(mid, K, mat)) { result = mid; end = mid - 1; } else { start = mid + 1; } } // Return the difference between the minimum // possible maximum value and minimum value return Math.max(result - minn, 0); } // Example input matrix let mat = [ [1, 4, 7], [3, 2, 6], [11, 4, 12] ]; let K = 3; // Find the minimized maximum value let maxValue = minimizeMax(K, mat); // Print the result console.log( "The minimized maximum value is: " + maxValue); </script> |
The minimized maximum value is: 9
Time Complexity: O(M * N * log(Max), where M is the number of rows and N is the number of columns in the matrix and Max is the maximum element in the matrix.
Auxiliary Space: O(1)
Contact Us