LeetCode 525: Contiguous Array Solution

Master LeetCode problem 525 (Contiguous Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

525. Contiguous Array

Medium

Array Hash Table Prefix Sum

Problem Explanation

Explanation:

We can solve this problem by keeping track of the running sum of zeros and ones encountered while iterating through the array. We store the running sum in a hashmap where the key is the running sum and the value is the index at which that running sum was encountered. If we encounter the same running sum again, it means that the subarray between the two occurrences has equal numbers of zeros and ones. We calculate the length of this subarray and update the maximum length found so far.

Algorithm:

Initialize a hashmap map with key 0 and value -1.
Initialize variables maxLen to store the maximum length found so far and count to keep track of the running sum (count of ones - count of zeros).
Iterate through the input array.
For each element, update the count variable accordingly (increment by 1 if it is 1, decrement if it is 0).
If count is already present in the map, calculate the length of the subarray and update maxLen if needed.
If count is not in the map, add it with the current index.
Return maxLen as the result.

Time Complexity:

The time complexity of this approach is O(n), where n is the length of the input array.

Space Complexity:

The space complexity of this approach is O(n), where n is the length of the input array.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 525 (Contiguous Array)?

This page provides optimized solutions for LeetCode problem 525 (Contiguous Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 525 (Contiguous Array)?

The time complexity for LeetCode 525 (Contiguous Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 525 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 525 in Java, C++, or Python.

Back to LeetCode Solutions