Java Solution make 0 to -1 O(n) time and O(n) space


  • 0

    make all the 0 in the original array to -1, and use HashMap to record all the "NEW" running sum encountered as of now. Don't update the 'existing' sum in the HashMap since the existing one represents the longest contiguous array with the equal count of 0 and 1 so far.

    public class Solution {
        public int findMaxLength(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int[] copy = nums.clone();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (copy[i] == 0) copy[i] = -1;
            } 
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int sum = 0;
            int res = 0;
            for (int i = 0; i < n; i++) {
                sum += copy[i];
                if (map.containsKey(sum)) {
                    res = Math.max(res, i - map.get(sum));
                }
                else map.put(sum, i);
            }
            return res;
        }
    }
    

Log in to reply
 

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