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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rotate Array

Difficulty: Medium

Problem Description

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

Key Insights

  • The rotation can be optimized by using the modulus operation to handle cases where k is greater than the length of the array.
  • The problem can be solved using several methods, including reversing parts of the array or using additional space for a new array.
  • In-place solutions can achieve O(1) extra space by manipulating the array with careful indexing.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) for the in-place solution; O(n) if using an additional array.

Solution

To solve this problem, we can use the following approaches:

  1. Reverse Method:

    • Reverse the entire array.
    • Reverse the first k elements.
    • Reverse the remaining n-k elements. This method takes advantage of the properties of array reversal to achieve the desired rotation with O(1) extra space.

  2. Extra Array Method:

    • Create a new array of the same length as the original.
    • Copy elements into their new positions based on the calculated indices. This method uses O(n) extra space but is straightforward to implement.

  3. Brute Force Method:

    • Move each element one step to the right k times. This method is less efficient with a time complexity of O(n*k) and is not recommended for larger inputs.

Code Solutions

def rotate(nums, k):
    n = len(nums)
    k = k % n  # Handle cases where k is larger than n
    nums.reverse()  # Step 1: Reverse the entire array
    nums[:k] = reversed(nums[:k])  # Step 2: Reverse the first k elements
    nums[k:] = reversed(nums[k:])  # Step 3: Reverse the remaining elements
← Back to All Questions