algoadvance

Leetcode 189. Rotate Array

Problem Statement

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

Examples:

1. Example 1:

    Input: nums = [1,2,3,4,5,6,7], k = 3
    Output: [5,6,7,1,2,3,4]
    Explanation:
    rotate 1 steps to the right: [7,1,2,3,4,5,6]
    rotate 2 steps to the right: [6,7,1,2,3,4,5]
    rotate 3 steps to the right: [5,6,7,1,2,3,4]
   

2. Example 2:

    Input: nums = [-1,-100,3,99], k = 2
    Output: [3,99,-1,-100]
    Explanation: 
    rotate 1 steps to the right: [99,-1,-100,3]
    rotate 2 steps to the right: [3,99,-1,-100]
   

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

Clarifying Questions

1. Q: Does the rotation occur in-place or can we use additional space? A: The optimal solution should aim for in-place rotation to achieve better space complexity.

2. Q: What if k is greater than nums.length? A: Since rotating an array of length n by k steps is the same as rotating it by k % n steps, k should be taken modulo n.

Strategy

To rotate the array to the right by k steps, we can use the following method which works in O(n) time complexity and O(1) space complexity:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining n - k elements.

This approach leverages the fact that reversing segments of the array can help reposition the elements correctly with minimal additional space.

Code

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;  // Handle case where k >= n
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
    
    void reverse(vector<int>::iterator begin, vector<int>::iterator end) {
        while (begin < end) {
            --end;
            iter_swap(begin++, end);
        }
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7};
    int k1 = 3;
    sol.rotate(nums1, k1);
    for(int num : nums1) {
        cout << num << " ";
    } // Expected Output: 5 6 7 1 2 3 4
    cout << endl;

    vector<int> nums2 = {-1, -100, 3, 99};
    int k2 = 2;
    sol.rotate(nums2, k2);
    for(int num : nums2) {
        cout << num << " ";
    } // Expected Output: 3 99 -1 -100
    cout << endl;

    return 0;
}

Time Complexity

• Time Complexity: O(n)
  • reverse function runs in O(k) and O(n - k) for the respective segments, which totals to O(n).
• Space Complexity: O(1)
  • In-place modifications are performed without requiring extra storage proportional to the input size.

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?