Java O(1) space solution of Rotate Array.


  • 81
    V

    The basic idea is that, for example, nums = [1,2,3,4,5,6,7] and k = 3, first we reverse [1,2,3,4], it becomes[4,3,2,1]; then we reverse[5,6,7], it becomes[7,6,5], finally we reverse the array as a whole, it becomes[4,3,2,1,7,6,5] ---> [5,6,7,1,2,3,4].

    Reverse is done by using two pointers, one point at the head and the other point at the tail, after switch these two, these two pointers move one position towards the middle.

    public class Solution {

    public void rotate(int[] nums, int k) {
    
        if(nums == null || nums.length < 2){
            return;
        }
        
        k = k % nums.length;
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
        
    }
    
    private void reverse(int[] nums, int i, int j){
        int tmp = 0;       
        while(i < j){
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
    

    }


  • 0
    W

    Thank you for the explanation. I understand that this works, but don't really understand why this works. Could you please elaborate on it. Thanks.


  • 2
    V

    [1,2,3,4,5,6,7], n = 7, k = 3. Reverse[1,2,3,4] -------> [4,3,2,1,5,6,7], reverse [5, 6, 7] ------> [4, 3, 2, 1, 7, 6, 5], reverse the whole array ------> [5, 6, 7, 1, 2, 3, 4].

    That is the basic idea of this method, hope can help you out.


  • 0
    M

    Where are you get the idea? I am very appreciate you. It's amazing.


  • 4

    really smart idea, after think a while, the "flip" idea can be used to partition and re-order the array in any way. Just flip individual segment and flip the list of segments. E.g. [1,2,3,4,5,6,7], I want it to be [7, 3,4,5,6, 1,2], first flip individual segment [1,2] -> [2,1], [3,4,5,6] -> [6,5,4,3], [7] -> [7]. Concatenate segments to be [2,1,6,5,4,3,7], finally, flip the whole thing -> [7,3,4,5,6,1,2]


  • 1
    D

    Great idea. but I have a little question. If n doubles, the complexity also doubles. So why is this solution of O(1) instead of O(n)?


  • 0
    S

    He mentioned it's 0(1) SPACE complexity, not runtime.


  • 0
    N

    awesome explanation!


  • 0
    P

    This is an amazing idea...truly!


  • 0

    This is what I am really looking for. Thx


  • 0
    G

    That's a pretty good idea.But why this is not the fastest one.


  • 0
    L

    that's great!


  • 1
    Z

    ah,there is a mistake if you input[1,2,3,4] and k=3,the true is [1,2,3,4],but the fact is [2,3,4,1]
    sorry for my bad english,thank you!


  • 0

    Here're some exploration on why we can do the rotation by first reverse the whole array and then reverse elements from index 0 to k-1, then k to nums.length-1:

    for convenience, write nums.length-->len
    Suppose all elements of nums[] are indexed with:
    0, 1, ..., k-2. k-1, k, k+1, ..., len-2, len-1

    After reversing the whole array, these elements become:
    len-1, len-2, ..., k+1, k, k-1, k-2, ... ,1, 0

    if do this "reverse(nums, 0, k - 1)", correspondingly, we first reverse elements from first one (it's len-1 using original index) to k-1 (i.e. len-k using original index)
    That is , we reverse:
    len-1, len-2, ..., len-k, len-k-1,len-k-2,..., 1, 0
    to len-k, len-k+1,...,len-2,len-1, len-k-1,len-k-2,...,1,0
    |--------- k elements here---------|
    After "reverse(nums, k, nums.length - 1)", the nums array finally becomes:
    len-k, len-k+1,...len-2,len-1, 0, 1, ..., len-k-2, len-k-1
    |---------- k elements---------|
    compared to original array:
    0, 1, ..., k-2. k-1, k, k+1, ..., len-2, len-1
    From the changes of these elemnents position (like 0, it may be intuitive to find the array really has been rotated by k)


  • 3
    X
    k = k % nums.length;
    

    Can somebody tell me why this line is necessary?


  • 1
    N

    @xiaoming8
    For example,
    Input [1,2,3], k=5:
    When k=0, it returns the result, [1,2,3].
    When k=1, it returns [3,1,2].
    When k=2, it returns [2,3,1].
    When k=3, it returns [1,2,3], which is the same result as the situation k=0.
    When k=4, it returns [3,1,2], the same result as the situation k=1.
    ...

    So we can see that the result is related to the remainder of (k/nums.length). So we can use the mod operator.


  • 0
    X

    @NewtonTree Nice explanation, Thank you!


  • 0
    A
    This post is deleted!

  • 0
    A

    @xiaoming8 This is to contain outOfBounds exception for K > nums.length


  • 0
    N

    Good solution!


Log in to reply
 

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