189. Rotate Array
Rotate Array (LeetCode 189) 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.
How to solve Rotate Array
Rotate Array is a In-Place Array and Matrix Rotation problem, part of Array/Matrix Manipulation Patterns. Learn in-place rotation techniques for arrays and matrices. Rotate without using extra space.
Work towards the solution in these steps:
- The easiest solution would use additional memory and that is perfectly fine.
- 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.
- 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.
The reference solution runs in O(n) time and O(1) space.
The Rotate Array solution and editorial walks through the full approach with reference code.
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) time and O(1) 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
Problems related to Rotate Array
Other problems that use the same In-place Rotation and Array/Matrix Manipulation Patterns techniques:
- Concatenation of Array — Easy, same subpattern
- Rotate Image — Medium, same subpattern
- Transpose Matrix — Easy, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Contains Duplicate — Easy, same pattern
Rotate Array FAQ
What is the LeetCode number of Rotate Array?
Rotate Array is LeetCode problem 189, rated Medium.
What pattern is used to solve Rotate Array?
Rotate Array is a In-Place Array and Matrix Rotation problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the In-place Rotation subpattern.
What is the time complexity of Rotate Array?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Rotate Array?
Rotate Array has been reported in interviews at Microsoft, Apple, Amazon.