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


Log in to reply
 

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