algoadvance

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

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]

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. What should be done if k is greater than the length of the array?
   • We can use modular arithmetic to handle cases where k is greater than nums.length. Since rotating the array nums.length times will bring it back to its original state, we can take k = k % nums.length.
2. Can we use extra space?
   • While the problem doesn’t explicitly prohibit using extra space, aiming for an in-place solution can be more optimal.

Strategy

To achieve an efficient (in-place) rotation:

1. Normalize k: Since rotating nums.length times doesn’t change the array, we can take k = k % len(nums).
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

This approach works because reversing the entire array rearranges the array such that the elements that need to be at the beginning of the array move to the end, and vice versa. Reversing the segments then puts the elements in the correct order.

Code

def rotate(nums, k):
    """
    Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    k = k % n
    
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1
            
    # Reverse the entire array
    reverse(0, n - 1)
    # Reverse the first k elements
    reverse(0, k - 1)
    # Reverse the remaining n - k elements
    reverse(k, n - 1)

# Example usage:
nums1 = [1, 2, 3, 4, 5, 6, 7]
rotate(nums1, 3)
print(nums1) # Output: [5,6,7,1,2,3,4]

nums2 = [-1, -100, 3, 99]
rotate(nums2, 2)
print(nums2) # Output: [3,99,-1,-100]

Time Complexity

• The function rotate has a time complexity of O(n), where n is the length of the input array nums. This is because reversing the array takes O(n) time, and we reverse the entire array and the two subarrays with a total of O(n) work.
• The space complexity is O(1) since the rotation is done in-place without using any extra space apart from a few variable assignments.

Try our interview co-pilot at AlgoAdvance.com

• 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?