Scale Engineer

Rotate Array

Med
#0179Time: O(n * k)Space: O(1)22 companies
Patterns
MathTwo Pointers
Data structures
Array
Companies
AccentureAmerican ExpressCapgeminiEPAM Systems

Prompt

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?

Approaches

4 approaches with complexity analysis and trade-offs.

This approach simulates the rotation process step by step. For each of the k rotation steps, it moves every element in the array one position to the right. The last element is moved to the first position.

Algorithm

    1. Calculate the effective rotation count by taking k = k % nums.length.
    1. Repeat the rotation process k times.
    1. In each of the k iterations, perform a single right rotation:
    • a. Store the last element of the array in a temporary variable, last = nums[n-1].
    • b. Shift all elements from index n-2 down to 0 one position to the right. This can be done by iterating from j = n-1 down to 1 and setting nums[j] = nums[j-1].
    • c. Place the stored last element at the beginning of the array: nums[0] = last.

Walkthrough

The most straightforward way to solve the problem is to literally rotate the array k times. A single right rotation involves taking the last element and moving it to the front, while shifting every other element one position to the right.

We can implement this by running a loop k times. Inside this loop, we perform the single rotation. To avoid unnecessary rotations when k is larger than the array length n, we first take k = k % n.

class Solution {    public void rotate(int[] nums, int k) {        int n = nums.length;        // To handle cases where k > n        k %= n;                for (int i = 0; i < k; i++) {            int lastElement = nums[n - 1];            // Shift all elements one position to the right            for (int j = n - 1; j > 0; j--) {                nums[j] = nums[j - 1];            }            // Place the last element at the front            nums[0] = lastElement;        }    }}

Complexity

Time

O(n * k)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • It's an in-place solution, using constant extra space.

Cons

  • Extremely inefficient for large arrays or large values of k.

  • Will likely result in a 'Time Limit Exceeded' (TLE) error on most coding platforms for larger constraints.

Solutions

public class Solution {    private int[] nums;    public void Rotate(int[] nums, int k) {        this.nums = nums;        int n = nums.Length;        k %= n;        reverse(0, n - 1);        reverse(0, k - 1);        reverse(k, n - 1);    }    private void reverse(int i, int j) {        for (; i < j; ++i, --j) {            int t = nums[i];            nums[i] = nums[j];            nums[j] = t;        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem