Longest Subarray with Equal 0s and 1s
This program finds longest subarray with equal number of 0s and 1s.
Problem Statement
Write a Java program to find longest subarray with equal 0s and 1s.
Source Code
| 1 | import java.util.HashMap; |
| 2 | public class LongestEqualSubarray { |
| 3 | public static void main(String[] args) { |
| 4 | System.out.println("Eduinq Longest Subarray with Equal 0s and 1s"); |
| 5 | int[] arr = {0,1,0,1,1,0,0}; |
| 6 | HashMap<Integer,Integer> map = new HashMap<>(); |
| 7 | int sum=0, maxLen=0; |
| 8 | for(int i=0;i<arr.length;i++){ |
| 9 | sum+= (arr[i]==0 ? -1 : 1); |
| 10 | if(sum==0) maxLen=i+1; |
| 11 | if(map.containsKey(sum)) maxLen=Math.max(maxLen,i-map.get(sum)); |
| 12 | else map.put(sum,i); |
| 13 | } |
| 14 | System.out.println("Longest subarray length = "+maxLen); |
| 15 | } |
| 16 | } |
Program Output
Eduinq Longest Subarray with Equal 0s and 1s Longest subarray length = 6
Explanation
Each 0 is treated as -1 to balance the counts, and a running sum tracks the difference between 1s and 0s while a HashMap stores the earliest index of each sum value, updating the maximum length whenever a sum repeats, finding the longest balanced subarray.