Maximize median of a KxK sub-grid in an NxN grid
Given a square matrix arr[][] of size N consisting of non-negative integers and an integer K, the task is to find the maximum median value of the elements of a square submatrix of the size K.
Examples:
Input: arr[][] = {{1, 5, 12}, {6, 7, 11}, {8, 9, 10}}, N = 3, K = 2
Output: 9
Explanation:
The median of all subsquare of size 2*2 are:
- The subsquare {{1, 5}, {6, 7}} has the median equal to 5.
- The subsquare {{5, 12}, {7, 11}} has the median equal to 7.
- The subsquare {{6, 7}, {8, 9}} has the median equal to 7.
- The subsquare {{7, 11}, {9, 10}} has the median equal to 9.
Therefore, the maximum possible median value among all possible square matrix is equal to 9.
Input: arr[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 10, 11}, {12, 13, 14, 13}}, N = 4, K = 2
Output: 11
Naive Approach: The simplest approach to solve the given above problem is to iterate over every submatrix of size K*K and then find the maximum median among all the submatrix formed.
Time Complexity: O(N2 * K2)
Auxiliary Space: O(1)
Efficient Approach: The above problem can be optimized based on the following observations:
- If M is the median of a square submatrix, then the count of numbers less than or equal to the M in that submatrix must be less than (K2+1)/2.
- The idea is to use Binary Search to find the given median value as:
- If the count of numbers less than M in any submatrix of size KΓK is less than (K2+1)/2, then increment the left boundary.
- Otherwise, decrement the right boundary.
- The idea is to use the prefix sum for the matrix to count the elements less than a particular value in constant time in a square submatrix.
Follow the steps below to solve the problem:
- Initialize two variables, say low as 0 and high as INT_MAX representing the range of the search space.
- Iterate until low is less than high and perform the following steps:
- Find the mid-value of the range [low, high] and store it in a variable say mid.
- Initialize vector of vectors say Pre to store the count of element less than or equal to mid in a prefix submatrix.
- Iterate over every element of the matrix arr[][] using variable i and j and update the value of Pre[i + 1][j + 1] as Pre[i + 1][j] + Pre[i][j + 1] β Pre[i][j] and then increment Pre[i + 1][j + 1] by 1 if arr[i][j] is less than or equal to mid.
- Initialize a variable, say flag as false to store if the value of mid is possible or not as the median.
- Iterate over every possible value of pair (i, j) of [K, N]*[K, N] and then perform the following steps:
- Find the count of elements less than or equal to mid in the square submatrix with top-left vertex as (i β K, j β K) and bottom right vertex as (i, j) and then store it in a variable say X as Pre[i][j] β Pre[i β K][j] β Pre[i][j β K]+ Pre[i β K][j β K].
- If X is less than (K2+1)/2 then mark flag true and break out of the loop.
- If the flag is true then update the value of low as (mid + 1). Otherwise, update the value of high as mid.
- After completing the above steps, print the value of low as the maximum median obtained among all possible square submatrix of size K*K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to determine if a given // value can be median bool isMaximumMedian(vector<vector< int > >& arr, int N, int K, int mid) { // Stores the prefix sum array vector<vector< int > > Pre( N + 5, vector< int >(N + 5, 0)); // Traverse the matrix arr[][] for ( int i = 0; i < N; ++i) { for ( int j = 0; j < N; ++j) { // Update Pre[i+1][j+1] Pre[i + 1][j + 1] = Pre[i + 1][j] + Pre[i][j + 1] - Pre[i][j]; // If arr[i][j] is less // than or equal to mid if (arr[i][j] <= mid) Pre[i + 1][j + 1]++; } } // Stores the count of elements // should be less than mid int required = (K * K + 1) / 2; // Stores if the median mid // can be possible or not bool flag = 0; // Iterate over the range [K, N] for ( int i = K; i <= N; ++i) { // Iterate over the range [K, N] for ( int j = K; j <= N; ++j) { // Stores count of elements less // than or equal to the value // mid in submatrix with bottom // right vertices at (i, j) int X = Pre[i][j] - Pre[i - K][j] - Pre[i][j - K] + Pre[i - K][j - K]; // If X is less than or // equal to required if (X < required) flag = 1; } } // Return flag return flag; } // Function to find the maximum median // of a subsquare of the given size int maximumMedian(vector<vector< int > >& arr, int N, int K) { // Stores the range of the // search space int low = 0, high = 1e9; // Iterate until low is less // than high while (low < high) { // Stores the mid value of // the range [low, high] int mid = low + (high - low) / 2; // If the current median can // be possible if (isMaximumMedian(arr, N, K, mid)) { // Update the value of low low = mid + 1; } else { // Update the value of high high = mid; } } // Return value stored in low as // answer return low; } // Driver Code int main() { vector<vector< int > > arr = { { 1, 5, 12 }, { 6, 7, 11 }, { 8, 9, 10 } }; int N = arr.size(); int K = 2; cout << maximumMedian(arr, N, K); return 0; } |
Java
// Java program for the above approach public class GFG { // Function to determine if a given // value can be median static boolean isMaximumMedian( int arr[][] , int N, int K, int mid) { // Stores the prefix sum array int [][]Pre = new int [N+ 5 ][N+ 5 ]; // Traverse the matrix arr[][] for ( int i = 0 ; i < N; ++i) { for ( int j = 0 ; j < N; ++j) { // Update Pre[i+1][j+1] Pre[i + 1 ][j + 1 ] = Pre[i + 1 ][j] + Pre[i][j + 1 ] - Pre[i][j]; // If arr[i][j] is less // than or equal to mid if (arr[i][j] <= mid) Pre[i + 1 ][j + 1 ]++; } } // Stores the count of elements // should be less than mid int required = (K * K + 1 ) / 2 ; // Stores if the median mid // can be possible or not boolean flag = false ; // Iterate over the range [K, N] for ( int i = K; i <= N; ++i) { // Iterate over the range [K, N] for ( int j = K; j <= N; ++j) { // Stores count of elements less // than or equal to the value // mid in submatrix with bottom // right vertices at (i, j) int X = Pre[i][j] - Pre[i - K][j] - Pre[i][j - K] + Pre[i - K][j - K]; // If X is less than or // equal to required if (X < required) flag = true ; } } // Return flag return flag; } // Function to find the maximum median // of a subsquare of the given size static int maximumMedian( int arr[][], int N, int K) { // Stores the range of the // search space int low = 0 , high = ( int )1e9; // Iterate until low is less // than high while (low < high) { // Stores the mid value of // the range [low, high] int mid = low + (high - low) / 2 ; // If the current median can // be possible if (isMaximumMedian(arr, N, K, mid)) { // Update the value of low low = mid + 1 ; } else { // Update the value of high high = mid; } } // Return value stored in low as // answer return low; } // Driver Code public static void main(String args[]) { int [][] arr = { { 1 , 5 , 12 }, { 6 , 7 , 11 }, { 8 , 9 , 10 } }; int N = arr.length; int K = 2 ; System.out.print( maximumMedian(arr, N, K)); } } // This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach # Function to determine if a given # value can be median def isMaximumMedian(arr, N, K, mid): # Stores the prefix sum array Pre = [[ 0 for x in range (N + 5 )] for y in range (N + 5 )] # Traverse the matrix arr[][] for i in range (N): for j in range (N): # Update Pre[i+1][j+1] Pre[i + 1 ][j + 1 ] = (Pre[i + 1 ][j] + Pre[i][j + 1 ] - Pre[i][j]) # If arr[i][j] is less # than or equal to mid if (arr[i][j] < = mid): Pre[i + 1 ][j + 1 ] + = 1 # Stores the count of elements # should be less than mid required = (K * K + 1 ) / / 2 # Stores if the median mid # can be possible or not flag = 0 # Iterate over the range [K, N] for i in range (K, N + 1 ): # Iterate over the range [K, N] for j in range (K, N + 1 ): # Stores count of elements less # than or equal to the value # mid in submatrix with bottom # right vertices at (i, j) X = (Pre[i][j] - Pre[i - K][j] - Pre[i][j - K] + Pre[i - K][j - K]) # If X is less than or # equal to required if (X < required): flag = 1 # Return flag return flag # Function to find the maximum median # of a subsquare of the given size def maximumMedian(arr, N, K): # Stores the range of the # search space low = 0 high = 1000000009 # Iterate until low is less # than high while (low < high): # Stores the mid value of # the range [low, high] mid = low + (high - low) / / 2 # If the current median can # be possible if (isMaximumMedian(arr, N, K, mid)): # Update the value of low low = mid + 1 else : # Update the value of high high = mid # Return value stored in low as # answer return low # Driver Code if __name__ = = "__main__" : arr = [ [ 1 , 5 , 12 ], [ 6 , 7 , 11 ], [ 8 , 9 , 10 ] ] N = len (arr) K = 2 print (maximumMedian(arr, N, K)) # This code is contributed by ukasp |
C#
// C# program for the above approach using System; class GFG{ // Function to determine if a given // value can be median static bool isMaximumMedian( int [,] arr, int N, int K, int mid) { // Stores the prefix sum array int [,]Pre = new int [N + 5, N + 5]; // Traverse the matrix arr[][] for ( int i = 0; i < N; ++i) { for ( int j = 0; j < N; ++j) { // Update Pre[i+1][j+1] Pre[i + 1, j + 1] = Pre[i + 1, j] + Pre[i, j + 1] - Pre[i, j]; // If arr[i][j] is less // than or equal to mid if (arr[i, j] <= mid) Pre[i + 1, j + 1]++; } } // Stores the count of elements // should be less than mid int required = (K * K + 1) / 2; // Stores if the median mid // can be possible or not bool flag = false ; // Iterate over the range [K, N] for ( int i = K; i <= N; ++i) { // Iterate over the range [K, N] for ( int j = K; j <= N; ++j) { // Stores count of elements less // than or equal to the value // mid in submatrix with bottom // right vertices at (i, j) int X = Pre[i, j] - Pre[i - K, j] - Pre[i, j - K] + Pre[i - K, j - K]; // If X is less than or // equal to required if (X < required) flag = true ; } } // Return flag return flag; } // Function to find the maximum median // of a subsquare of the given size static int maximumMedian( int [,] arr, int N, int K) { // Stores the range of the // search space int low = 0, high = ( int )1e9; // Iterate until low is less // than high while (low < high) { // Stores the mid value of // the range [low, high] int mid = low + (high - low) / 2; // If the current median can // be possible if (isMaximumMedian(arr, N, K, mid)) { // Update the value of low low = mid + 1; } else { // Update the value of high high = mid; } } // Return value stored in low as // answer return low; } // Driver code public static void Main( string [] args) { int [,] arr = { { 1, 5, 12 }, { 6, 7, 11 }, { 8, 9, 10 } }; int N = arr.GetLength(0); int K = 2; Console.WriteLine(maximumMedian(arr, N, K)); } } // This code is contributed by avijitmondal1998 |
Javascript
<script> // JavaScript Program for the above approach // Function to determine if a given // value can be median function isMaximumMedian(arr, N, K, mid) { // Stores the prefix sum array let Pre = Array(N + 5).fill().map(() => Array(N + 5).fill(0)); // Traverse the matrix arr[][] for (let i = 0; i < N; ++i) { for (let j = 0; j < N; ++j) { // Update Pre[i+1][j+1] Pre[i + 1][j + 1] = Pre[i + 1][j] + Pre[i][j + 1] - Pre[i][j]; // If arr[i][j] is less // than or equal to mid if (arr[i][j] <= mid) Pre[i + 1][j + 1]++; } } // Stores the count of elements // should be less than mid let required = Math.floor((K * K + 1) / 2); // Stores if the median mid // can be possible or not let flag = 0; // Iterate over the range [K, N] for (let i = K; i <= N; ++i) { // Iterate over the range [K, N] for (let j = K; j <= N; ++j) { // Stores count of elements less // than or equal to the value // mid in submatrix with bottom // right vertices at (i, j) let X = Pre[i][j] - Pre[i - K][j] - Pre[i][j - K] + Pre[i - K][j - K]; // If X is less than or // equal to required if (X < required) flag = 1; } } // Return flag return flag; } // Function to find the maximum median // of a subsquare of the given size function maximumMedian(arr, N, K) { // Stores the range of the // search space let low = 0, high = 1e9; // Iterate until low is less // than high while (low < high) { // Stores the mid value of // the range [low, high] let mid = low + Math.floor((high - low) / 2); // If the current median can // be possible if (isMaximumMedian(arr, N, K, mid)) { // Update the value of low low = mid + 1; } else { // Update the value of high high = mid; } } // Return value stored in low as // answer return low; } // Driver Code let arr = [[1, 5, 12], [6, 7, 11], [8, 9, 10]]; let N = arr.length; let K = 2; document.write(maximumMedian(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
9
Time Complexity: O(N2 * log(109))
Auxiliary Space: O(N2)