DevExCode

Sign in to devexcode.com with google.com

To continue, google.com will share your name, email address, and profile picture with this site. See this site's privacy policy.

525. Contiguous Array

ArrayHash TablePrefix Sum

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:

  1. Initialize a hashmap map with key 0 and value -1.
  2. 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).
  3. Iterate through the input array.
  4. For each element, update the count variable accordingly (increment by 1 if it is 1, decrement if it is 0).
  5. If count is already present in the map, calculate the length of the subarray and update maxLen if needed.
  6. If count is not in the map, add it with the current index.
  7. 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.

View Leetcode Problem
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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question