Java 1ms Not-so-fancy Divide-and-conquer solution O(1) space other than the recursion stack


  • 0

    This is not as smart as the Three Reverses solution or the Cyclic Replacements solution in the editorial solution article. Just throwing something a little more plain-and-easy here to inspire thoughts.

    In the example of [1,2,3,4,5,6] and k = 2:

    • First swap 1,2 and 5,6. (with a call to reverse, which is not defined in the same way as the Three Reverses solution).
    • Then recurse on the rest [3,4,1,2] with k = 2.

    The code itself should be quite straightforward.

    public class Solution {
        public void rotate(int[] nums, int k) {
            rotate(nums, 0, nums.length - 1, k);
        }
    
        public void rotate(int[] nums, int lo, int hi, int k) {
            int n = hi - lo + 1;
            if (k >= n) k = k % n;
            if (k <= 0) return;
            if (k == n - k) reverse(nums, lo, hi, k);
            else if (n - k > k) {
                reverse(nums, lo, hi, k);
                rotate(nums, lo + k, hi, k);
            } else {
                reverse(nums, lo, hi, n - k);
                rotate(nums, lo, hi - (n - k), k - (n - k));
            }
        }
    
        public void reverse(int[] nums, int lo, int hi, int k) {
            int tmp;
            int n = hi - lo + 1;
            if (k > n / 2) return;
            for (int i = 0; i < k; i++) {
                tmp = nums[hi - k + 1 + i];
                nums[hi - k + 1 + i] = nums[lo + i];
                nums[lo + i] = tmp;
            }
        }
    }
    

    I am not claiming O(1) space for this algorithm because some people feel the definition that excludes recursion stack is controversial. I am only claiming O(1) space and whatever the recursion takes here for the algorithm.

    The general idea is kinda similar to a approach in this solution.


Log in to reply
 

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