Rotate Array Counterclockwise

Problem

Given an array, rotate it counterclockwise by dd steps, where dd is a positive integer. Array indices wrap around. Modify the array in place.

Examples

  • [1, 2, 3, 4, 5], 2 Output [3, 4, 5, 1, 2]

  • [2, 4, 6, 8, 10, 12, 14, 16, 18, 20], 3 Output [8, 10, 12, 14, 16, 18, 20, 2, 4, 6]

  • [7, 3, 9, 1], 9 Output [3, 9, 1, 7]

Constraints

  • 1≤n≤105 (array length)1 \le n \le 10^5 \ (\text{array length})

  • 0≤v≤105 (element value)0 \le v \le 10^5 \ (\text{element value})

  • 1≤d≤1051 \le d \le 10^5

Expected Complexities

  • Time Complexity: O(n)\mathcal{O}(n)

  • Auxiliary Space: O(1)\mathcal{O}(1)

Solution

Python
from typing import TypeVar

T = TypeVar("T")


def rotate_array_counterclockwise_reversal(arr: list[T], d: int) -> list[T]:
    n: int = len(arr)
    d %= n

    def reverse(start_index: int, end_index: int) -> None:
        while start_index < end_index:
            arr[start_index], arr[end_index] = arr[end_index], arr[start_index]
            start_index += 1
            end_index -= 1

    reverse(0, d - 1)
    reverse(d, n - 1)
    reverse(0, n - 1)

    return arr


import math


def rotate_array_counterclockwise_juggling(arr: list[T], d: int) -> list[T]:
    n: int = len(arr)
    d %= n
    cycles: int = math.gcd(n, d)

    for i in range(cycles):
        start = arr[i]
        current_index = i

        while True:
            next_index = (current_index + d) % n

            if next_index == i:
                break

            arr[current_index] = arr[next_index]
            current_index = next_index

        arr[current_index] = start

    return arr


print(rotate_array_counterclockwise_reversal([1, 2, 3, 4, 5], 2))
print(rotate_array_counterclockwise_reversal([2, 4, 6, 8, 10, 12, 14, 16, 18, 20], 3))
print(rotate_array_counterclockwise_juggling([7, 3, 9, 1], 9))