Change array in-place


  • 0
    Y

    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.


  • 0

    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.


  • 0

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


  • 0
    Y

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


  • 0
    This post is deleted!

  • 0

    @yrxwin Fair enough. Does the array have duplicates?


  • 0

    @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


  • 0

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


  • 0

    @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)


  • 0
    Y

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


  • 0

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

  • 1
    P

    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
    

  • 0

Log in to reply
 

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