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

Listing 1: 189 Rotate Array my solution

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

Listing 2: 189 Rotate Array my solution-results

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

Listing 3: 189 Rotate Array leetcode solution

<<imports for typing>>

Listing 4: 189 Rotate Array leetcode solution-results

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