525. Contiguous Array.md

525. Contiguous Array

---

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

Example 1:

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

Example 2:

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

Note:

• The length of the given binary array will not exceed 50,000.

---

Solution

• mine

  • Java

    Brute Force [Time Limit Exceeded]

    //O(N^2)time O(1)space
    public int findMaxLength(int[] nums) {
        int maxlen = 0;
        for (int i = 0; i < nums.length; i++) {
            int zeroes = 0, ones = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 0) {
                    zeroes++;
                } else {
                    ones++;
                }
                if (zeroes == ones) {
                    maxlen = Math.max(maxlen, j - i + 1);
                }
            }
        }
        return maxlen;
    }
    

    HashMap Runtime: 20 ms, faster than 77.91%, Memory Usage: 49.2 MB, less than 100.00% of Java online submissions

    //O(N)time O(N)space
    public int findMaxLength(int[] nums) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(count)) {
                res = Math.max(res, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return res;
    }
    

    Extra Array Runtime: 7 ms, faster than 98.30%, Memory Usage: 48.1 MB, less than 100.00% of Java online submissions

    //O(N)time O(N)space
    public int findMaxLength(int[] nums) {
        int res = 0;
        int[] t = new int[nums.length * 2 + 1];
        Arrays.fill(t, -2);
        t[nums.length] = -1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i] == 0 ? -1 : 1;
            int index = count + nums.length;
            if(t[index] != -2){
                res = Math.max(res, i - t[index]);
            }else{
               t[index] = i;  
            }
        }
        return res;
    }
    

---

• the most votes

  • Extra Array Runtime: 7 ms, faster than 98.30%, Memory Usage: 48.5 MB, less than 100.00% of Java online submissions

    //O(N)time O(N)space
    public int findMaxLength(int[] nums) {
        int[] arr = new int[2 * nums.length + 1];
        Arrays.fill(arr, -2);
        arr[nums.length] = -1;
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 0 ? -1 : 1);
            if (arr[count + nums.length] >= -1) {
                maxlen = Math.max(maxlen, i - arr[count + nums.length]);
            } else {
                arr[count + nums.length] = i;
            }
    
        }
        return maxlen;
    }
    

  • HashMapRuntime: 21 ms, faster than 38.11%, Memory Usage: 49.5 MB, less than 100.00% of Java online submissions

    //O(N)time O(N)space
    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 = 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;
    }