Q5 PepCoding | Largest Subarray With Zero Sum
Mon Jan 23 2023 08:17:31 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(int[] arr) {
//make a prefix sum array and store ps,index in hashmap
HashMap<Integer,Integer> fmap = new HashMap<>();
int sum =0 ;
fmap.put(0, -1); //adding 0 PS on -1 index
//while making PS if any PS repeats find the length of that sub array,do not add the sum and index if PS repeats as we have to find the largest length and adding PS again will update the index to a closer index
int max = 0;
for(int i =0 ; i < arr.length ; i++){
sum += arr[i];
if(fmap.containsKey(sum)){
int length = i - fmap.get(sum);
if(length > max)
max = length;
}
else{
fmap.put(sum,i);
}
}
return max;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int[] arr = new int[scn.nextInt()];
for (int i = 0; i < arr.length; i++) {
arr[i] = scn.nextInt();
}
System.out.println(solution(arr));
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/largest-subarray-with-zero-sum-official/ojquestion
Comments