Java O(N) time O(1) space with Explanation and Proof
This the code I use:\njava\npublic class Solution {\n    public int arrayNesting(int[] nums) {\n        int n = nums.length, max = 0;\n        for (int i = 0; i
This the code I use:\n```java\npublic class Solution {\n    public int arrayNesting(int[] nums) {\n        int n = nums.length, max = 0;\n        for (int i = 0; i < n; i++) {\n            int index = i, count = 0;\n            while (nums[index] < n && nums[index] != i) {\n                count++;\n                nums[index] += n;\n                index = nums[index] - n;\n            }\n            if (++count > max)\n                max = count;\n            if (max >= (n + 1) / 2)\n                return max;\n        }\n        return max;\n    }\n}\n```\nThe given condition that **the index domain is the same as the value domain** is frequently encountered in Leetcode problems. When we have this condition, I tend to think of using a technique I call **inplace flag**. Instead of using an extra `visited` array, we can just mutate the input array to reflect the flag information we want.\n\nThe usual inplace flagging techniques include:\n* negating: negate to reflect one visit, use `abs` to get the original value. This only works to detect odd numbers of previous occurrence. It is not appropriate for this problem also because the value can actually be 0 in this problem, so negating 0 does not really flag anything.\n* module (which I used here): add one `n` to reflect a visit. Mod `n` with the entry to get the original value.\n* sorting: put each number into its corresponding index. This is not recoverable with O(1) space, so not considered here.\n\nRegarding the problem of **Input Pollution**, it is actually easily fixable when using **inplace flagging**, albeit in a way some may argue imperfect. We can just recover the original input array before returning at the end. For negating, just do `abs`; for module method, just mod `n` at the end. This method fixes the problem in some situation but may still cause problem in a multithreading context.\n\n## Proof of this method\nFirst, I personally like this explanation:\n\n@szlghl1 said in [\\[C\\+\\+\\] \\[Java\\] Clean Code \\- O\\(N\\)](/post/201606):\n> Just some supplement.\n> \n> From the statement "The array of size N contains number [0, N-1]", we can know that in-degree of all nodes are exactly one (n different edges for n nodes).\n> \n> Therefore the graph should consist of several cycles and the cycles have no "tails". That's why we can skip the visited nodes, where to begin in a visited cycle doesn't matter in this circumstance.\n\nIt's concise and good enough for this problem. Also, I have not taken any automata course or learned anything about FSM theory. I have a feeling there are some theorems there to make the proofs here trivially easy. But again, I don't know any.\n\nBut in case you are into a more verbose proof, here goes.\n\n## Lemma 1: when we start from any `k`, we will eventually go back to `k`.\n**Proof**: \nFirst, let's understand each entry of `A[i] = e` as a mapping `i -> e`. Let's simplify. Suppose that there is no `k -> k` mapping for any `k`. That is no `k` is its own value. Then we ca easily see that there will be a cycle and when we start from `k` we will get back: there are only `n` distinct numbers in total. We get a different number each iteration, and then we are guaranteed to have a cycle somewhere.\nOne caveat: what if there was a cycle when we start from `k`, but the cycle does not actually contain `k` itself? like `k -> a -> b -> c -> a`? This is also impossible, because in such a situation you will see that `a` actually belongs to two different mappings where it's a descendant: `k -> a` and `c -> a`. No number can have two different parents because that would mean in the original array, two different indices have the same value, that is just illegal.\n\nNow, what if there are actually *one* `k -> k` mappings? Just think of the subproblem formed by the `N-1` numbers: the lemma is valid in this subproblem. Regarding the sole `k -> k` itself, it's a cycle already, and does not undermine the proof of the lemma. \nWhat if there are more such `k -> k` mappings? Just think inductively. They don't matter. \n**End Of Proof**\n\nNow, lemma 1 proved why we do the duplicate detection as the loop header. But what about the *visited flag** part? Why is it that as long as we found a visited number, we can leave it there because it's already covered by some cycle from a previous `i`?\n\n## Lemma 2: All cycles are disjoint.\n**Proof**: to make the lemma easier to prove, we rephrase:\nIf we start from `k` and reached a visited `t`, then `k` must belong to the same cycle as `t`.\n\nThis is actually easily provable using the same thought regarding the  `k -> a -> b -> c -> a` above: now that `t` is visited, we know that `t` is in a cycle. And now that `k` can reach `t`, then if we start from `k`, we must enter this very cycle at some point. Say this point is `t'` (`t'` can be the same as `t`):\n* if `t'` is not `t`: then we know that we must have a mapping `k -> t'`. Suppose `k` is not in this cycle for the purpose of contradiction. Then there must be a node `t''` in the cycle which is not `k` but which also provides `t'' -> t'`. Now `t'` has two distinct parents, and that is illegal. Thus contradiction.\n* if `t'` equals `t`: so we have `k -> t`. Do something similar to the above case and it's also easily provable.\n**End of Proof**\n\nI think these two lemmas suffice for understanding the problem and the algorithm now. Hope this helps.
[]