## Wednesday, May 25, 2016

### Change array in-place

https://discuss.leetcode.com/topic/98/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

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)

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