<p>Given an integer array <code>nums</code>, rotate the array to the right by <code>k</code> steps, where <code>k</code> is non-negative.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7], k = 3
<strong>Output:</strong> [5,6,7,1,2,3,4]
<strong>Explanation:</strong>
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]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-100,3,99], k = 2
<strong>Output:</strong> [3,99,-1,-100]
<strong>Explanation:</strong> 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>0 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<ul>
	<li>Try to come up with as many solutions as you can. There are at least <strong>three</strong> different ways to solve this problem.</li>
	<li>Could you do it in-place with <code>O(1)</code> extra space?</li>
</ul>

"""
Method 1: Use two rounds of reverses (the order of round 1 and round 2 can be swapped):
          Round 1: reverse the overall nums, yielding nums_r;
          Round 2: reverse nums_r[0, n - k] and nums_r[n - k, n] respectively.
Time: O(n), where n = len(nums)
Space: O(1)


Method 2: Employ Python functions: 
          element = lst.pop(-1), and, lst.insert(0, element)
Time: O(k), where n = len(nums)
Space: O(1)


Method 3: Employ Python functions: 
          element = lst.pop(0), and, lst.append(element)
Time: O(n - k), where n = len(nums)
Space: O(1)


Method 4 ( *invalid* ): list slicing
Time: O(1)
Space: O(1)

Note: 
1. lst.insert(pos, element), where pos specifies the position index (starting from 0) at which to insert element
2. int(9.9) = 9
"""

class Solution:
    def rotate1(self, nums: List[int], k: int) -> None:
        """
        Method 1. Do not return anything, modify nums in-place instead.
        Round 1 reverse and round 2 reverse can be swapped.
        """
        n = len(nums)
        k = k % n

        # round 1
        self.reverse(nums, 0, n)  # reverse nums[0: n]

        # round 2
        self.reverse(nums, 0, k)  # reverse nums[0: k]
        self.reverse(nums, k, n)  # reverse nums[k: n]
    
    def reverse(self, lst: List[int], s: int, e: int) -> None:
        """
        Given lst[s: e] where the last element is excluded, this method in-place reverses the involving elements.
        """
        for i in range(int((e - s) / 2)):
            tmp = lst[s + i]
            lst[s + i] = lst[e - 1 - i]
            lst[e - 1 - i] = tmp
    
    def rotate2(self, nums: List[int], k: int) -> None:
        """
        Method 2. Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n

        for i in range(k):
            element = nums.pop(-1)
            nums.insert(0, element)

    def rotate(self, nums: List[int], k: int) -> None:
        """
        Method 3. Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n  # k = 0, 1, ..., n - 1 ==> (n - k) = n, n - 1, ..., 1
        m = (n - k) % n

        for i in range(m):
            element = nums.pop(0)
            nums.append(element)
    
    def rotate4(self, nums: List[int], k: int) -> None:
        """
        Method 4 ( *invalid* ). Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums = nums[n - k: n] + nums[0: n - k]
        
26300