Python and Java with little tricks (incl. a oneliner :-)


  • 11

    Keeping track of the balance (number of ones minus number of zeros) and storing the first index where each balance occurred.


    Python

    Keeping the balance in units of 0.5 which makes the update expression short (not that num * 2 - 1 or 1 if num else -1 would be terribly long):

    def findMaxLength(self, nums):
        index = {0: -1}
        balance = maxlen = 0
        for i, num in enumerate(nums):
            balance += num - 0.5
            maxlen = max(maxlen, i - index.setdefault(balance, i))
        return maxlen
    

    Just for fun as an ugly one-liner:

    def findMaxLength(self, nums):
        return reduce(lambda(f,b,m),(i,x):(f,b+x-.5,max(m,i-f.setdefault(b+x-.5,i))),enumerate(nums),({0:-1},0,0))[2]
    

    Java

    Using putIfAbsent so I only need one map function call per number.

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> index = new HashMap<>();
        index.put(0, -1);
        int balance = 0, maxlen = 0;
        for (int i = 0; i < nums.length; i++) {
            balance += nums[i] * 2 - 1;
            Integer first = index.putIfAbsent(balance, i);
            if (first != null)
                maxlen = Math.max(maxlen, i - first);
        }
        return maxlen;
    }
    

    Could avoid using Math.max like this:

            if (first != null && i - first > maxlen)
                maxlen = i - first;

  • 0
    Z

    0.5 is interesting :o)


  • 0
    S

    nice trick with putIfAbsent.

    multiplication and subtraction can be avoided using an array.

    int[] offset = {-1,1}; // before for loop
    balance += offset[nums[i]];


  • 0

    @Sylar Does that have some advantage?


  • 0
    S

    @StefanPochmann It can map 0 -> -1 and 1 -> 1 without doing any explicit math. It probably doesn't make any difference to runtime.


  • 0
    M

    @StefanPochmann
    Thanks for sharing this.
    Can you please explain the logic in more detail?


Log in to reply
 

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