525. Contiguous Array


Problem Description

The problem provides an array nums consisting of only binary digits (0s and 1s). The task is to find a contiguous subarray where the number of 0s and 1s are equal, and this subarray should be the longest of any such subarrays in the given array. The length of this subarray is what we need to return.

Contiguous means that the elements are consecutive, without any interruptions from elements that are not part of the subarray.

For example, if the input array is [0,1,0], the longest contiguous subarray with equal number of 0s and 1s would be [0, 1] or [1, 0], and the length would be 2.

Intuition

The intuition behind the solution comes from the understanding that if we were to maintain a running difference between the number of 0s and 1s, a subarray with an equal number of 0s and 1s would correspond to a situation where the difference becomes zero. However, since we want to find the longest such subarray, we need a way to record the occurrences of the running difference.

Here's how we arrive at the solution:

  1. We use a variable to keep a running count of the number of 1s and 0s we've seen so far. Let's increment this count by 1 for every 1 we see and decrement it by 1 for every 0 we see in the array.
  2. We use a hashmap to keep track of the earliest index where each running count value has appeared.
  3. As we iterate through the array:
    • We update the running count based on the current element.
    • We check if the running count is already in the hashmap. If it's not, we add it to the hashmap with the current index.
    • If the running count is already in the hashmap, it means we've found a subarray where the difference between the number of 0s and 1s is the same as some previous index, which implies that we have an equal number of 0s and 1s in between these two indexes.
    • We calculate the length of this subarray by subtracting the previous index of this running count value from the current index and check if it's greater than the length of the previous longest subarray we've found. If it is, we update our answer.
  4. The maximum length found in this manner is the length of the longest contiguous subarray with equal numbers of 0s and 1s.

By following this approach, the algorithm elegantly handles the issue without having to compare every possible subarray, thereby reducing the complexity from O(n^2) to O(n).

Learn more about Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Solution Approach

The implementation of the solution utilizes a hashmap (dictionary in Python) and a single pass through the array, taking advantage of the prefix sum concept and storing indices where each sum first occurs. Here's a step-by-step breakdown of the code used:

  1. Initialize a variable s to 0, which will be used to keep track of the running count (prefix sum) of the number of 1s and 0s seen so far in the array. When a 1 is encountered in the array, s is incremented by 1, and for a 0, s is decremented by 1.

  2. Initialize another variable ans to 0, which will store the maximum length of the subarray found during the process.

  3. Create a hashmap mp with one initial key-value pair {0: -1}, which signifies that before we start processing the array, the running count is 0 and its index is -1 (this helps handle cases where the subarray starts from index 0).

  4. Iterate through the array using a loop, and for each element at index i:

    • Update the running count s. If the value v is 1, increment s by 1. If not, decrement s by 1 (s += 1 if v == 1 else -1).
    • Check if the running count s is already in the hashmap mp.
      • If it is, compute the length of the subarray (i - mp[s]) which represents the distance from the first occurrence of this running count to the current index. Compare and update the answer ans to be the maximum length found so far (ans = max(ans, i - mp[s])).
      • If it is not, add this running count s along with the current index i to the hashmap (mp[s] = i), marking the first appearance of this running sum.
  5. After the loop concludes, the variable ans will hold the maximum length of the longest contiguous subarray with an equal number of 0s and 1s, which the function then returns.

In essence, the algorithm relies on the prefix sum pattern where changes in the running sum are monitored and recorded. When a running sum reoccurs, it indicates a potential subarray of interest. The hashmap acts as an efficient way to keep track of the indices where sums first occur, enabling the calculation of subarray lengths in constant time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's walk through a small example using the given solution approach with the input array nums = [0, 1, 0, 1, 1, 0, 0].

The array is [0, 1, 0, 1, 1, 0, 0]. We initialize s = 0 for the running count, ans = 0 for the maximum length of subarray, and a hashmap mp with {0: -1}.

Now, we iterate over the array and update our running count s, the hashmap mp, and our answer ans.

  • Step 1: i = 0, nums[i] = 0. s = -1 (decremented from 0). This -1 is not in mp, so mp is now {0: -1, -1: 0}. ans remains 0.
  • Step 2: i = 1, nums[i] = 1. s = 0 (incrementing from -1). s is in mp at index -1, so ans = 1 - (-1) = 2.
  • Step 3: i = 2, nums[i] = 0. s = -1 (decremented from 0). s is in mp, so the length of this subarray is 2 - 0 = 2. ans = max(2, 2) = 2.
  • Step 4: i = 3, nums[i] = 1. s = 0 (incrementing from -1). s is in mp, so the length of this subarray is 3 - (-1) = 4. ans = max(2, 4) = 4.
  • Step 5: i = 4, nums[i] = 1. s = 1 (incremented from 0). This 1 is not in mp, so mp is now {0: -1, -1: 0, 1: 4}. ans remains 4.
  • Step 6: i = 5, nums[i] = 0. s = 0 (decremented from 1). s is in mp, so the length of this subarray is 5 - (-1) = 6. ans = max(4, 6) = 6.
  • Step 7: i = 6, nums[i] = 0. s = -1 (decremented from 0). s is in mp, so the length of this subarray is 6 - 0 = 6. ans remains 6 as it's equal to the current maximum.

After going through the entire array, the longest contiguous subarray with an equal number of 0s and 1s is [1, 0, 1, 1, 0, 0] starting from index 1 to index 6 and has a length of 6. This is the final answer and is the value of ans after iterating through the array.

Not Sure What to Study? Take the 2-min Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Python Solution

1class Solution:
2    def findMaxLength(self, nums: List[int]) -> int:
3        # Initialize the current balance between 0s and 1s and the maximum length found
4        balance = max_length = 0
5        # Create a hash map to store the first occurrence of each balance
6        balance_map = {0: -1}
7      
8        # Iterate over the elements in the array
9        for index, value in enumerate(nums):
10            # Update the balance (+1 for 1, -1 for 0)
11            balance += 1 if value == 1 else -1
12          
13            # Check if the same balance has been seen before
14            if balance in balance_map:
15                # If we have seen this balance before, calculate the length of the subarray
16                # between the previous index and the current index
17                max_length = max(max_length, index - balance_map[balance])
18            else:
19                # If this is the first time we've seen this balance,
20                # store the index for this balance in the hash map
21                balance_map[balance] = index
22      
23        # Return the maximum length of the subarray with equal number of 0s and 1s
24        return max_length
25

Java Solution

1class Solution {
2  
3    // Function to find the maximum length of a contiguous subarray with equal number of 0s and 1s.
4    public int findMaxLength(int[] nums) {
5        // Create a hash map to store the sum so far (key) and its index (value).
6        Map<Integer, Integer> sumToIndexMap = new HashMap<>();
7      
8        // Initialize the sum of elements to 0 and the answer to the max length to 0.
9        sumToIndexMap.put(0, -1); // Sum of 0 is considered to appear before the array starts.
10        int sum = 0, maxLength = 0;
11
12        // Iterate through the array.
13        for (int i = 0; i < nums.length; i++) {
14            // Update sum: +1 for '1', -1 for '0'. This helps in finding equal numbers of 1s and 0s.
15            sum += nums[i] == 1 ? 1 : -1;
16
17            // If the sum has been seen before, it means the subarray between the two indices has
18            // equal number of 0s and 1s.
19            if (sumToIndexMap.containsKey(sum)) {
20                // Update maxLength with the larger value between current maxLength and the distance
21                // between current index and the first index where this sum appeared.
22                maxLength = Math.max(maxLength, i - sumToIndexMap.get(sum));
23            } else {
24                // If sum is not found in the map, add it with its index.
25                sumToIndexMap.put(sum, i);
26            }
27        }
28      
29        // Return the found maximum length.
30        return maxLength;
31    }
32}
33

C++ Solution

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the maximum length of a contiguous subarray with an equal number of 0 and 1.
8    int findMaxLength(vector<int>& nums) {
9        unordered_map<int, int> prefixSumToIndex; // Map to store prefix sum to index mapping.
10        int currentSum = 0; // Current prefix sum.
11        int maxLength = 0; // Maximum length of the subarray found so far.
12        prefixSumToIndex[0] = -1; // Initialize with the base case prefix sum before any element is processed.
13
14        // Iterate through the array.
15        for (int i = 0; i < nums.size(); ++i) {
16            // Update the current sum: increment by 1 for a '1', decrement by 1 for a '0'
17            currentSum += nums[i] == 1 ? 1 : -1;
18
19            // Check if the current sum has been seen before.
20            if (prefixSumToIndex.count(currentSum)) {
21                // If yes, calculate the length of the subarray and update the maximum length.
22                maxLength = max(maxLength, i - prefixSumToIndex[currentSum]);
23            } else {
24                // If not, add the current sum and index to the map.
25                prefixSumToIndex[currentSum] = i;
26            }
27        }
28        return maxLength; // Return the maximum length found.
29    }
30};
31

Typescript Solution

1/**
2 * Finds the maximum length of a contiguous subarray with an equal number of 0 and 1.
3 * @param {number[]} nums - The input array containing 0s and 1s.
4 * @return {number} - The maximum length of a contiguous subarray with equal number of 0s and 1s.
5 */
6function findMaxLength(nums: number[]): number {
7    // Create a map to store the sum at each index. The map will help us find when we've seen a sum before.
8    const sumIndexMap = new Map<number, number>();
9    // Initialize sum for index -1 (before the start of the array) to 0.
10    sumIndexMap.set(0, -1);
11    let sum = 0; // This will hold our cumulative sum.
12    let maxLength = 0; // This will store the maximum length we find.
13
14    for (let i = 0; i < nums.length; ++i) {
15        // Update sum: decrement for 0 and increment for 1.
16        sum += nums[i] == 0 ? -1 : 1;
17      
18        // If the sum has been seen before, we have found a subarray with equal number of 0s and 1s.
19        if (sumIndexMap.has(sum)) {
20            // The length is the current index - the previous index where we've seen the same sum.
21            maxLength = Math.max(maxLength, i - sumIndexMap.get(sum)!);
22        } else {
23            // If the sum hasn't been seen before, set the current index as the value for this sum.
24            sumIndexMap.set(sum, i);
25        }
26    }
27  
28    // Return the maximum length found.
29    return maxLength;
30}
31
Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Time and Space Complexity

The time complexity of the code is O(n), as it iterates through the nums list once, performing a constant amount of work for each element (checking and updating a dictionary, and updating a running sum and maximum length).

The space complexity of the code is O(n), in the worst case, where n is the number of elements in the input list nums. This is because the dictionary mp can potentially store an entry for each unique sum encountered, which corresponds to each index in the list in the worst-case scenario.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