Find the Sub | Java program to find subarray with sum closest to 0 ; Returns subarray with sum closest to 0. ; To consider the case of subarray starting from beginning of the array ; Store prefix sum with index ; Sort on the basis of sum ; Find two consecutive elements with minimum difference ; Update minimum difference and starting and ending indexes ; Return starting and ending indexes ; Driver code
import java . util . * ; class Prefix { int sum , index ; } class Pair { int first , second ; Pair ( int a , int b ) { first = a ; second = b ; } } class GFG { static Pair findSubArray ( int arr [ ] , int n ) { int start = - 1 , end = - 1 , min_diff = Integer . MAX_VALUE ; Prefix pre_sum [ ] = new Prefix [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) pre_sum [ i ] = new Prefix ( ) ; pre_sum [ 0 ] . sum = 0 ; pre_sum [ 0 ] . index = - 1 ; for ( int i = 1 ; i <= n ; i ++ ) { pre_sum [ i ] . sum = pre_sum [ i - 1 ] . sum + arr [ i - 1 ] ; pre_sum [ i ] . index = i - 1 ; } Arrays . sort ( pre_sum , ( ( a , b ) -> a . sum - b . sum ) ) ; for ( int i = 1 ; i <= n ; i ++ ) { int diff = pre_sum [ i ] . sum - pre_sum [ i - 1 ] . sum ; if ( min_diff > diff ) { min_diff = diff ; start = pre_sum [ i - 1 ] . index ; end = pre_sum [ i ] . index ; } } Pair p = new Pair ( start + 1 , end ) ; return p ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , - 4 , - 1 , 6 } ; int n = arr . length ; Pair point = findSubArray ( arr , n ) ; System . out . print ( " Subarray ▁ starting ▁ from ▁ " ) ; System . out . println ( point . first + " ▁ to ▁ " + point . second ) ; } }