## 1. Description

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

Constraints:

1. $$1 \leq nums.length \leq 10^{5}$$
2. $$-2^{31} \leq nums[i] \leq 2^{31} - 1$$
3. $$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 = 
k = 10
rotate(nums, k)
print(nums == )

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

4 approaches.

1. Brute force, which will probably time out.
2. Using extra array, which is my solution.
3. Using cyclic replacements
4. Using reverse
<<imports for typing>>



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

# 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