Why {3, 1, 2} is a loop and {-1, -2, -3, -4, -5} is not?


  • 9
    A

    In the {3, 1, 2} case we jump and return to the same position. So there is really one step and it is considered a loop. Is it because we "fly over 2 positions"? Fine. Then why {-1, -2, -3, -4, -5} is not a loop? We make one step from -1 to -5 and then we do exactly the same as in case {3, 1, 2) but to the left.

    For this question to be reasonable the description should take these cases:

    {-1, 2} -> False

    {-2, 1, -1, -2, -2} -> False

    {2, -1, 1, -2, -2} -> False

    {3, 1, 2} -> True

    {-1, -2, -3, -4, -5} -> False

    and spell out why exactly the expected results are the way they are.


  • 3
    L

    I guess the reason is that the initial position is not necessarily the zeroth element. For {3, 1, 2}, if we count from 1, then there is a cycle 1 -> 2 -> 1 with more than one element, which is valid. For {-1, -2, -3, -4, -5}, no matter what position we start from, we always end up with a cycle -5 -> -5, which includes only one element and is thus invalid.


  • 0
    R

    I think every element has to be repeated at least twice in the cycle and in the case you pointed out -1 only repeats once.


Log in to reply
 

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