Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Rotate Array

Array, Two Pointers

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]

Solutions

The problem is asking to rotate an array to the right by k steps. This means that each element in the array should be moved k positions to the right, and the elements that go beyond the end of the array should be moved to the start of the array.

Approach – Brute Force Technique

In the brute force approach, we rotate the array k times. In each rotation, we move each element to its next position and move the last element to the start of the array.

Steps

  1. Define the function: The function Rotate is defined with two parameters, nums (an array of integers) and k (the number of steps to rotate).

  2. Outer loop: The outer loop runs k times. Each iteration of this loop corresponds to a single step of rotation.

  3. Store the last element: Before shifting the elements, the last element of the array is stored in the variable temp. This is because it will be overwritten during the shifting process and we need to place it at the start of the array.

  4. Shift elements to the right: The inner loop runs from the end of the array to the start, shifting each element one position to the right. This is done by setting nums[j] to nums[j - 1].

  5. Place the last element at the start: After all elements have been shifted, there is an empty spot at the start of the array (i.e., nums[0]). The last element that we stored in temp is placed here.

  6. Repeat: The process is repeated k times to achieve the required rotation.

public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        for (int i = 1; i <= k; i++)
        {
            int temp = nums[nums.Length - 1];
            for (int j = nums.Length - 1; j > 0; j--)
            {
                nums[j] = nums[j - 1];
            }
            if (nums.Length > 0)
            {
                nums[0] = temp;
            }
        }
    }
}

Complexity

  • Time Complexity: O(n*k)

  • Auxiliary Space: O(1)

Approach – Two Pointers Technique

In the optimized approach, we use the reverse operation to achieve the rotation. We first reverse the entire array, then reverse the first k elements, and finally reverse the remaining n - k elements.

Steps

  1. Calculate the effective number of rotations: The number of rotations k is taken modulo the length of the array n. This is because rotating the array n times doesn't change the array, so we only need to consider the remainder of k divided by n.

  2. Reverse the entire array: The Reverse function is called with parameters 0 and n - 1, which reverses the entire array.

  3. Reverse the first part of the array: The Reverse function is called again with parameters 0 and k - 1, which reverses the first k elements of the array.

  4. Reverse the second part of the array: The Reverse function is called one more time with parameters k and n - 1, which reverses the remaining n - k elements of the array.

The Reverse function is a helper function that reverses the elements in the nums array between the start and end indices. It does this by swapping the elements at the start and end indices, and then incrementing start and decrementing end until start is no longer less than end.

public class Solution
{
    public void Rotate(int[] nums, int k)
    {
        int n = nums.Length;
        k = k % n;
        Reverse(nums, 0, n - 1);
        Reverse(nums, 0, k - 1);
        Reverse(nums, k, n - 1);
    }

    public void Reverse(int[] nums, int start, int end)
    {
        while (start < end)
        {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

}

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(1)

PreviousMove ZeroesNextPlus One

Last updated 1 year ago