Array Nesting


  • 0

    Click here to see the full article post


  • 0
    J

    There seem to be a few minor typoes in this article.

    In the Time complexity section, it reads " loop body will be executed $$O(n^2) times. ". I believe the $$O should be formatted as a big O.

    Similarly: "we can put a very large integer value (\text{Integer.MAX_VALUE}) at the position which has been visited" should probably have that wall of escaped text handled somehow.

    Otherwise informative and helpful article!


  • 0

    @jobjobsteven Thanks. I've corrected the n^2 factor. But couldn't understand your viewpoint about \text{Integer.MAX_VALUE}.


  • 0
    S

    So I thought bruteforce algorithm explanation assumes that cycle of shape O (end resumes at start), but cycle could also be of shape __O (end resumes after start) in which case it will end up in infinite loop as control will never visit start but will looping in a cycle, but then I realized each element of array must be unique as it must range from 0 to n-1 in an array of size n. Having __O loop means at least two items point back to same index, which is impossible.....just posting it so others can know why __O type of cycle is not possible and bruteforce will always work


  • 0

    I suggest flipping the visited elements of the array in Approach #3 (i.e turn the value 6 into -6, etc), because then you can restore the original array very easily when you've found your answer.


  • 0
    Y

    Agree with @DeusVult


  • 0
    L

    @DeusVult
    Zero is present in an array, so we need to handle this by subtracting 1, so k turns into -k-1


  • 0
    G

    Approach #2 Python TLE.


  • 0
    G

    Oh, sorry I forget to set visited[start] = True


  • 0
    Z

    if (res > nums.length / 2) add this code at the end of while, you can just return res


Log in to reply
 

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