2022-01-31-150345-189_rotate_array.org

189 Rotate Array

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⁵$
2. $-2³¹ \leq nums[i] \leq 2³¹ - 1$
3. $0 \leq k \leq 10⁵$

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]

Solution

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:

we need to modify nums instead of return ret as I was planning to do.

Algorithm

See previous section.

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

Complexity

Time complexity:

O(n)

Space complexity:

O(n)

Leetcode solution

https://leetcode.com/problems/rotate-array/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>>

Time complexity:

Space complexity:

More analysis

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

Related problems

Log time

leetcode solution

cyclic replacements