Java solution in one pass, O(1) space, O(n) time


  • 29
    J

    I got the idea from this C++ solution: 3 lines of C++ in one pass using swap

    But since Java doesn't have all those nice trick of swap() and pointer operations, I modified it to store the processed section at the end, and then handle the rest at the beginning of the array.

    The idea is: for a given K, I can put (n - k) elements to their final locations at the end of the array in a single pass; after that, the problem is reduced to a sub-problem of processing the remaining elements.

    For example, [1,2,3,4,5,6,7] k = 3, in the first iteration in the while loop, put n-k=4 elements to the final places at the end. Will have to start from the last element, so that the other elements will be bubbled down correctly. It will look like this after the first iteration: [7, 5, 6, 1, 2, 3, 4]

    The 2nd iteration will handle the remaining 3 elements: [7, 5, 6]; to determine the new k, we first observe that the # of out-of-order elements being put to the beginning of the array are (range % k), and in this example, only one element (7) is out of order. then to move the out-of-order elements back in order, we just need to rotate the remaining 3 elements to the right by k' = n - (range % k) = 2.

    therefore, after 2nd iteration in while loop, we will get [6, 5, 7], then n <- 2, k <- 1;

    the 3rd iteration starts with sub array [6,5], k =1, and we will get [5,6] after it, and then n <- 1.

        if (nums.length == 0) return;
        int n = nums.length;
        while ((k %= n) > 0 && n > 1) {
            int range = n - k;
            for (int i = 1; i <= range; i++) {
                int val = nums[n - i];
                nums[n - i] = nums[n - i - k];
                nums[n - i - k] = val;
            }
            n = k;
            k = n - (range % k);
        }
    

    Hope this helps.


Log in to reply
 

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