Find the number of sub arrays in the permutation of first N natural numbers such that their median is M | Java implementation of the approach ; Function to return the count of sub - arrays in the given permutation of first n natural numbers such that their median is m ; If element is less than m ; If element greater than m ; If m is found ; Count the answer ; Increment sum ; Driver code
import java . util . HashMap ; class GFG { public static int segments ( int n , int [ ] p , int m ) { HashMap < Integer , Integer > c = new HashMap < > ( ) ; c . put ( 0 , 1 ) ; boolean has = false ; int sum = 0 ; int ans = 0 ; for ( int r = 0 ; r < n ; r ++ ) { if ( p [ r ] < m ) sum -- ; else if ( p [ r ] > m ) sum ++ ; if ( p [ r ] == m ) has = true ; if ( has ) ans += ( c . get ( sum ) == null ? 0 : c . get ( sum ) ) + ( c . get ( sum - 1 ) == null ? 0 : c . get ( sum - 1 ) ) ; else c . put ( sum , c . get ( sum ) == null ? 1 : c . get ( sum ) + 1 ) ; } return ans ; } public static void main ( String [ ] args ) { int [ ] a = { 2 , 4 , 5 , 3 , 1 } ; int n = a . length ; int m = 4 ; System . out . println ( segments ( n , a , m ) ) ; } }