Contiguous Array

LeetCode Q 525 - Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Solution

Our solution will be explained with an example.
input array: [0, 1, 0, 0, 0, 1, 1, 1]
Use a variable sum. Traverse the array, when meet a 0, sum - 1; when meed a 1, sum + 1.
From the following image, we can find that if at any moment, the countcount becomes zero, it implies that we’ve encountered equal number of zeros and ones from the beginning till the current index of the array(ii). Not only this, another point to be noted is that if we encounter the same countcount twice while traversing the array, it means that the number of zeros and ones are equal between the indices corresponding to the equal countcount values.

Therefore, we use a map to store that information. Say key is the sum val, value denotes the index. In every iteration, 1) update sum; 2) see if that sum is already a key of the map, if it is then update maxLen = Max(maxLen, i - map.get(sum)).

Code:

public int findMaxLength(int[] nums) {
	Map<Integer, Integer> map = new HashMap<>();
	int sum = 0, maxLength = 0; map.put(0, -1); 
	for (int i = 0; i < nums.length; i++) {
		if (nums[i] == 0)
			sum--;
		else
			sum++;
		
		if (map.containsKey(sum))
			maxLength = Math.max(maxLength, i - map.get(sum));
		else
			map.put(sum, i);
	}
	return maxLength;
}