What is the brute force approach and complexity for Search in Rotated Sorted Array II?

Check every element for target with time complexity O(N) and space complexity O(1).

What is the optimal approach and complexity for Search in Rotated Sorted Array II?

LC 33's sorted-half check; when nums[lo] == nums[mid] == nums[hi], do lo++, hi-- with optimal time complexity O(N) and space complexity O(1).

Search in Rotated Sorted Array II

Q: How do you identify the pattern for Search in Rotated Sorted Array II?

Look for key signals in the prompt: "sorted, then rotated" indicates Same shape as LC 33: one half is usually sorted.; "may contain duplicates" indicates nums[lo] == nums[mid] no longer proves the left half is sorted. Watch for the all-equal case.; "return true / false" indicates Only presence matters, so we don't care which copy of target we find.; "how do duplicates affect run time?" indicates A hint that the answer is not O(log N) worst case..

Medium·LeetCode #81 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

This is Search in Rotated Sorted Array, but now the values may repeat.

The array nums was sorted from smallest to largest (duplicates allowed) and then possibly rotated: cut at some index and the front part moved to the back. For example, [0, 1, 2, 4, 4, 4, 5, 6, 6, 7] can become [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].

Given nums and a number target, return true if target is in nums, otherwise false. Try to do as few checks as you can.

Input

A rotated sorted array nums that may contain duplicates, and an integer target.

Output

true if target appears in nums, otherwise false.

Example 1

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0

Output: true

0 appears at indexes 3 and 4.

Example 2

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3

Output: false

3 is not in the array.

Example 3

Input: nums = [1, 0, 1, 1, 1], target = 0

Output: true

nums[lo], nums[mid] and nums[hi] are all 1 at the start, so you can't tell where the drop is. This is the case that breaks the LC 33 code.

Constraints

• 1 ≤ n ≤ 5000
• −10^4 ≤ nums[i] ≤ 10^4
• nums is a sorted array (duplicates allowed) that may have been rotated.
• −10^4 ≤ target ≤ 10^4
• Follow-up: how do duplicates change the running time?

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sorted, then rotated”

→ Same shape as LC 33: one half is usually sorted.

“may contain duplicates”

→ nums[lo] == nums[mid] no longer proves the left half is sorted. Watch for the all-equal case.

“return true / false”

→ Only presence matters, so we don't care which copy of target we find.

“how do duplicates affect run time?”

→ A hint that the answer is not O(log N) worst case.

Approach Complexity Ladder

Brute Force — linear scanO(N)O(1)

Check every element for target

Optimal — rotated search + shrink on tiesO(N)O(1)

LC 33's sorted-half check; when nums[lo] == nums[mid] == nums[hi], do lo++, hi--

Brute Force Intuition

Walk the whole array and return true as soon as you see target.

Recognition rule for this sub-pattern:

Array is not fully sorted, but one half always is. Decide which half is sorted, then which half holds the answer.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Find Peak Element