189. Rotate Array

#two-pointers #math

Problem

Rotate Array - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public void rotate(int[] nums, int k) {
        // n -> nums.length, number of elements in nums
        // Time Complexity: O(n)
        // For reversing, and reversing the parts based on pivot = 2 * O(n) = O(n)

        // Space Complexity: O(1)

        // Reverse the full original array
        reverse(nums, 0, nums.length-1);

        k = k % nums.length; // Using mod to handle arraysout of bounds exception
        
        // Find pivot
        int pivot = k - 1;

        // Reverse the first part
        reverse(nums, 0, pivot);

        // Reverse the second part
        reverse(nums, pivot+1, nums.length-1);
    }

    private void reverse(int[] nums, int start, int end) {
        while(start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }

    private void swap(int[] nums, int idx1, int idx2) {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}