Clean Java Slow/Fast Solution


  • 3
    G
    This post is deleted!

  • 0
    M

    @gc19931011 I came up with a quite similar solution.

    Since there must be more than one element along the loop I gained a bit of speed by adding a check

    if (nums.length <= 2) return false;
    

    upfront.

    First I used a forward flag like you did but came up with

    nums[start] ^ nums[currentIndex]) < 0
    

    for the directory change check and with

    int nextIndex = (currentIndex + numbers[currentIndex]) % numbers.length;
    if (nextIndex < 0) nextIndex = numbers.length + nextIndex;
    

    to calculate the next index.


  • 1
    Y

    This solution is incorrect and fails the test case [2, 2, -1, 2], which should give "true" but the given solution returns "false". Correct me if I am wrong, thanks.


  • 0
    M

    @Yoursong the example you provided is not valid and should return false because the loop changes the direction.

    The question states:

    The loop must be "forward" or "backward'. 
    

    First it jumps forward from index 0 to index 2. From there it jumps backwards to index 1. The change of directions meas it is neither forward nor backward.


  • 0
    Y

    @magic_al The loop doesn't need to start from index 0. In my example there is a forward loop index 1 -> index 3 -> index 1 -> index 3 -> ... so it should return "true".


  • 0
    M

    @Yoursong ah I see, your right. I didn't consider that.

    The question also states:

    A loop starts and ends at a particular index with more than 1 element along the loop.
    

    I guess it depends how you define start and stop. The way I see it is that the loop stops as soon as it reaches the start. Then since there is only one element between start and stop it is false.


  • 1
    Y

    @magic_al how about this test case [2, 2, -1, 1, 2]. There is a forward loop index 1 -> index 3 -> index 4 -> index 1 -> index 3 -> *** but this solution gives "false".

    I guess what is wrong with this solution is that it should not return false immediately after it detects a change of direction. It should continue trying other possibilities.


  • 0
    X

    Failed in this testcase : [8,1,1,1,1,1,1,3,-8]


  • 0
    M

    @Yoursong you are right of course. It should continue to the next iteration rather than return false.


  • 0
    I

    This solution fails in case [2, 1, 2, 1, 5]


Log in to reply
 

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