Given an array of length n having integers 0 to n1 in unsorted order.
Please modify this array such that the value at a[i] becomes a[a[i]].
For example, if a[0] = 5, a[0] will have value a[5] and so on.
e.g. {2, 4, 3, 1, 0} => {3, 0, 1, 4, 2}
This should take O(n) time complexity.
Change array inplace


Could you please give the question an actual title? Not "Adobe Interview Question", otherwise there will be many questions with the same title.
You may add the company name to the tag. To see how, please read this for more information.




@1337c0d3r Given an array of length n having integers 0 to n1 in unsorted order. If all numbers exist there would not have duplicates

@1337c0d3r yes, right. I think that here the trick is that every permuatation is represented as a product of disjoint cycles, and we have to follow all cycles. When we finish one cycle, I suggest to mark numbers from the cycle in some way (put them negative) to avoid visiting the same cycle twice In the example above we have only one cycle (023140)

@1337c0d3r My understanding is that there is no duplicate, just 0 to n1 every number appear once.

Here are my implementations.
Method 1, visited numbers in the cycle are set negativevoid changeInPlace(int[] nums) { int maxVal = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { int startIndex = i; int nextIndex = nums[startIndex]; while (i != nextIndex) { int next = nums[nextIndex]; swap(nextIndex,startIndex, nums); nums[startIndex]+=maxVal; startIndex = nextIndex; nextIndex = next; } nums[startIndex]+=maxVal; } } for (int i = 0;i < nums.length; i++) { System.out.println(nums[i]maxVal); } }
Another test which is very illustrative to observe multiple cycles is : {6,4,2,3,1,5,0}
Time complexity O(n)
Method 2, visited numbers in the cycle are increased with nums.length
Here is an more triecker way :void changeInPlace(int[] nums) { for (int i = 0; i < nums.length; i++) { if (nums[i] < nums.length) { int startIndex = i; int nextIndex = nums[startIndex]; while (i != nextIndex) { int next = nums[nextIndex]; swap(nextIndex,startIndex, nums); nums[startIndex]+=nums.length; startIndex = nextIndex; nextIndex = next; } nums[startIndex]+=nums.length; } } for (int i = 0;i < nums.length; i++) { System.out.println(nums[i]nums.length); }
