Anyone want to discuss who hasn't figured this one out yet?


  • 0
    G

    Hey, first timer here, wondering if anyone would like to throw clues at me or put our heads together to try to figure this one out without looking at solutions.

    I realized quickly (after figuring out brute force) that this was some sort of dp problem. My solution that I came up with afaik works however was too slow, I timed out after the 22nd test. My dp is super rusty.

    I'm going to try to explain my solution. The value I'm hashing is "balance" which is 0 if there are equal number of 0s and 1s and incrementally negative or positive if there is 1, 2, 3, etc. more 1s than 0s or vice versa. My solution is essentially looping through and creating new "balance" values by looking into my hash. Each outer loop I increase my subarray length by 1. I'm stuck here, I feel like I'm missing a key part in structuring my loops such that the solution is much faster...


  • 0
    G

    In fact, I don't think my solution is DP at all :D


  • 1

    @georgeqwu Hint: one loop is enough. Otherwise your idea seems correct.


  • 0
    T
    This post is deleted!

  • 0
    G

    @dettier

    If I hash the maxLengthOfBalancedSubList at iteration i, I don't know which subList up to index i contains the maxLength, right? But if I compare the number at interation i with all possible balances from hashed subLists seen until now, then I can update both maxLength... Updating the hash in this way isn't linear though :/


  • 1

    @georgeqwu Think of it this way -- if the list [0...i] is unbalanced, what is the minimum amount of items should you remove from the beginning to make it balanced?


Log in to reply
 

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