Find largest median of a sub array with length at least K

0 0 11 minutes read

Given an array arr[] of length N (1? arr[i] ? N) and an integer K. The task is to find the largest median of any subarray in arr[] of at least K size.

Examples:

Input: arr[] = {1, 2, 3, 2, 1}, K = 3
Output: 2
Explanation: Here the median of all possible sub arrays with length >= K is 2, so the maximum median is 2.

Input: arr[] = {1, 2, 3, 4}, K = 2
Output: 3
Explanation: Here the median of sub array( [3. 4] ) = 3 which is the maximum possible median.

Naive Approach: Go through all the sub-arrays with length at least K in arr[] and find the median of each sub-array and get the maximum median.

Below is the implementation of the above approach.

C++

// C++ code to find the maximum median
// of a sub array having length at least K.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum median
// of a sub array having length at least k.
int maxMedian(int arr[], int N, int K)
{
    // Variable to keep track
    // of maximum median.
    int mx_median = -1;
 
    // Go through all the sub arrays
    // having length at least K.
    for (int i = 0; i < N; i++) {
        for (int j = i + K - 1; j < N; j++) {
            int len = j - i + 1;
            int temp[len];
 
            // Copy all elements of
            // arr[i ... j] to temp[].
            for (int k = i; k <= j; k++)
                temp[k - i] = arr[k];
 
            // Sort the temp[] array
            // to find the median.
            sort(temp, temp + len);
 
            mx_median = max(mx_median,
                            temp[(len - 1)
                                 / 2]);
        }
    }
    return mx_median;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    // Function Call
    cout << maxMedian(arr, N, K);
    return 0;
}

Java

// Java code to find the maximum median
// of a sub array having length at least K.
import java.util.*;
public class GFG
{
 
// Function to find the maximum median
// of a sub array having length at least k.
static int maxMedian(int arr[], int N, int K)
{
   
    // Variable to keep track
    // of maximum median.
    int mx_median = -1;
 
    // Go through all the sub arrays
    // having length at least K.
    for (int i = 0; i < N; i++) {
        for (int j = i + K - 1; j < N; j++) {
            int len = j - i + 1;
            int temp[] = new int[len];
 
            // Copy all elements of
            // arr[i ... j] to temp[].
            for (int k = i; k <= j; k++)
                temp[k - i] = arr[k];
 
            // Sort the temp[] array
            // to find the median.
            Arrays.sort(temp);
 
            mx_median = Math.max(mx_median,
                            temp[(len - 1)
                                 / 2]);
        }
    }
    return mx_median;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 2, 3, 2, 1 };
    int N = arr.length;
    int K = 3;
 
