Array
15. Rotate Array

Rotate Array (opens in a new tab) Medium

Problem

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

Example

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3

Output: [5, 6, 7, 1, 2, 3, 4]

Summary

To solve this problem, we can use an in-place approach to rotate the array. First, we reverse the whole array, then reverse the first k elements, and finally, reverse the remaining elements. This way, we obtain the rotated array.

Solution

In TypeScript

function rotate(nums: number[], k: number): void {
  k = k % nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
}
 
function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}

In Python

def rotate(nums: List[int], k: int) -> None:
	k = k % len(nums)
	reverse(nums, 0, len(nums) - 1)
	reverse(nums, 0, k - 1)
	reverse(nums, k, len(nums) - 1)
 
def reverse(nums: List[int], start: int, end: int) -> None:
	while start < end:
		nums[start], nums[end] = nums[end], nums[start]
		start += 1
		end -= 1

Step-by-step explanation

  1. Calculate the remainder when k is divided by nums.length. This is necessary because if k is larger than the array length, the effective number of rotations will be the remainder of the division.
k = k % nums.length;
  1. Reverse the entire array by calling the reverse helper function with the start index as 0 and the end index as nums.length - 1.
reverse(nums, 0, nums.length - 1);
  1. Reverse the first k elements of the array by calling the reverse helper function with the start index as 0 and the end index as k - 1.
reverse(nums, 0, k - 1);
  1. Reverse the remaining elements in the array, which are from index k to nums.length - 1, by calling the reverse helper function with the start index as k and the end index as nums.length - 1.
reverse(nums, k, nums.length - 1);
  1. Define the reverse helper function, which takes the nums array, a start index, and an end index as its input parameters. The purpose of this function is to reverse the elements within the specified range of the input array.
function reverse(nums: number[], start: number, end: number): void {
	// ...
}
  1. Inside the reverse function, use a while loop to iterate through the elements within the specified range. The loop should continue as long as the start index is less than the end index.
while (start < end) {
	// ...
}
  1. In each iteration, use array destructuring to swap the elements at the start and end indices.
[nums[start], nums[end]] = [nums[end], nums[start]];
  1. Increment the start index and decrement the end index to move towards the middle of the specified range.
start++;
end--;

In summary, the solution provided rotates the array to the right by reversing the entire array, reversing the first k elements, and then reversing the remaining elements. The time complexity is O(n) as each element is reversed once, and the space complexity is O(1) since the operation is performed in-place.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array. Each element in the array is reversed exactly once (in three different steps), which results in linear time complexity.

Space Complexity

The space complexity of this solution is O(1) because we perform the rotation in-place, without using any additional data structures.

14. Longest Consecutive Sequence16. Contiguous Array