Queries to find minimum sum of array elements from either end of an array | Java implementation of the above approach ; Function to find the minimum sum for the given queries ; Stores prefix and suffix sums ; Stores pairs of prefix and suffix sums ; Traverse the array ; Add element to prefix ; Store prefix for each element ; Traverse the array in reverse ; Add element to suffix ; Storing suffix for each element ; Traverse the array queries [ ] ; Minimum of suffix and prefix sums ; Driver Code
import java . util . * ; class GFG { static class pair < E , P > { E first ; P second ; public pair ( E first , P second ) { this . first = first ; this . second = second ; } } @ SuppressWarnings ( { " unchecked " , " rawtypes " } ) static void calculateQuery ( int arr [ ] , int N , int query [ ] , int M ) { int prefix = 0 , suffix = 0 ; HashMap < Integer , pair > mp = new HashMap < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { prefix += arr [ i ] ; mp . put ( arr [ i ] , new pair ( prefix , 0 ) ) ; } for ( int i = N - 1 ; i >= 0 ; i -- ) { suffix += arr [ i ] ; mp . put ( arr [ i ] , new pair ( mp . get ( arr [ i ] ) . first , suffix ) ) ; } for ( int i = 0 ; i < M ; i ++ ) { int X = query [ i ] ; System . out . print ( Math . min ( ( int ) mp . get ( X ) . first , ( int ) mp . get ( X ) . second ) + " ▁ " ) ; } } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 6 , 7 , 4 , 5 , 30 } ; int queries [ ] = { 6 , 5 } ; int N = arr . length ; int M = queries . length ; calculateQuery ( arr , N , queries , M ) ; } }