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++
#include <bits/stdc++.h>
using namespace std;
bool isMaximumMedian(vector<vector<int> >& arr,
int N, int K, int mid)
{
vector<vector<int> > Pre(
N + 5, vector<int>(N + 5, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
int required = (K * K + 1) / 2;
bool flag = 0;
for (int i = K; i <= N; ++i) {
for (int j = K; j <= N; ++j) {
int X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
if (X < required)
flag = 1;
}
}
return flag;
}
int maximumMedian(vector<vector<int> >& arr,
int N, int K)
{
int low = 0, high = 1e9;
while (low < high) {
int mid = low + (high - low) / 2;
if (isMaximumMedian(arr, N, K, mid)) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
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
public class GFG
{
static boolean isMaximumMedian(int arr[][] , int N, int K, int mid)
{
int [][]Pre = new int [N+5][N+5];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
int required = (K * K + 1) / 2;
boolean flag = false;
for (int i = K; i <= N; ++i) {
for (int j = K; j <= N; ++j) {
int X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
if (X < required)
flag = true;
}
}
return flag;
}
static int maximumMedian(int arr[][], int N, int K)
{
int low = 0, high = (int)1e9;
while (low < high) {
int mid = low + (high - low) / 2;
if (isMaximumMedian(arr, N, K, mid)) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
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));
}
}
|
Python3
def isMaximumMedian(arr, N, K, mid):
Pre = [[0 for x in range(N + 5)]
for y in range(N + 5)]
for i in range(N):
for j in range(N):
Pre[i + 1][j + 1] = (Pre[i + 1][j] +
Pre[i][j + 1] -
Pre[i][j])
if (arr[i][j] <= mid):
Pre[i + 1][j + 1] += 1
required = (K * K + 1) // 2
flag = 0
for i in range(K, N + 1):
for j in range(K, N + 1):
X = (Pre[i][j] - Pre[i - K][j] -
Pre[i][j - K] + Pre[i - K][j - K])
if (X < required):
flag = 1
return flag
def maximumMedian(arr, N, K):
low = 0
high = 1000000009
while (low < high):
mid = low + (high - low) // 2
if (isMaximumMedian(arr, N, K, mid)):
low = mid + 1
else:
high = mid
return low
if __name__ == "__main__":
arr = [ [ 1, 5, 12 ],
[ 6, 7, 11 ],
[ 8, 9, 10 ] ]
N = len(arr)
K = 2
print(maximumMedian(arr, N, K))
|
C#
using System;
class GFG{
static bool isMaximumMedian(int[,] arr, int N,
int K, int mid)
{
int [,]Pre = new int[N + 5, N + 5];
for(int i = 0; i < N; ++i)
{
for(int j = 0; j < N; ++j)
{
Pre[i + 1, j + 1] = Pre[i + 1, j] +
Pre[i, j + 1] -
Pre[i, j];
if (arr[i, j] <= mid)
Pre[i + 1, j + 1]++;
}
}
int required = (K * K + 1) / 2;
bool flag = false;
for(int i = K; i <= N; ++i)
{
for(int j = K; j <= N; ++j)
{
int X = Pre[i, j] - Pre[i - K, j] -
Pre[i, j - K] + Pre[i - K, j - K];
if (X < required)
flag = true;
}
}
return flag;
}
static int maximumMedian(int[,] arr, int N, int K)
{
int low = 0, high = (int)1e9;
while (low < high)
{
int mid = low + (high - low) / 2;
if (isMaximumMedian(arr, N, K, mid))
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
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));
}
}
|
Javascript
<script>
function isMaximumMedian(arr, N, K, mid) {
let Pre = Array(N + 5).fill().map(() => Array(N + 5).fill(0));
for (let i = 0; i < N; ++i) {
for (let j = 0; j < N; ++j) {
Pre[i + 1][j + 1] = Pre[i + 1][j]
+ Pre[i][j + 1]
- Pre[i][j];
if (arr[i][j] <= mid)
Pre[i + 1][j + 1]++;
}
}
let required = Math.floor((K * K + 1) / 2);
let flag = 0;
for (let i = K; i <= N; ++i) {
for (let j = K; j <= N; ++j) {
let X = Pre[i][j] - Pre[i - K][j]
- Pre[i][j - K]
+ Pre[i - K][j - K];
if (X < required)
flag = 1;
}
}
return flag;
}
function maximumMedian(arr, N, K) {
let low = 0, high = 1e9;
while (low < high) {
let mid = low + Math.floor((high - low) / 2);
if (isMaximumMedian(arr, N, K, mid)) {
low = mid + 1;
}
else {
high = mid;
}
}
return low;
}
let arr
= [[1, 5, 12], [6, 7, 11], [8, 9, 10]];
let N = arr.length;
let K = 2;
document.write(maximumMedian(arr, N, K));
</script>
|
Time Complexity: O(N2 * log(109))
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!