algoadvance

Leetcode 189. Rotate Array

Problem Statement

Given an array, rotate the array to the right by k steps, where k is non-negative.

Clarifying Questions

1. Bounds on k and size of the array (n):
   • What are the bounds on n (the length of the array) and k?
   • Is k always less than or equal to n?
2. Array content:
   • Can the array contain duplicate elements?
   • Are there any constraints on the type or range of elements within the array?
3. Special cases:
   • How should the function behave if the array is empty or contains only one element?
4. In-place rotation:
   • Should the rotation be done in-place, or can additional space be used?

Strategy

1. Normalize k: Since rotating by n is equivalent to not rotating at all, we can use k % n to handle cases where k is greater than n.

2. Reverse parts of the array:
   • Reverse the entire array.
   • Reverse the first k elements.
   • Reverse the remaining n - k elements.
3. Example:
   • Input: nums = [1,2,3,4,5,6,7], k = 3
   • Steps:
     1. Reverse entire array: [7,6,5,4,3,2,1]
     2. Reverse first 3 elements: [5,6,7,4,3,2,1]
     3. Reverse remaining 4 elements: [5,6,7,1,2,3,4]
   • Output: [5,6,7,1,2,3,4]

Code

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // Normalize k
        
        // Reverse entire array
        reverse(nums, 0, n - 1);
        
        // Reverse first k elements
        reverse(nums, 0, k - 1);
        
        // Reverse remaining n-k elements
        reverse(nums, k, n - 1);
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

Time Complexity

• Time Complexity: O(n) where n is the number of elements in the array. This comes from three passes over the array.
• Space Complexity: O(1) because the rotation is performed in-place without requiring additional space.

This solution efficiently rotates the array using the reversal method while maintaining an in-place operation and linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?