Algorithm


Problem Name: 525. Contiguous Array

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

 

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct elem_s {
    int n;
    int idx;
    struct elem_s *shadow;
} elem_t;
​
#define SZ 10240
​
void free_set(elem_t **set, int sz) {
    int i;
    elem_t *e, *s;
    for (i = 0; i  <  sz; i ++) {
        e = set[i];
        while (e) {
            s = e->shadow;
            free(e);
            e = s;
        }
    }
}
void put(elem_t **set, int n, int idx) {
    int k = n; //(n >= 0) ? n : -n;
    elem_t *e = malloc(sizeof(elem_t));
    e->n = n;
    e->idx = idx;
    e->shadow = set[k % SZ];
    set[k % SZ] = e;
}
elem_t *lookup(elem_t **set, int n) {
    int k = n; //(n >= 0) ? n : -n;
    elem_t *e = set[k % SZ];
    while (e && e->n != n) e = e->shadow;
    return e;
}
int findMaxLength(int* nums, int numsSize) {
    int n[2] = { 0 };
    int i, d = 0;
    elem_t *buff[SZ * 2] = { 0 };
    elem_t *e, *set = &buff[SZ];
    
    if (!numsSize) return 0;
    
    put(set, 0, -1);
    
    for (i = 0; i  <  numsSize; i ++) {
        n[nums[i]] ++;
        e = lookup(set, n[0] - n[1]);
        if (!e) {
            put(set, n[0] - n[1], i);
        } else if (d  <  i - e->idx) {
            d = i - e->idx;
        }
    }
    
    free_set(buff, sizeof(buff)/sizeof(buff[0]));
​
    return d;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1]

Output

x
+
cmd
2

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        for(auto& x: nums) if(!x) x = -1;
        unordered_map < int, int>m;
        m[0] = -1;
        int sum = 0, maxlen = 0;
        for(int i = 0; i  <  nums.size(); i++){
            sum += nums[i];
            if(m.count(sum)) maxlen = max(maxlen, i - m[sum]);
            else m[sum] = i;
        }
        return maxlen;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1]

Output

x
+
cmd
2

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int findMaxLength(int[] nums) {
    Map map = new HashMap<>();
    map.put(0, -1);
    int maxLength = 0;
    int count = 0;
    for (int i = 0; i  <  nums.length; i++) {
      count += nums[i] == 0 ? -1 : 1;
      if (map.containsKey(count)) {
        maxLength = Math.max(maxLength, i - map.get(count));
      } else {
        map.put(count, i);
      }
    }
    return maxLength;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1,0]

Output

x
+
cmd
2

#4 Code Example with Javascript Programming

Code - Javascript Programming


const findMaxLength = function(nums) {
  let res = 0, sum = 0
  const hash = {0: -1}, n = nums.length
  
  for(let i = 0; i  <  n; i++) {
      const cur = nums[i]
      sum += cur === 0 ? -1 : 1
      if(hash[sum] != null) {
          res = Math.max(res, i - hash[sum])
      } else {
          hash[sum] = i
      }
      
  }
  
  return res
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1,0]

Output

x
+
cmd
2

#6 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;

namespace LeetCode
{
    public class _0525_ContiguousArray
    {
        public int FindMaxLength(int[] nums)
        {
            var map = new Dictionary < int, int>();
            map.Add(0, -1);

            var maxlen = 0;
            var 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[count]);
                else
                    map.Add(count, i);
            }

            return maxlen;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1]

Output

x
+
cmd
2
Advertisements

Demonstration


Previous
#524 Leetcode Longest Word in Dictionary through Deleting Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#526 Leetcode Beautiful Arrangement Solution in C, C++, Java, JavaScript, Python, C# Leetcode