logoNEURAL COOK
SearchAll PostsTagsNotesAuthor
logoNEURAL COOK

A posts created with Next.js and Tailwind.css

Explore

  • All posts
  • Notes
  • Snippets
  • Tags
  • RSS feed

Connect

instagramtwitterfacebookyoutubelinkedinmailgithub

© 2026 VIKI. All rights reserved.

Built with
Contents
Table Of Contents
Check if Array is SortedLargest Element in an ArrayArray Rotation (Left and Right)Left Rotate Array by OneLinear SearchMax Consecutive OnesSecond Largest Element in an ArraySingle Number
Code Scratch/take u forward/arrays/fundamentals

Array Rotation (Left and Right)

4 min read
On this pageQuestion
QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up

# Question

Given an integer array numsnumsnums and a non-negative integer kkk, rotate the array:

  1. To the Right: kkk elements from the back move to the front.
  2. To the Left: kkk elements from the front move to the back.

The operation must be performed in-place with O(1)O(1)O(1) extra space.

# Solution

# Pattern

The Triple Reversal Algorithm A mathematical property where an array can be divided into two parts AAA and BBB. By reversing AAA, then BBB, then the entire array Reverse(A)Reverse(B)Reverse(A)Reverse(B)Reverse(A)Reverse(B), we achieve a cyclic shift.

# How to Identify

  • Requirement for in-place modification of a sequence.
  • Cyclic shifts or rotations where elements "wrap around."
  • Constraints demanding O(1)O(1)O(1) space and O(n)O(n)O(n) time.

# Description

Step-by-step explanation:

  • Step 1: Normalize kkk. Since rotating nnn times is a null operation, set k=k(modn)k = k \pmod nk=k(modn).
  • Step 2: Partition the Array. - For Right Rotation: Divide at index n−kn - kn−k.
    • For Left Rotation: Divide at index kkk.
  • Step 3: Reverse the Parts.
    • Reverse the first part.
    • Reverse the second part.
  • Step 4: Global Reverse.
    • Reverse the entire array from index 000 to n−1n - 1n−1.

# The Intuition

Think of the array as two separate blocks: XXX and YYY. If you want to move XXX to the end (Left Rotation), the goal is to transform [X,Y][X, Y][X,Y] into [Y,X][Y, X][Y,X].

  1. Reverse X→[XR,Y]X \rightarrow [X^R, Y]X→[XR,Y]
  2. Reverse Y→[XR,YR]Y \rightarrow [X^R, Y^R]Y→[XR,YR]
  3. Reverse the whole thing →[(XR,YR)R]=[Y,X]\rightarrow [(X^R, Y^R)^R] = [Y, X]→[(XR,YR)R]=[Y,X]

# Complexity

LabelWorstAverage
Time ComplexityO(n)O(n)O(n)O(n)O(n)O(n)
Space ComplexityO(1)O(1)O(1)O(1)O(1)O(1)

# Time Complexity

O(n)O(n)O(n). Each element is swapped a maximum of two times across the three reversal steps (2n2n2n operations), which simplifies to linear time.

# Space Complexity

O(1)O(1)O(1). Only a single temporary variable is used for swapping, regardless of input size.

# Code

class Solution {
    /**
     * Rotates array to the right by k steps.
     * Logic: Reverse (0 to n-k-1), then (n-k to n-1), then (0 to n-1)
     */
    public void rotateRight(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int n = nums.length;
        k %= n;
        if (k == 0) return;
 
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
 
    /**
     * Rotates array to the left by k steps.
     * Logic: Reverse (0 to k-1), then (k to n-1), then (0 to n-1)
     */
    public void rotateLeft(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int n = nums.length;
        k %= n;
        if (k == 0) return;
 
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
        reverse(nums, 0, n - 1);
    }
 
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

# Caveats

  • k=0k=0k=0 or k=nk=nk=n: Always perform the modulus and check if kkk is 0 to avoid unnecessary processing.
  • Empty Arrays: Defensive coding for null or length == 0 is essential for production-grade code.
  • Integer Overflow: If kkk is provided as a very large long, casting and modulus must be done carefully.

# Concepts to Think About

  • Cyclic Buffers: In many real-world applications (like OS kernels), instead of shifting data, we move the "start" pointer in a virtual circular array.

  • Cache Locality: The reversal algorithm is faster than the "Juggling" algorithm because it accesses memory in a linear, predictable sequence, which modern CPUs optimize via prefetching.

  • GCD Juggling: Understanding how the Greatest Common Divisor determines the number of cycles in a permutation.

  • Left vs. Right Rotation: To perform a Right Rotation by k, the logic is slightly different. You would reverse the last k elements, then the first n−k, then the whole. Can you see how the "split point" moves?

  • The Juggling Algorithm: There is another O(1) space approach using the Greatest Common Divisor (GCD) of n and k. It moves elements in "cycles." While harder to code, it performs fewer total assignments than the Reversal method.

  • Block Swap Algorithm: This is another O(n) time approach that is very efficient for large k. It works by swapping blocks of size k recursively.

  • Why Modulo? If n=5 and k=7, rotating 7 times is the same as rotating 2 times (7(mod5)). Always include this to show you understand cyclic properties.

# Logical Follow-up

Question: Can you solve this with O(1)O(1)O(1) space without using the reversal trick? Solution: Use the Juggling Algorithm. Calculate g=GCD(n,k)g = GCD(n, k)g=GCD(n,k). There are ggg cycles to process. For each cycle, move elements to their target positions (i+k)(modn)(i + k) \pmod n(i+k)(modn) one by one.

Question: How would you rotate a linked list by kkk? Solution: Find the (n−k)th(n-k)^{th}(n−k)th node, make the list circular by connecting the tail to the head, set the new head to the (n−k+1)th(n-k+1)^{th}(n−k+1)th node, and break the circular connection.

←PreviousLargest Element in an ArrayNext→Left Rotate Array by One

On this page

QuestionSolutionPatternHow to IdentifyDescriptionThe IntuitionComplexityCodeCaveatsConcepts to Think AboutLogical Follow-up