Abstract / Summary

Given an array and a number of steps rotate the array elements to the right by that many steps in place.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 45% (9+ million submissions).

Typical patterns to solve this problem:

• Array
• Math
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single public method rotate. The method receives a mutable reference to a std::vector<int> and an integer k. Its purpose is to rotate the elements of the vector to the right by k positions, wrapping elements that fall off the end back to the front. The algorithm leverages the C++ Standard Library to achieve the rotation efficiently while handling a variety of input conditions.

Key Steps

The rotation logic is composed of three distinct operations, each reflected in a concise code fragment.

The first operation normalizes the rotation count with respect to the vector length:

k %= nums.size();

By applying the modulo operator, any k that exceeds the number of elements is reduced to an equivalent smaller offset. This ensures that the subsequent steps work with the minimal necessary shift.

The second operation converts the right-rotation problem into a left-rotation that std::rotate can handle directly. The transformation is performed by subtracting the normalized k from the vector size:

k = nums.size() - k;

When k is zero after the modulo, the subtraction yields the original size, which std::rotate interprets as a no-op. For any other value, the computed index points to the element that should become the new first element after rotation.

The final step invokes the standard algorithm std::rotate, supplying iterators that delineate the range to be rotated and the pivot position:

std::rotate(nums.begin(), nums.begin() + k, nums.end());

std::rotate rearranges the elements in-place, moving the segment [nums.begin(), nums.begin() + k) to the end while preserving the relative order of all elements.

Edge Cases Handled

When k is a multiple of the vector length, the modulo operation reduces k to zero. The subsequent subtraction yields a pivot equal to the vector size, causing std::rotate to receive a range where the middle iterator coincides with the end iterator. In this situation the algorithm performs no modifications, effectively leaving the vector unchanged.

If k is zero from the outset, the modulo step leaves it unchanged, and the subtraction produces a pivot equal to the vector size. The call to std::rotate again results in a no-op, confirming that the method gracefully handles a request for zero rotation.

For vectors containing a single element, the size is one. The modulo operation yields zero regardless of k, and the subtraction produces a pivot of one. std::rotate receives a range where the middle iterator is the end iterator, which again leads to no movement, correctly preserving the sole element.

The code also implicitly supports negative values of k if they are supplied, because the modulo operation with a negative dividend yields a negative remainder in C++. The subsequent subtraction still computes a valid pivot within the range [0, size], allowing std::rotate to perform the appropriate leftward shift that corresponds to a rightward rotation by a negative offset.

Performance Optimizations

The implementation minimizes work by reducing the rotation count with a modulo operation, eliminating unnecessary full-cycle rotations. This early reduction prevents the algorithm from traversing the vector more times than required.

By delegating the core rearrangement to std::rotate, the method benefits from the highly tuned library implementation, which typically employs a three-reverse technique or block swapping to achieve the rotation with a minimal number of element moves. This in-place strategy avoids allocating auxiliary storage, keeping the memory footprint low.

The use of iterator arithmetic (nums.begin() + k) provides direct access to the pivot position without additional loops or index calculations, allowing the compiler to generate efficient pointer arithmetic.

Overall, the combination of input normalization, transformation to a left-rotation, and reliance on a standard library routine results in a concise solution that executes with optimal data movement and low overhead.

Imagine you have a long line of numbered toy blocks sitting in a row. Sometimes you want to shift these blocks so that the ones at the end move to the front, just like a spinning merry-go-round.

The first part of this code finds out exactly how many blocks need to move. If you have a very long line of blocks and you want to jump them forward a huge number of times, it figures out the shorter way to get them to the same spots.

Next, the code figures out the new starting point for the line. It counts backward from the end of the row to find the perfect spot where the shift should happen.

Finally, the computer uses a special command to shuffle the blocks around. It takes the group of blocks starting from that new spot and moves them to the very front of the line, while pushing the other blocks neatly out of the way to the back. Every block stays in its same relative order, but they have all slid over to take their new places in the row.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python								TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python	C#	Rust	JS	Go				TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	AdelDaniel										Dart
	aylei					Rust
	begeekmyfriend								C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda			Python
	charles-wangkai		Java
	chenyanzhe	C++
	Dijkstra-Edu		Java
	everthis						JS
	fartem									Ruby
	FelixFan1122				C#
	fpdjsns	C++
	fsq	C++
	gaosq0604			Python
	gouthampradhan		Java
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx								C
	linouk23	C++
	lkwq007			Python
	luangong	C++
	MacJim	C++
	muhammadfarhankt							Go
	pruthvikp			Python
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28		Java
	vthwang		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
fsq	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
pruthvikp	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality