# 189 Rotate Array

## 1. Description

Given an array, rotate the array to the right by `k`

steps, where `k`

is non-negative.

Constraints:

- \(1 \leq nums.length \leq 10^{5}\)
- \(-2^{31} \leq nums[i] \leq 2^{31} - 1\)
- \(0 \leq k \leq 10^{5}\)

### 1.1. Examples:

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] 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]

## 2. Solution

### 2.1. Understanding the problem

I think this question definitely needs to use `mod`

.

Suppose the result set is `ret`

.
One trivial case is where `len(nums) == 1`

, then `ret == nums`

.

Another observation is if `len(nums) == k`

, then `ret == nums`

Therefore we are not concerned about rotating the list `k`

times,
we are concerned about rotating the list `r = k % len(nums)`

times.

If we make more effort we can see that `ret = nums[r:] + nums[:r]`

.

Because there's this comment from the existing code:

:rtype: None Do not return anything, modify nums in-place instead.

we need to modify `nums`

instead of return `ret`

as I was planning to do.

### 2.2. Algorithm

See previous section.

### 2.3. Code

from typing import List def rotate(nums: List[int], k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ r = k % len(nums) # time limit exceeded # for i in range(r): # nums.insert(0, nums.pop()) # this does not work because it didn't modify the original object bound to nums # nums = nums[-r::1] + nums[:-r] nums[:] = nums[-r::1] + nums[:-r] # tests nums = [0] k = 10 rotate(nums, k) print(nums == [0]) nums = [0, 1, 2] k = 3 rotate(nums, k) print(nums == [0, 1, 2]) nums = [-1,-100,3,99] k = 2 rotate(nums, k) print(nums == [3, 99, -1, -100]) nums = [1, 2, 3, 4, 5, 6, 7] k = 3 rotate(nums, k) print(nums == [5, 6, 7, 1, 2, 3, 4])

True True True True

#### 2.3.1. Complexity

##### 2.3.1.1. Time complexity:

`O(n)`

##### 2.3.1.2. Space complexity:

`O(n)`

### 2.4. Leetcode solution

https://leetcode.com/problems/rotate-array/solution/

4 approaches.

- Brute force, which will probably time out.
- Using extra array, which is my solution.
- Using cyclic replacements
- Using reverse

```
<<imports for typing>>
```

#### 2.4.1. Time complexity:

#### 2.4.2. Space complexity:

## 3. More analysis

### 3.1. General thoughts

I was able to come up with the solution idea but I wasn't aware of how to modify `nums`

**in-place**.
I initially used `nums = nums[-r::1] + nums[:-r]`

which I knew was a bit off and wasn't passing the tests, but I didn't know how to fix it until I looked up other people's solutions.

Also something of interest here.

from typing import List def rotate(nums: List[int], k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ r = k % len(nums) nums = nums[-r::1] + nums[:-r] print("Shadowed numns: ", nums) # tests nums = [-1,-100,3,99] k = 2 rotate(nums, k) print("Original nums: ", nums) print(str(nums) == str([3, 99, -1, -100]))

Shadowed numns: [3, 99, -1, -100] Original nums: [-1, -100, 3, 99] False