LeetCode - Algorithms - 189. Rotate Array

Problem

189. Rotate Array

Follow up

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

Java

Using Reverse

© Approach 4: Using Reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[] nums, int k) {
        final int N = nums.length;
        if (k >= N)
            k = k % N;
        reverse(nums, 0, N - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, N - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        int temp;
        for (int i = 0; i < (end - start + 1) / 2; i++) {
            temp = nums[start + i];
            nums[start + i] = nums[end - i];
            nums[end - i] = temp;
        }
    }
}

Submission Detail

  • 35 / 35 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Array.
  • Memory Usage: 39.4 MB, less than 97.56% of Java online submissions for Rotate Array.

brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[] nums, int k) {
        int temp;
        final int N = nums.length;
        if (k >= N)
            k = k % N;
        for (; k > 0; k--) {
            temp = nums[N - 1];
            for (int i = N - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = temp;
        }
    }
}

Submission Detail

  • 35 / 35 test cases passed.
  • Runtime: 183 ms, faster than 22.49% of Java online submissions for Rotate Array.
  • Memory Usage: 39.4 MB, less than 96.24% of Java online submissions for Rotate Array.