# Change array in-place

• Given an array of length n having integers 0 to n-1 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.

• Could you please give the question an actual title? Not "Adobe Interview Question", otherwise there will be many questions with the same title.

• @yrxwin Could we use extra O(n) space?

• @1337c0d3r I though should do in-place, otherwise too simple.

• This post is deleted!

• @yrxwin Fair enough. Does the array have duplicates?

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

• @elmirap Yes, but the problem description did not mention all numbers from 0 to n-1 must exist. @yrxwin could you please confirm?

• @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 (0-2-3-1-4-0)

• @1337c0d3r My understanding is that there is no duplicate, just 0 to n-1 every number appear once.

• Here are my implementations.
Method 1, visited numbers in the cycle are set negative

``````void 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);
}
``````

• It's kind of cheating. I use extra space implicitly because all elements will be much larger after the first loop.

But it works and it's O(n).

``````def changeInPlace(nums):
l = len(nums)
for i in range(l):
nums[i] += (nums[nums[i]] % l) * l
for i in range(l):
nums[i] /= l
``````

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