Rotate Array

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given an array of integers and an integer k.
  • We need to rotate the array to the right by k steps.
  • The rotation should be performed in-place, meaning we should modify the original array without using any additional space.

2. Analyze the problem: To solve this problem, we can use the cyclic rotation approach. We'll divide the problem into smaller components to rotate the elements of the array in cycles.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. Calculate the effective number of rotations by taking the modulus of k with the length of the array to handle cases where k is greater than the length of the array.
  2. If the effective number of rotations is 0, return the array as it is.
  3. Initialize a variable count to 0 to keep track of the number of elements that have been rotated.
  4. Initialize a variable start to 0 to store the starting index of each cycle.
  5. While count is less than the length of the array:
    • Initialize variables current and prev to start to keep track of the current and previous indices within each cycle.
    • Set temp to the value at the current index.
    • Iterate until we reach the starting index of the cycle again:
      • Calculate the next index within the cycle as (current + k) % length, where length is the length of the array.
      • Update the value at the current index with the value at the prev index.
      • Update current with the next index and prev with the current index.
      • Update count by 1.
    • Set the value at the current index to temp.
    • Move to the next cycle by updating start to (start + 1) % length.
  6. The array is now rotated by k steps.

4. Explain your approach: The approach involves rotating the elements of the array in cycles. We iterate through each cycle and track the current and previous indices within the cycle. We update the elements within the cycle by shifting each element to the next position. We continue this process until we reach the starting index of the cycle again. By repeating this process for all cycles, the array is rotated by k steps.

5. Write clean and readable code:

python
def rotate(nums, k):
    length = len(nums)
    k %= length

    if k == 0:
        return nums

    count = 0
    start = 0

    while count < length:
        current = prev = start
        temp = nums[current]

        while True:
            next_idx = (current + k) % length
            nums[next_idx], temp = temp, nums[next_idx]
            current = next_idx
            count += 1

            if current == start:
                break

        start = (start + 1) % length

    return nums

6. Test your code: Let's test the code with different test cases to ensure its correctness:

  1. Test case with an empty array:

    • Input: nums = [], k = 3
    • Expected output: []

  2. Test case with an array containing multiple elements:

    • Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
    • Expected output: [5, 6, 7, 1, 2, 3, 4]

  3. Test case with k equal to the length of the array:

    • Input: nums = [1, 2, 3, 4, 5], k = 5
    • Expected output: [1, 2, 3, 4, 5]

  4. Test case with a large value of k:

    • Input: nums = [1, 2, 3, 4, 5, 6], k = 100
    • Expected output: [3, 4, 5, 6, 1, 2]
python
# Test case 1: Empty array
nums = []
k = 3
print(rotate(nums, k))  # Output: []

# Test case 2: Array with multiple elements
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
print(rotate(nums, k))  # Output: [5, 6, 7, 1, 2, 3, 4]

# Test case 3: k equals the length of the array
nums = [1, 2, 3, 4, 5]
k = 5
print(rotate(nums, k))  # Output: [1, 2, 3, 4, 5]

# Test case 4: Large value of k
nums = [1, 2, 3, 4, 5, 6]
k = 100
print(rotate(nums, k))  # Output: [3, 4, 5, 6, 1, 2]

7. Optimize if necessary: The current solution has a time complexity of O(n), where n is the length of the array. We iterate through each element of the array once. The space complexity is O(1) as we only use a constant amount of additional space.

8. Handle error cases: The code handles the case where the input array is empty. It returns an empty array as the output in that case.

9. Discuss complexity analysis: The time complexity of the solution is O(n), where n is the length of the array. We iterate through each element of the array once. The space complexity is O(1) as we only use a constant amount of additional space. The solution has a linear time complexity and constant space complexity.

Next Post Previous Post