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

  

#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;

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets