algoadvance

Leetcode 525. Contiguous Array

Problem Statement

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

Clarifying Questions

  1. What is the range of the array length?
    • The length of the array will be in the range [1, 105].
  2. What are the possible values in the array?
    • The array will contain only binary values (0s and 1s).
  3. Are there any constraints on memory or runtime
    • Optimize for both time and space complexity as much as possible.

Strategy

To solve the problem, we need to find the longest contiguous subarray with an equal number of 0s and 1s. To achieve this, we can use a hashmap to track the first occurrence of each count difference we encounter as we iterate through the array.

Here’s the detailed approach:

  1. Transform the array: Treat 0 as -1. This way, the problem reduces to finding a subarray with a sum of zero.
  2. Use a hashmap to store counts: Use a hashmap to store the first occurrence of each count. This helps in quickly finding the maximum length of a subarray with a sum of zero.
  3. Iterate through the array: As you iterate through the array, keep a running sum (cumulative sum). Whenever the cumulative sum reaches the same value at different points, it means the subarray between these points has a sum of zero.
  4. Update the maximum length: If the cumulative sum has been seen before, update the maximum length using the difference between the current index and the stored index from the hashmap.
  5. Edge Case: Ensure to handle cases where the entire array or a part of it might already have an equal number of 0s and 1s.

Code

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> count_map;
        count_map[0] = -1; // To handle the case when subarray starts from index 0
        int max_length = 0;
        int count = 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            count += (nums[i] == 1) ? 1 : -1;
            
            if (count_map.find(count) != count_map.end()) {
                max_length = max(max_length, i - count_map[count]);
            } else {
                count_map[count] = i;
            }
        }
        
        return max_length;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the length of the array. This is because we make a single pass through the array, with constant time operations for each element using the hashmap.

Space Complexity

The space complexity is O(n) as we might store up to n entries in the hashmap in the worst case.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI