Find the sum of medians of all odd length subarrays
Last Updated :
22 Feb, 2023
Given an array arr[] of size N, the task is to find the sum of medians of all sub-array of odd-length.
Examples:
Input: arr[] = {4, 2, 5, 1}
Output: 18
Explanation : Sub-Arrays of odd length and their medians are :
- [4] -> Median is 4
- [4, 2, 5] -> Median is 4
- [2] -> Median is 2
- [2, 5, 1] -> Median is 2
- [5] -> Median is 5
- [1] -> Median is 1
Their sum = 4 + 4+ 2 + 2 + 5 +1 = 18
Input: arr[] = {1, 2}
Output: 3
Pre-requisites: Median of Stream of Running Integers using STL
Naive Approach: Generate each and every sub-array. If the length of the sub-array is odd, then sort the sub-array and return the middle element.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector< int > arr)
{
int ans = 0;
int n = arr.size();
for ( int i = 0; i < n; i++)
{
vector< int > new_arr;
for ( int j = i; j < n; j++)
{
new_arr.push_back(arr[j]);
if ((new_arr.size() % 2) == 1)
{
sort(new_arr.begin(), new_arr.end());
int mid = new_arr.size() / 2;
ans += new_arr[mid];
}
}
}
return ans;
}
int main()
{
vector< int > arr = { 4, 2, 5, 1 };
cout << solve(arr);
}
|
Java
import java.util.*;
class GFG {
static int solve( int [] arr) {
int ans = 0 ;
int n = arr.length;
for ( int i = 0 ; i < n; i++) {
List<Integer> new_arr = new LinkedList<Integer>();
for ( int j = i; j < n; j++) {
new_arr.add(arr[j]);
if ((new_arr.size() % 2 ) == 1 ) {
Collections.sort(new_arr);
int mid = new_arr.size() / 2 ;
ans += new_arr.get(mid);
}
}
}
return ans;
}
public static void main(String[] args) {
int [] arr = { 4 , 2 , 5 , 1 };
System.out.println(solve(arr));
}
}
|
Python3
def solve(arr):
ans = 0
n = len (arr)
for i in range (n):
new_arr = []
for j in range (i, n, 1 ):
new_arr.append(arr[j])
if ( len (new_arr)) % 2 = = 1 :
new_arr.sort()
mid = len (new_arr) / / 2
ans + = new_arr[mid]
return (ans)
if __name__ = = "__main__" :
arr = [ 4 , 2 , 5 , 1 ]
print (solve(arr))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static int solve( int [] arr) {
int ans = 0;
int n = arr.Length;
for ( int i = 0; i < n; i++) {
List< int > new_arr = new List< int >();
for ( int j = i; j < n; j++) {
new_arr.Add(arr[j]);
if ((new_arr.Count % 2) == 1) {
new_arr.Sort();
int mid = new_arr.Count / 2;
ans += new_arr[mid];
}
}
}
return ans;
}
public static void Main() {
int [] arr = { 4, 2, 5, 1 };
Console.Write(solve(arr));
}
}
|
Javascript
<script>
function solve(arr) {
var ans = 0;
var n = arr.length;
for ( var i = 0; i < n; i++) {
var new_arr= new Array();
for ( var j = i; j < n; j++) {
new_arr.push(arr[j]);
if ((new_arr.length % 2) == 1) {
new_arr.sort();
var mid = Math.floor(new_arr.length / 2);
ans += new_arr[mid];
}
}
}
return ans;
}
var arr = [ 4, 2, 5, 1 ];
document.write(solve(arr));
</script>
|
Time Complexity: O(N3 * Log(N))
Auxiliary Space: O(N)
Note: Instead of sorting array each time, which costs (N*logN), insertion sort can be applied. But still, overall Time Complexity will be O(N3).
Efficient Approach: The median of the sorted array is the value separating the higher half from the lower half in the array. For finding out the median, we only need the middle element, rather than the entire sorted array. The approach of Median of Stream of Running Integers can be applied over here. Follow the steps mentioned below
- Use max and min heaps to calculate the running median.
- Traverse each and every element in the array.
- While creating a new subarray, add an element into the heaps and return median if the size is odd else return 0.
- Max_heap is used to store lower half elements such that the maximum element is at the top and min_heap is used to store higher half elements such that the minimum element is at the top.
- The difference between both the heaps should not be greater than one, and one extra element is always placed in max_heap.
Note: Here max_heap is implemented using min_heap, by just negating the values so that the maximum negative element can be popped.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
class find_median {
public :
find_median()
{
max_heap
= std::priority_queue< int , std::vector< int >,
std::less< int > >();
min_heap
= std::priority_queue< int , std::vector< int >,
std::less< int > >();
}
int add( int val)
{
if (max_heap.empty() || max_heap.top() > val) {
max_heap.push(-val);
}
else {
min_heap.push(val);
}
if (max_heap.size() + 1 > min_heap.size()) {
val = -max_heap.top();
max_heap.pop();
min_heap.push(val);
}
if (min_heap.size() > max_heap.size()) {
val = min_heap.top();
min_heap.pop();
max_heap.push(-val);
}
if ((min_heap.size() + max_heap.size()) % 2 == 1) {
return -max_heap.top();
}
else {
return 0;
}
}
std::priority_queue< int , std::vector< int >,
std::less< int > >
max_heap;
std::priority_queue< int , std::vector< int >,
std::less< int > >
min_heap;
};
int solve(std::vector< int > arr)
{
int ans = 0;
int n = arr.size();
for ( int i = 0; i < n; i++) {
find_median obj;
for ( int j = i; j < n; j++)
{
int val = obj.add(arr[j]);
ans += val;
}
}
return (ans);
}
int main()
{
std::vector< int > arr = { 4, 2, 5, 1 };
std::cout << solve(arr);
return 0;
}
|
Java
import java.util.*;
class FindMedian {
private List<Integer> max_heap;
private List<Integer> min_heap;
public FindMedian() {
max_heap = new ArrayList<>();
min_heap = new ArrayList<>();
}
public int add( int val) {
if (max_heap.size() == 0 || max_heap.get( 0 ) > val) {
max_heap.add(-val);
}
else {
min_heap.add(val);
}
if (max_heap.size() + 1 > min_heap.size()) {
int v = max_heap.get(max_heap.size() - 1 );
max_heap.remove(max_heap.size() - 1 );
min_heap.add(-v);
}
if (min_heap.size() > max_heap.size()) {
int v = min_heap.get(min_heap.size() - 1 );
min_heap.remove(min_heap.size() - 1 );
max_heap.add(-v);
}
if ((min_heap.size() + max_heap.size()) % 2 == 1 ) {
return (-max_heap.get( 0 ));
}
else {
return 0 ;
}
}
}
class GFG {
public static int solve( int [] arr) {
int ans = 0 ;
int n = arr.length;
for ( int i = 0 ; i < n; i++) {
FindMedian obj = new FindMedian();
for ( int j = i; j < n; j++) {
int val = obj.add(arr[j]);
ans += val;
}
}
return (ans);
}
public static void main(String[] args) {
int [] arr = { 4 , 2 , 5 , 1 };
System.out.println(solve(arr));
}
}
|
Python3
from heapq import heappush as push, heappop as pop
class find_median():
def __init__( self ):
self .max_heap = []
self .min_heap = []
def add( self , val):
if ( len ( self .max_heap) = = 0 or
self .max_heap[ 0 ] > val):
push( self .max_heap, - val)
else :
push( self .min_heap, val)
if ( len ( self .max_heap) + 1 >
len ( self .min_heap)):
val = pop( self .max_heap)
push( self .min_heap, - val)
if ( len ( self .min_heap) >
len ( self .max_heap)):
val = pop( self .min_heap)
push( self .max_heap, - val)
if ( len ( self .min_heap) +
len ( self .max_heap)) % 2 = = 1 :
return ( - self .max_heap[ 0 ])
else :
return 0
def solve(arr):
ans = 0
n = len (arr)
for i in range (n):
obj = find_median()
for j in range (i, n, 1 ):
val = obj.add(arr[j])
ans + = val
return (ans)
if __name__ = = "__main__" :
arr = [ 4 , 2 , 5 , 1 ]
print (solve(arr))
|
C#
using System;
using System.Collections.Generic;
public class FindMedian
{
private List< int > max_heap;
private List< int > min_heap;
public FindMedian()
{
max_heap = new List< int >();
min_heap = new List< int >();
}
public int Add( int val)
{
if (max_heap.Count == 0 || max_heap[0] > val) {
max_heap.Add(-val);
}
else {
min_heap.Add(val);
}
if (max_heap.Count + 1 > min_heap.Count) {
int v = max_heap[max_heap.Count - 1];
max_heap.RemoveAt(max_heap.Count - 1);
min_heap.Add(-v);
}
if (min_heap.Count > max_heap.Count) {
int v = min_heap[min_heap.Count - 1];
min_heap.RemoveAt(min_heap.Count - 1);
max_heap.Add(-v);
}
if ((min_heap.Count + max_heap.Count) % 2 == 1) {
return (-max_heap[0]);
}
else {
return 0;
}
}
}
public class GFG {
public static int Solve( int [] arr)
{
int ans = 0;
int n = arr.Length;
for ( int i = 0; i < n; i++) {
FindMedian obj = new FindMedian();
for ( int j = i; j < n; j++) {
int val = obj.Add(arr[j]);
ans += val;
}
}
return (ans);
}
public static void Main()
{
int [] arr = { 4, 2, 5, 1 };
Console.WriteLine(Solve(arr));
}
}
|
Javascript
class find_median {
constructor() {
this .max_heap = [];
this .min_heap = [];
}
add(val) {
if ( this .max_heap.length == 0 || this .max_heap[0] > val) {
this .max_heap.push(-val);
}
else {
this .min_heap.push(val);
}
if ( this .max_heap.length + 1 > this .min_heap.length) {
let val = this .max_heap.pop();
this .min_heap.push(-val);
}
if ( this .min_heap.length > this .max_heap.length) {
let val = this .min_heap.pop();
this .max_heap.push(-val);
}
if (( this .min_heap.length + this .max_heap.length) % 2 === 1) {
return (- this .max_heap[0]);
}
else {
return 0;
}
}
}
function solve(arr) {
let ans = 0;
let n = arr.length;
for (let i = 0; i < n; i++) {
let obj = new find_median();
for (let j = i; j < n; j++) {
let val = obj.add(arr[j]);
ans += val;
}
}
return (ans);
}
let arr = [4, 2, 5, 1];
console.log(solve(arr));
|
Time Complexity: O(N2 * Log(N))
Auxiliary Space: O(N)