What if input can be negative?


  • 0
    M

    I was thinking an idea with arbitrary input for a long time, but nothing came out. Is that possible to develop a linear time and constant space solution if input can be negative??


  • 4

    I doubt it. Here's a vague argument against it:

    With negative numbers, you could have a path like this:

    1-level:   +--+     +--+  +--------+
               |  |     |  |  |        |           ...
    0-level:   +  +-----+  +--+        +-- ...
    

    That is, you could encode a binary string, i.e., arbitrary data, in the path. And at some point the path could go above the 1-level, then somewhere left, and down to the 1-level, essentially testing a certain bit. Any bit could get tested, and if you don't go through the path again, you'd have to test the bit with just the O(1) data you kept. Which would mean you'd have a way to compress arbitrary data into O(1) space, which is impossible. So if you use only O(1) space, you'd have to go through the path again.

    Now imagine the 1-level isn't just one unit above the 0-level but many units, and the bit-width is also wide. So that the path doing a bit-test over a 0-bit can go back up, move to another bit, test that one, move back up and somewhere else and test more bits, all without crossing. This way I could test many bits and you'd have go through the path many times, costing more than O(n) time.


Log in to reply
 

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