Maximize median of a KxK sub-grid in an NxN grid

Last Updated : 28 Jul, 2021

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(N² * K²)
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 (K²+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 (K²+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 (K²+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>

Output:

Time Complexity: O(N² * log(10⁹))
Auxiliary Space: O(N²)

Suggest improvement

Exit Point in a Binary Matrix

Longest subsequence with non negative prefix sum at each position

Share your thoughts in the comments

Maximize median of a KxK sub-grid in an NxN grid

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?