Rotate Array

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

What is Being Asked?

(One sentence on the actual task.)

Key Observations

(Patterns, constraints, or hints in the problem statement.)

Approach Taken

(Step-by-step logic or pseudocode before coding.)

Why This Works

(Explain the core reason the solution is correct.)

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Two Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Going through each item once
• Space: $O(1)$ → Reason: Not storing an extra array

Code (Brute Force)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        result = [0] * len(nums)
        for i, num in enumerate(nums):
            result[(i + k) % len(nums)] = num

        for i in range(len(nums)):
            nums[i] = result[i]   

Code (Optimized)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
		k = k % len(nums)
        self.reverse(nums, 0, len(nums) - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, len(nums) - 1)

    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

Common Mistakes / Things I Got Stuck On

• k - the number of times to shift elements can be greater than number of items in the array
  • example k = 7 and `nums = [1,2]
  • k = k % len(nums) ensures k is good