leetcode
  • LeetCode Problems
  • Array
    • Array Partition I
    • Toeplitz Matrix
    • Find All Numbers Disappeared in an Array
    • Max Area of Island
    • Move Zeros
    • Two Sum II - Input array is sorted
    • Degree of an Array
    • Image Smoother
    • Positions of Large Groups
    • Missing Number
    • Maximum Product of Three Numbers
    • Min Cost Climbing Stairs
    • Longest Continuous Increasing Subsequence
    • Remove Element
    • Pascal's Triangle
    • Maximum Subarray
    • Largest Number At Least Twice of Others
    • Search Insert Position
    • Plus One
    • Find Pivot Index
    • Pascal's Triangle II
    • Two Sum
    • Maximize Distance to Closest Person
    • Maximum Average Subarray I
    • Remove Duplicates from Sorted Array
    • Magic Squares In Grid
    • Contains Duplicate II
    • Merge Sorted Array
    • Can Place Flowers
    • Shortest Unsorted Continuous Subarray
    • K-diff Pairs in an Array
    • Third Maximum Number
    • Rotate Array
    • Non-decreasing Array
    • Find All Duplicates in an Array
    • Teemo Attacking
    • Beautiful Arrangement II
    • Product of Array Except Self
    • Max Chunks To Make Sorted
    • Subsets
    • Best Time to Buy and Sell Stock with Transaction Fee
    • Combination Sum III
    • Find the Duplicate Number
    • Unique Paths
    • Rotate Image
    • My Calendar I
    • Spiral Matrix II
    • Combination Sum
    • Task Scheduler
    • Valid Triangle Number
    • Minimum Path Sum
    • Number of Subarrays with Bounded Maximum
    • Insert Delete GetRandom O(1)
    • Find Minimum in Rotated Sorted Array
    • Sort Colors
    • Find Peak Element
    • Subarray Sum Equals K
    • Subsets II
    • Maximum Swap
    • Remove Duplicates from Sorted Array II
    • Maximum Length of Repeated Subarray
    • Image Overlap
    • Length of Longest Fibonacci Subsequence
  • Contest
    • Binary Gap
    • Advantage Shuffle
    • Minimum Number of Refueling Stops
    • Reordered Power of 2
  • Dynamic Programming
    • Climbing Stairs
    • Range Sum Query - Immutable
    • Counting Bits
    • Arithmetic Slices
    • Palindromic Substrings
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Pair Chain
    • Integer Break
    • Shopping Offers
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • Predict the Winner
    • Stone Game
    • Is Subsequence
    • Delete and Earn
    • Longest Palindromic Subsequence
    • Target Sum
    • Unique Binary Search Trees
    • Minimum Path Sum
    • Combination Sum IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Largest Sum of Averages
    • Largest Plus Sign
    • Untitled
  • Invert Binary Tree
  • Intersection of Two Arrays
  • Surface Area of 3D Shapes
  • K Closest Points to Origin
  • Rotting Oranges
  • Smallest Integer Divisible by K
  • Duplicate Zeros
  • DI String Match
  • Implement Queue using Stacks
  • Increasing Order Search Tree
  • Reveal Cards In Increasing Order
  • Reshape the Matrix
  • Partition List
  • Total Hamming Distance
  • Validate Binary Search Tree
  • Decode Ways
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Search Tree from Preorder Traversal
  • Design Circular Queue
  • Network Delay Time
  • Most Frequent Subtree Sum
  • Asteroid Collision
  • Binary Tree Inorder Traversal
  • Check If Word Is Valid After Substitutions
  • Construct Binary Tree from Preorder and Postorder Traversal
  • K-Concatenation Maximum Sum
Powered by GitBook
On this page
  • Description
  • Solutions
  • My solution (also optimal)
  • Easier to understand solution
  1. Array

Rotate Array

Description

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

Example 1:

Input: [1,2,3,4,5,6,7] and 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: [-1,-100,3,99] and 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]

Note:

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

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

Solutions

My solution (also optimal)

Idea: directly put numbers in their new positions.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0 || k % n == 0) return;
        k %= n;
        int count = 0; // number of elements in correct position
        int start = 0;
        while(count < n){
            int i = start;
            int prev = nums[i]; // value of number in previous index
            do{
                i = (i + k) % n; // destination index
                swap(prev, nums[i]);
                ++count;
            }while(i != start);
            ++start;
        }
    }
};

Easier to understand solution

Idea: the objective is to move the first n - k numbers to the last n - k positions, and move the last k numbers to the first k positions. If we reverse nums, then the original first n - k numbers and the last k numbers are in correct ranges. Then we reverse the two ranges to make all numbers in correct positions.

E.g.,

Original array: [1, 2, 3, 4, 5, 6] , k = 4

Objective: [3, 4, 5, 6, 1, 2]

After first reversing: [6, 5, 4, 3, 2, 1].[6, 5, 4, 3] and [2, 1] are in correct ranges but in reversed order.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0 || k % n == 0) return;
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};
PreviousThird Maximum NumberNextNon-decreasing Array

Last updated 6 years ago