We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rotate Array

Number: 189

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Apple, Bloomberg, Meta, Microsoft, American Express, Accenture, tcs, Samsung, Infosys, EPAM Systems, Adobe, Uber, Zoho, Walmart Labs, Goldman Sachs, TikTok, Oracle, Yahoo, Siemens, Wipro

Problem Description

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. In other words, move the last k elements to the front of the array while preserving their order.

Key Insights

  • The rotation amount k might be greater than the length of the array, so use k % n (where n is the array length) to compute the effective rotation.
  • A smart in-place solution involves reversing sections of the array:
    • Reverse the entire array.
    • Reverse the first k elements.
    • Reverse the remaining n-k elements.
  • Alternative approaches include using extra space or performing k single-step rotations (which is less optimal).

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(1) if done in-place.

Solution

We solve the problem using the "reverse" technique to perform the rotation in-place. First, we adjust k by taking k modulo the length of the array to handle cases where k exceeds the array length. Then, we reverse the entire array. Next, we reverse the first k elements to restore their correct order. Finally, we reverse the remaining n-k elements. This sequence yields the array rotated to the right by k positions while strictly using O(1) extra space.

Code Solutions

# Python solution using the reverse method

def rotate(nums, k):
    # Calculate the effective rotations needed
    n = len(nums)  
    k = k % n  # in case k is greater than the length of the array
    
    # Helper function to reverse a portion of the list in place
    def reverse(left, right):
        while left < right:
            # Swap the elements at indices left and right
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    # Reverse the entire array
    reverse(0, n - 1)
    # Reverse the first k elements to restore their order
    reverse(0, k - 1)
    # Reverse the remaining n - k elements
    reverse(k, n - 1)

# Example usage:
# nums = [1,2,3,4,5,6,7]
# rotate(nums, 3)
# print(nums)  # Output: [5,6,7,1,2,3,4]
← Back to All Questions