    // Function Call
    System.out.println(maxMedian(arr, N, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code for the above approach 
 
# Function to find the maximum median
# of a sub array having length at least k.
def maxMedian(arr, N, K):
 
    # Variable to keep track
    # of maximum median.
    mx_median = -1;
 
    # Go through all the sub arrays
    # having length at least K.
    for i in range(N):
        for j in range(i + K - 1, N):
            _len = j - i + 1;
            temp = [0] * _len
 
            # Copy all elements of
            # arr[i ... j] to temp[].
            for k in range(i, j + 1):
                temp[k - i] = arr[k];
 
            # Sort the temp[] array
            # to find the median.
            temp.sort()
 
            mx_median = max(mx_median, temp[((_len - 1) // 2)]);
    return mx_median;
 
 
# Driver code
arr = [1, 2, 3, 2, 1];
N = len(arr)
K = 3;
 
# Function Call
print(maxMedian(arr, N, K));
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code to find the maximum median
// of a sub array having length at least K.
using System;
class GFG
{
 
// Function to find the maximum median
// of a sub array having length at least k.
static int maxMedian(int []arr, int N, int K)
{
   
    // Variable to keep track
    // of maximum median.
    int mx_median = -1;
 
    // Go through all the sub arrays
    // having length at least K.
    for (int i = 0; i < N; i++) {
        for (int j = i + K - 1; j < N; j++) {
            int len = j - i + 1;
            int []temp = new int[len];
 
            // Copy all elements of
            // arr[i ... j] to temp[].
            for (int k = i; k <= j; k++)
                temp[k - i] = arr[k];
 
            // Sort the temp[] array
            // to find the median.
            Array.Sort(temp);
 
            mx_median = Math.Max(mx_median,
                            temp[(len - 1)
                                 / 2]);
        }
    }
    return mx_median;
}
 
// Driver Code:
public static void Main()
{
    int []arr = { 1, 2, 3, 2, 1 };
    int N = arr.Length;
    int K = 3;
 
    // Function Call
    Console.WriteLine(maxMedian(arr, N, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach 
 
       // Function to find the maximum median
       // of a sub array having length at least k.
       function maxMedian(arr, N, K)
       {
        
           // Variable to keep track
           // of maximum median.
           let mx_median = -1;
 
           // Go through all the sub arrays
           // having length at least K.
           for (let i = 0; i < N; i++) {
               for (let j = i + K - 1; j < N; j++) {
                   let len = j - i + 1;
                   let temp = new Array(len).fill(0)
 
                   // Copy all elements of
                   // arr[i ... j] to temp[].
                   for (let k = i; k <= j; k++)
                       temp[k - i] = arr[k];
 
                   // Sort the temp[] array
                   // to find the median.
                   temp.sort(function (a, b) { return a - b })
                   let x = Math.floor((len - 1) / 2)
                   mx_median = Math.max(mx_median,
                       temp[x]);
               }
           }
           return mx_median;
       }
 
       // Driver code
       let arr = [1, 2, 3, 2, 1];
       let N = arr.length;
       let K = 3;
 
       // Function Call
       document.write(maxMedian(arr, N, K));
 
 // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N³ log(N))
Auxiliary Space: O(N)

Efficient Approach: An efficient approach is to use the binary search algorithm. Prefix sum technique can be used here in order to check quickly if there exists any segment of length at least K having a sum greater than zero, it helps in reducing the time complexity. Follow the steps below to solve the given problem.

Let l and r denote the left and right boundary for our binary search algorithm.
For each mid-value check if it is possible to have a median equal to mid of a subarray having a length of at least K.
Define a function for checking the above condition.
- Take an array of length N ( Pre[] ) and at i-th index store 1 if arr[i] >= mid else -1.
- Calculate the prefix sum of the array Pre[].
- Now in some segments, the median is at least x if the sum on this sub-segment is positive. Now we only need to check if the array Pre[] consisting of ?1 and 1 has a sub-segment of length at least K with positive-sum.
- For prefix sum at position i choose the minimum prefix sum amongst positions 0, 1, . . ., i?K, which can be done using prefix minimum in linear time.
- Maintain the maximum sum of a sub-array having a length of at least K.
- If the maximum sum is greater than 0 return true, else return false.
Return the maximum median possible finally.

Below is the implementation of the above approach.

C++

// C++ code to find the maximum median
// of a sub array having length at least K
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if
// the median is possible or not.
bool good(int arr[], int& N, int& K,
          int& median)
{
    int pre[N];
    for (int i = 0; i < N; i++) {
        if (arr[i] >= median)
            pre[i] = 1;
        else
            pre[i] = -1;
 
        if (i > 0)
            pre[i] += pre[i - 1];
    }
 
    // mx denotes the maximum
    // sum of a sub array having
    // length at least k.
    int mx = pre[K - 1];
 
    // mn denotes the minimum
    // prefix sum seen so far.
    int mn = 0;
 
    for (int i = K; i < N; i++) {
        mn = min(mn, pre[i - K]);
        mx = max(mx, pre[i] - mn);
    }
    if (mx > 0)
        return true;
    return false;
}
 
// Function to find the maximum median
// of a sub array having length at least K
int maxMedian(int arr[], int N, int K)
{
    // l and r denote the left and right
    // boundary for binary search algorithm
    int l = 1, r = N + 1;
 
    // Variable to keep track
    // of maximum median
    int mx_median = -1;
 
    while (l <= r) {
        int mid = (l + r) / 2;
        if (good(arr, N, K, mid)) {
            mx_median = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return mx_median;
}
 
// Driver function
int main()
{
    int arr[] = { 1, 2, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    // Function Call
    cout << maxMedian(arr, N, K);
    return 0;
}

Java

// Java code to find the maximum median
// of a sub array having length at least K
import java.util.*;
 
class GFG{
 
  // Function to check if
  // the median is possible or not.
  static boolean good(int arr[], int N, int K,
                      int median)
  {
    int []pre = new int[N];
    for (int i = 0; i < N; i++) {
      if (arr[i] >= median)
        pre[i] = 1;
      else
        pre[i] = -1;
 
      if (i > 0)
        pre[i] += pre[i - 1];
    }
 
    // mx denotes the maximum
    // sum of a sub array having
    // length at least k.
    int mx = pre[K - 1];
 
    // mn denotes the minimum
    // prefix sum seen so far.
    int mn = 0;
 
    for (int i = K; i < N; i++) {
      mn = Math.min(mn, pre[i - K]);
      mx = Math.max(mx, pre[i] - mn);
    }
    if (mx > 0)
      return true;
    return false;
  }
 
  // Function to find the maximum median
  // of a sub array having length at least K
  static int maxMedian(int arr[], int N, int K)
  {
    // l and r denote the left and right
    // boundary for binary search algorithm
    int l = 1, r = N + 1;
 
    // Variable to keep track
    // of maximum median
    int mx_median = -1;
 
    while (l <= r) {
      int mid = (l + r) / 2;
      if (good(arr, N, K, mid)) {
        mx_median = mid;
        l = mid + 1;
      }
      else
        r = mid - 1;
    }
    return mx_median;
  }
 
  // Driver function
  public static void main(String[] args)
  {
    int arr[] = { 1, 2, 3, 2, 1 };
    int N = arr.length;
    int K = 3;
 
    // Function Call
    System.out.print(maxMedian(arr, N, K));
  }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python code to find the maximum median
# of a sub array having length at least K
 
# Function to check if
# the median is possible or not.
def good(arr, N, K, median):
    pre = [0]*N
    for i in range(N):
        if(arr[i] >= median):
            pre[i] = 1
        else:
            pre[i] = -1
 
        if(i > 0):
            pre[i] += pre[i-1]
 
             
    # mx denotes the maximum
    # sum of a sub array having
    # length at least k.
    mx = pre[K-1]
 
    # mn denotes the minimum
    # prefix sum seen so far.
    mn = 0
 
    for i in range(K, N):
        mn = min(mn, pre[i-K])
        mx = max(mx, pre[i]-mn)
 
    if(mx > 0):
        return True
 
    return False
 
# Function to find the maximum median
# of a sub array having length at least K
def maxMedian(arr, N, K):
   
      # l and r denote the left and right
    # boundary for binary search algorithm
    l, r = 1, N+1
 
    # Variable to keep track
    # of maximum median
    mx_median = -1
 
    while(l <= r):
        mid = (l+r)//2
        if(good(arr, N, K, mid)):
            mx_median = mid
            l = mid+1
        else:
            r = mid-1
 
    return mx_median
 
arr = [1, 2, 3, 2, 1]
N = len(arr)
K = 3
 
# Function call
print(maxMedian(arr, N, K))
 
# This code is contributed by lokeshmvs21.

C#

// C# code to find the maximum median
// of a sub array having length at least K
using System;
 
public class GFG{
 
  // Function to check if
  // the median is possible or not.
  static bool good(int []arr, int N, int K,
                      int median)
  {
    int []pre = new int[N];
    for (int i = 0; i < N; i++) {
      if (arr[i] >= median)
        pre[i] = 1;
      else
        pre[i] = -1;
 
      if (i > 0)
        pre[i] += pre[i - 1];
    }
 
    // mx denotes the maximum
    // sum of a sub array having
    // length at least k.
    int mx = pre[K - 1];
 
    // mn denotes the minimum
    // prefix sum seen so far.
    int mn = 0;
 
    for (int i = K; i < N; i++) {
      mn = Math.Min(mn, pre[i - K]);
      mx = Math.Max(mx, pre[i] - mn);
    }
    if (mx > 0)
      return true;
    return false;
  }
 
  // Function to find the maximum median
  // of a sub array having length at least K
  static int maxMedian(int []arr, int N, int K)
  {
    // l and r denote the left and right
    // boundary for binary search algorithm
    int l = 1, r = N + 1;
 
    // Variable to keep track
    // of maximum median
    int mx_median = -1;
 
    while (l <= r) {
      int mid = (l + r) / 2;
      if (good(arr, N, K, mid)) {
        mx_median = mid;
        l = mid + 1;
      }
      else
        r = mid - 1;
    }
    return mx_median;
  }
 
  // Driver function
  public static void Main(String[] args)
  {
    int []arr = { 1, 2, 3, 2, 1 };
    int N = arr.Length;
    int K = 3;
 
    // Function Call
    Console.Write(maxMedian(arr, N, K));
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript code to find the maximum median
// of a sub array having length at least K
 
 // Function to check if
  // the median is possible or not.
  function good(arr , N , K,
                      median)
  {
    var pre = Array.from({length: N}, (_, i) => 0);
    for (var i = 0; i < N; i++) {
      if (arr[i] >= median)
        pre[i] = 1;
      else
        pre[i] = -1;
 
      if (i > 0)
        pre[i] += pre[i - 1];
    }
 
    // mx denotes the maximum
    // sum of a sub array having
    // length at least k.
    var mx = pre[K - 1];
 
    // mn denotes the minimum
    // prefix sum seen so far.
    var mn = 0;
 
    for (var i = K; i < N; i++) {
      mn = Math.min(mn, pre[i - K]);
      mx = Math.max(mx, pre[i] - mn);
    }
    if (mx > 0)
      return true;
    return false;
  }
 
  // Function to find the maximum median
  // of a sub array having length at least K
  function maxMedian(arr , N , K)
  {
   
    // l and r denote the left and right
    // boundary for binary search algorithm
    var l = 1, r = N + 1;
 
    // Variable to keep track
    // of maximum median
    var mx_median = -1;
 
    while (l <= r) {
      var mid = parseInt((l + r) / 2);
      if (good(arr, N, K, mid)) {
        mx_median = mid;
        l = mid + 1;
      }
      else
        r = mid - 1;
    }
    return mx_median;
  }
 
  // Driver function
var arr = [ 1, 2, 3, 2, 1 ];
var N = arr.length;
var K = 3;
 
// Function Call
document.write(maxMedian(arr, N, K));
 
// This code is contributed by shikhasingrajput 
</script>

Output

Time Complexity: O(N * logN).
Auxiliary Space: O(N)

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 zambiatek!