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 codeint 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 codepublic 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 codearr = [1, 2, 3, 2, 1];N = len(arr)K = 3;# Function Callprint(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
2
Time Complexity: O(N3 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 Kint 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 functionint 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 Kimport 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 Kdef 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_medianarr = [1, 2, 3, 2, 1]N = len(arr)K = 3# Function callprint(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 Kusing 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 functionvar arr = [ 1, 2, 3, 2, 1 ];var N = arr.length;var K = 3;// Function Calldocument.write(maxMedian(arr, N, K));// This code is contributed by shikhasingrajput </script> |
Output
2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
