Rotate Array

Rotate Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the In-place Rotation subpattern.

Problem statement

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

Example 1:

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]

Example 2:

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]

Constraints:

- 1 <= nums.length <= 105

- -231 <= nums[i] <= 231 - 1

- 0 <= k <= 105

Follow up:

- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.

- Could you do it in-place with O(1) extra space?

Topics and companies

Topics: Array, Math, Two Pointers.

Reported in interviews at Microsoft, Apple, Amazon.

How to practise Rotate Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) — Each reverse operation is O(n), and we do three reverses, so total is O(n). time and O(1) — All operations are done in-place, using only a constant amount of extra space. space.

Open Rotate Array in the code editor, or read the Rotate Array editorial for a worked solution with its approach and complexity analysis.

Where Rotate Array sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• In-place Rotation subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Rotate Array

Other problems that use the same In-place Rotation and Array/Matrix Manipulation Patterns techniques:

• Rotate Image — Medium, same subpattern
• Transpose Matrix — Easy, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Diagonal Traverse — Medium, same pattern
• Find All Duplicates in an Array — Medium, same pattern