Java one pass O(n) solution with explanation


  • 3
    Y

    diff[i] is "count of 1s" minus "count of 0s" so far.

    For given i and j, if diff[i] == diff[j], then the subarray between i and j is a contiguous array as defined in the questions.

    For any value of diff[], we save the index of the first item in the hashmap. Then once the value appears again, we get the length of the subarray between the current index and the index of the first item.

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

  • 0
    H

    @yuhaowang001 it can be more easier.

    class Solution {
    public:
    	int findMaxLength(vector<int>& nums) {
    		map<int, int> m;
    		m.insert(pair<int, int>(0, 0));
    		int ans = 0, k = 0;
    		for (int i = 0; i < nums.size(); i++) {
    			k = k + (nums[i] == 0 ? -1 : 1);
    			if (m.find(k) != m.end())
    				ans = ans < i + 1 - m[k] ? i + 1 - m[k] : ans;
    			else
    				m[k] = i + 1;
    		}
    		return ans;
    	}
    };
    

  • 0
    D

    @yuhaowang001
    Thanks for sharing the solution.
    I do not understand the rationale behind why does subtracting the previous index from the current index for the same value give us the correct solution?


  • 0
    J

    Let me add some explanation.
    If we keep track of the total count of ones and zeros from 0 to len - 1, then to valid whether the subarray from i to j is valid, we just have to check if ones[j] - ones[i - 1] == zeros[j] - zeros[i - 1].
    Naively it will take O(N^2) to compute. But that equation is the same as ones[j] - zeros[j] == one[i - 1] - zeros[i - 1], and it is diff[j] == diff[i - 1], then we can use hashmap to reduce the time complexity to O(N).
    Here is my implementation:

    public class Solution {
        public int findMaxLength(int[] nums) {
            HashMap<Integer, Integer> diff2idx = new HashMap<>();
            int res = 0;
            int diff = 0;
            diff2idx.put(0, -1);
            int ones = 0;
            for (int i = 0; i < nums.length; i++) {
                ones += nums[i];
                diff = ones - (i + 1 - ones); // ones - zeros
                if (diff2idx.containsKey(diff)) {
                    res = Math.max(res, i - diff2idx.get(diff));
                } else {
                    diff2idx.put(diff, i);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.