Abstract / Summary

Find the smallest number in a rotated sorted array that may have duplicate values.

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 47% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

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 class Solution with a single public member function findMin. The function receives a reference to a vector<int> and returns the smallest integer contained in the vector. The core operation is delegated to the standard library algorithm std::min_element, which abstracts the traversal and comparison logic.

Key Steps

The function consists of three logical parts: the method signature, the comment indicating the chosen approach, and the return statement that invokes std::min_element.

int findMin(vector<int>& nums) {
    // brute-force
    return *min_element(nums.begin(), nums.end());
}

The comment labels the strategy as “brute-force,” reflecting that the algorithm examines each element to determine the minimum. The call to min_element receives two iterators, nums.begin() and nums.end(), which define the range covering the entire vector. The algorithm returns an iterator pointing to the smallest element; dereferencing this iterator yields the integer value that the function returns.

Edge Cases Handled

When the input vector contains a single element, the range defined by begin() and end() still includes that element, and min_element correctly returns an iterator to it, resulting in the original value being returned. For vectors with duplicate minimum values, min_element stops at the first occurrence, which is acceptable because all duplicates share the same value. The implementation assumes that the vector is non-empty; the standard library’s min_element requires a valid range, and invoking it on an empty range would be undefined. Within the intended usage, the function safely handles any non-empty vector regardless of size or value distribution.

Performance Optimizations

By leveraging std::min_element, the code benefits from the highly optimized implementation provided by the C++ Standard Library. The algorithm is typically inlined and may take advantage of compiler vectorization or other low-level optimizations, reducing overhead compared to a manual loop. Additionally, using iterators avoids copying the container or its elements, keeping memory usage minimal. The single pass over the data ensures that the function performs the minimum amount of work necessary to locate the smallest value.

Imagine you have a big treasure chest filled with numbered cards scattered all around. Some cards have small numbers and some have really big numbers. The computer wants to find the smallest number hidden inside that chest. To do this, the computer looks at every single card one by one, from the very first card at the start all the way to the last card at the end. After checking all of them, the computer picks out the card with the tiniest number written on it and holds it up for you to see. It is just like searching for the smallest seashell on a beach.

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++	Python				Java			TS
	WalkCCC	C++	Python				Java
	leetcode.ca	C++	Python		Rust	JS	Java		Go	TS
	LeetcodeHelp	C++	Python				Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python				Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	fpdjsns	C++
	gaosq0604		Python
	halfrost								Go
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx							C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru				Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	trung-hn		Python
	varunu28						Java
	wisdompeak	C++
	withaarzoo	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
gaosq0604	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

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