189. Rotate Array

How to solve Rotate Array (LeetCode 189): the approach in brief

The problem

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

Pattern

Rotate Array is a Array/Matrix Manipulation Patterns problem, in the In-place Rotation subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Learn in-place rotation techniques for arrays and matrices. Rotate without using extra space.

Approach outline

1. The easiest solution would use additional memory and that is perfectly fine.
2. The actual trick comes when trying to solve this problem without using any additional memory. This means you need to use the original array somehow to move the elements around. Now, we can place each element in its original location and shift all the elements around it to adjust as that would be too costly and most likely will time out on larger input arrays.
3. One line of thought is based on reversing the array (or parts of it) to obtain the desired result. Think about how reversal might potentially help us out by using an example.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Rotate Array has been reported in interviews at Microsoft, Apple, Amazon.