One pass,use a HashMap to record 0-1 count difference


  • 24
    public class Solution {
        public int findMaxLength(int[] nums) {
            HashMap<Integer,Integer> map=new HashMap<>();
            map.put(0,-1);
            
            int zero=0;
            int one=0;
            int len=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]==0){
                    zero++;
                }else{
                    one++;
                }
                
                if(map.containsKey(zero-one)){
                    len=Math.max(len,i-map.get(zero-one));
                }else{
                    map.put(zero-one,i);
                }
            }
            
            return len;
        }
    }

  • 0
    D

    Thanks. This was very helpful.


  • 1

    nice solution without modifying current array content.


  • 0
    D

    @bxiao0801
    Thanks for sharing this. Can you please explain the logic behind this solution?


  • 1
        public int findMaxLength(int[] nums) {
          int count = 0;
          Map<Integer, Integer> map = new HashMap();//Key:count value:index
          map.put(0, -1);  // start from count 0, where is a virtual index of -1. 
          int res = 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)); // not replacing the index, the value in map will always be first index
            } else {
               map.put(count, i); 
            } 
          }  
          return res;  
        }

  • 0

    It can be further simplified by using just one number to record the number of diffs
    zero > 0 means we have more zeros than ones
    zero < 0 means we have more ones than zeros
    zero == 0 means we have equal number of ones and zeros
    For example, if at any index i we have zero = 1, then we have 1 diff (1 more 0s than 1s), we record it in the HashMap, and if later at index j we meet another situation that zero = 1, this means from the index i till the index j, the number of 0s and 1s are the same.

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

Log in to reply
 

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