Skip to content

Volume ITechnology

4.0.17 — Reverse and Rotate an Array ​

Classic · Easy to Medium · LeetCode 189 (Rotate Array)

The problem ​

  1. Reverse an array in place. [1, 2, 3, 4, 5] becomes [5, 4, 3, 2, 1].
  2. Rotate an array to the right by k steps. With k = 2, [1, 2, 3, 4, 5, 6, 7] becomes [6, 7, 1, 2, 3, 4, 5]. The last two elements wrap around to the front.
  3. Do the rotation in place, using O(1) extra memory.

1. Reverse in place ​

Two indexes walk inward, swapping as they go. This is Move 4 from 4.0.0.

python
def reverse(nums: list[int], i: int = 0, j: int | None = None) -> None:
    if j is None:
        j = len(nums) - 1
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1

a = [1, 2, 3, 4, 5]
reverse(a)
print(a)   # → [5, 4, 3, 2, 1]

The function takes an optional range i to j, so it can reverse just part of a list. The rotation below needs exactly that.

In Python, nums.reverse() does this in place, and nums[::-1] makes a reversed copy. Know the difference. The copy uses O(n) extra memory.

2. Rotate right by k ​

First, shrink k ​

Rotating a list of length 7 by 7 steps brings every element back to where it started. So rotating by 9 is the same as rotating by 2. Always start with k = k % n. This also stops a crash or wasted work when k is much bigger than n.

Way 1 — Slicing, with extra memory ​

The last k elements move to the front. Everything else moves after them.

python
def rotate_copy(nums: list[int], k: int) -> list[int]:
    n = len(nums)
    if n == 0:
        return nums
    k %= n
    return nums[-k:] + nums[:-k] if k else nums[:]   # (1)

print(rotate_copy([1, 2, 3, 4, 5, 6, 7], 2))   # → [6, 7, 1, 2, 3, 4, 5]
print(rotate_copy([1, 2, 3], 4))               # → [3, 1, 2]

(1) nums[-k:] is the last k elements. nums[:-k] is everything before them. The if k guard is needed because of an odd Python rule. When k is 0, nums[-0:] is nums[0:], the whole list, since -0 equals 0. Without the guard, rotating by 0 would double the list.

This is O(n) time but builds a new list, O(n) memory.

Way 2 — One step at a time ​

Move the last element to the front, k times. Each move shifts every other element right by one, which is O(n). Doing that k times is O(n \times k). For a million elements rotated by half a million, that is 5 \times 10^{11} steps. Too slow. Say it out loud as the brute force, and then move on.

Way 3 — Reverse three times, in place ​

This is the method most interviewers expect. It is the same idea as reversing the words of a sentence in 4.0.11.

Split the list into two parts: A, the first n - k elements, and B, the last k. Rotating right by k turns A B into B A.

  1. Reverse the whole list. A B becomes B^R A^R, where ^R means "reversed". The two blocks have swapped places, but each one is now backwards.
  2. Reverse the first k elements. That turns B^R back into B.
  3. Reverse the rest. That turns A^R back into A.
start                    1 2 3 4 5 | 6 7      A = 1..5, B = 6 7
reverse all              7 6 | 5 4 3 2 1      blocks swapped, each backwards
reverse first k = 2      6 7 | 5 4 3 2 1      B fixed
reverse the rest         6 7 | 1 2 3 4 5      A fixed. Done.
python
def rotate(nums: list[int], k: int) -> None:
    n = len(nums)
    if n == 0:
        return
    k %= n                      # (1)
    reverse(nums, 0, n - 1)     # (2)
    reverse(nums, 0, k - 1)     # (3)
    reverse(nums, k, n - 1)     # (4)

a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 2)
print(a)   # → [6, 7, 1, 2, 3, 4, 5]

b = [1, 2, 3]
rotate(b, 0)
print(b)   # → [1, 2, 3]

(1) Shrink k first. Without this, k = 9 on 7 elements would try to reverse past the end.

(2) Reverse everything. The blocks swap places.

(3) Reverse the first k elements back into their original order. When k is 0, this range is empty (0 to -1), and reverse does nothing, which is correct.

(4) Reverse the remaining elements back into order.

Why does reversing the whole thing swap the blocks? Reversing reads the list from the end. The end of the list is block B, so B comes out first, read backwards. Then comes A, read backwards. The order of the blocks flips, and so does the order inside each block. The two smaller reversals undo the inner flips and leave the block swap in place.

How much work? Step (2) does n/2 swaps. Steps (3) and (4) together do k/2 + (n-k)/2 = n/2 swaps. Total: n swaps. So it is O(n) time and O(1) extra memory.

Rotating left instead ​

Rotating left by k is the same as rotating right by n - k. Or do the reversals in the other order: reverse the first k, reverse the rest, then reverse the whole list.

python
def rotate_left(nums: list[int], k: int) -> None:
    n = len(nums)
    if n == 0:
        return
    k %= n
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)
    reverse(nums, 0, n - 1)

a = [1, 2, 3, 4, 5]
rotate_left(a, 2)
print(a)   # → [3, 4, 5, 1, 2]

Another in-place way you may hear about ​

The juggling method moves each element straight to its final position. It follows a chain. The element at 0 goes to position k. The element that was at k goes to 2k. This continues, wrapping around at the end. A chain can come back to its start before it has visited every position. The number of separate chains turns out to be \gcd(n, k), the HCF from 4.0.6. It is also O(n) and O(1). It is harder to get right, so name it and use the reversals.

Complexity ​

MethodTimeExtra memory
SlicingO(n)O(n)
One step at a timeO(n \times k)O(1)
Three reversalsO(n)O(1)

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What if k is bigger than the length of the list?" Use k = k % n first. Rotating by the full length changes nothing, so only the remainder matters.

"Rotate in place with no extra list." Reverse the whole list. Then reverse the first k elements. Then reverse the rest. The first reverse swaps the two blocks. The next two reverses fix the order inside each block.

"What does nums[-0:] give?" The whole list, because -0 is the same as 0. That is why the slicing version needs a special case for k = 0.

"Rotate left instead of right." Rotating left by k is the same as rotating right by n - k. Or do the three reverses in the opposite order.

One thing to volunteer: "Reversing the parts and then the whole is a general way to swap two blocks of different sizes in place."

Next: 4.0.18 Remove Duplicates and Move Zeros. The write-pointer pattern, which edits an array in place in one pass.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet