wayetan
1/7/2014 - 8:20 AM

LargestSubarrayWithEqualNumberof0sAnd1s

LargestSubarrayWithEqualNumberof0sAnd1s

public class LargestSubarrayWithEqualNumberof0sAnd1s {
    public static void findLargestSubarray(int[] array) {
    	// record the difference
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 0);
		int begin = 0;
		int max = 0;
		int current = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 0) {
				current--;
			} else {
				current++;
			}
			Integer p = map.get(current);
			if (p == null) {
				map.put(current, i + 1);
			} else {
				int l = p.intValue();
				if ((i + 1 - l) > max) {
					max = i + 1 - l;
					begin = l;
				}
			}

		}
		for (int j = begin; j < begin + max; j++) {
			System.out.print(array[j]);
		}

	}
}