LogoKode$word

LeetCode 154: Find Minimum in Rotated Sorted Array II – Java Binary Search Solution Explained

Learn how to solve LeetCode 154 Find Minimum in Rotated Sorted Array II using Binary Search in Java. Includes brute force approach, optimized solution, duplicates handling, dry run, intuition, complexity analysis, and interview explanation.

Krishna Shrivastava
4 views
LinkedInGithubX
0
0
HardBinary SearchRotated Sorted ArrayJavaLeetCode
LeetCode 154: Find Minimum in Rotated Sorted Array II – Java Binary Search Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 154 – Find Minimum in Rotated Sorted Array II is a classic binary search interview problem.

This problem is an advanced version of:

  1. Find Minimum in Rotated Sorted Array

The major difference is:

The array may contain duplicates.

That small change makes the problem much harder because duplicates can break normal binary search logic.

This problem teaches:

  1. Modified binary search
  2. Rotated array concepts
  3. Handling duplicates
  4. Edge case optimization
  5. Interview problem-solving techniques

Problem Link

🔗 Problem

LeetCode 154: Find Minimum in Rotated Sorted Array II

Official Problem:

LeetCode Problem Link

Problem Statement

An ascending sorted array is rotated between 1 and n times.

Example:

[0,1,4,4,5,6,7]

may become:

[4,5,6,7,0,1,4]

or

[0,1,4,4,5,6,7]

Given the rotated sorted array nums that may contain duplicates, return the minimum element.

Example

Example 1

Input:

nums = [1,3,5]

Output:

1

Example 2

Input:

nums = [2,2,2,0,1]

Output:

0

Understanding Rotated Sorted Arrays

Normally a sorted array looks like:

[1,2,3,4,5]

After rotation:

[4,5,1,2,3]

The minimum element becomes the pivot point.

Our goal is to efficiently find this pivot.

Brute Force Approach

Intuition

Traverse the entire array and keep track of the smallest element.

Algorithm

  1. Initialize minimum as first element.
  2. Traverse the array.
  3. Update minimum whenever a smaller element appears.
  4. Return minimum.

Java Code – Brute Force

class Solution {

public int findMin(int[] nums) {

int min = nums[0];

for(int num : nums) {
min = Math.min(min, num);
}

return min;
}
}

Dry Run – Brute Force

Input:

[2,2,2,0,1]

Traversal:

ElementMinimum
22
22
22
00
10

Final answer:

0

Complexity Analysis – Brute Force

Time Complexity

O(N)

Space Complexity

O(1)

Can We Do Better?

Yes.

Since the array is sorted and rotated, we can use Binary Search.

However, duplicates make the problem tricky.

Binary Search Intuition

In a rotated sorted array:

  1. One half is always sorted.
  2. The minimum lies in the unsorted half.

Without duplicates, binary search becomes straightforward.

But duplicates create ambiguity.

Example:

[2,2,2,0,2]

If:

nums[mid] == nums[right]

we cannot determine which side contains the minimum.

So we shrink the search space carefully.

Key Binary Search Observations

Case 1

If:

nums[mid]<nums[right]nums[mid] < nums[right]nums[mid]<nums[right]

then the right half is sorted, and minimum may lie at mid or left side.

Move:

right = mid

Case 2

If:

nums[mid]>nums[right]nums[mid] > nums[right]nums[mid]>nums[right]

then minimum lies in the right half.

Move:

left = mid + 1

Case 3

If:

nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]

we cannot identify the correct side.

Safely reduce search space:

right--

Optimized Binary Search Approach

Steps

  1. Initialize two pointers:
  2. left
  3. right
  4. Find middle element.
  5. Compare nums[mid] with nums[right].
  6. Narrow the search space accordingly.
  7. Continue until pointers meet.

Java Binary Search Solution

class Solution {

public int findMin(int[] nums) {

if(nums.length == 1) return nums[0];

int left = 0;
int right = nums.length - 1;

int min = Integer.MAX_VALUE;

while(left <= right) {

int mid = left + (right - left) / 2;

if(nums[mid] < nums[right]) {

right = mid;
min = Math.min(min, nums[right]);

}
else if(nums[mid] > nums[right]) {

min = Math.min(min, nums[right]);
left = mid + 1;

}
else {

right--;
}

min = Math.min(min, nums[mid]);
}

return min;
}
}

Dry Run – Binary Search

Input

nums = [2,2,2,0,1]

Initial State

LeftRight
04

Iteration 1

Mid

mid = 2

Value:

nums[mid] = 2
nums[right] = 1

Since:

2>12 > 12>1

Move:

left = mid + 1

Now:

LeftRight
34

Iteration 2

Mid

mid = 3

Value:

nums[mid] = 0
nums[right] = 1

Since:

0<10 < 10<1

Move:

right = mid

Now:

LeftRight
33

Final Answer

0

Time Complexity Analysis

Average Case

O(log N)

Worst Case

Due to duplicates:

O(N)

Why Worst Case Becomes O(N)

Consider:

[1,1,1,1,1]

Every comparison becomes:

nums[mid] == nums[right]

We can only shrink by one element:

right--

This degrades binary search to linear complexity.

Interview Explanation

In interviews, explain:

Duplicates destroy the ability to always determine the sorted half uniquely. When nums[mid] == nums[right], we cannot confidently eliminate one side, so we reduce the search space by one element.

This is the key insight interviewers look for.

Common Mistakes

1. Using Standard Binary Search Logic

Standard rotated-array logic fails with duplicates.

2. Ignoring Duplicate Case

This condition is essential:

else {
right--;
}

3. Infinite Loop Errors

Always update pointers carefully.

Alternative Simpler Binary Search

A cleaner version:

class Solution {

public int findMin(int[] nums) {

int left = 0;
int right = nums.length - 1;

while(left < right) {

int mid = left + (right - left) / 2;

if(nums[mid] < nums[right]) {
right = mid;
}
else if(nums[mid] > nums[right]) {
left = mid + 1;
}
else {
right--;
}
}

return nums[left];
}
}

This is the most common interview solution.

FAQs

Q1. Why does binary search become O(N)?

Duplicates prevent us from discarding half the search space confidently.

Q2. Why compare with nums[right]?

It helps identify whether the minimum lies on the left or right side.

Q3. Is this problem important for interviews?

Yes.

It is a very popular advanced binary search interview problem.

Conclusion

LeetCode 154 is an excellent problem for mastering:

  1. Modified binary search
  2. Rotated sorted arrays
  3. Duplicate handling
  4. Search optimization

The key challenge is handling:

nums[mid]=nums[right]nums[mid] = nums[right]nums[mid]=nums[right]

correctly.

Once you understand this pattern, many advanced binary search interview problems become much easier.

Related Articles

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Search in Rotated Sorted Array – Binary Search Explained with Java Solution (LeetCode 33)

Learn how to efficiently search for an element in a rotated sorted array using binary search. This guide explains the intuition, multiple strategies, and a clean Java implementation that achieves O(log n) time complexity.

Read Article
Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

Find Minimum in Rotated Sorted Array – Binary Search Explained | LeetCode Medium 153

LeetCode 153 – Find the minimum element in a rotated sorted array in O(log n) time.

Read Article
LeetCode 61 Rotate List Java Solution | Brute Force + Optimal Approach Explained (Linked List Rotation)

LeetCode 61 Rotate List Java Solution | Brute Force + Optimal Approach Explained (Linked List Rotation)

Learn how to solve LeetCode 61 Rotate List using brute force and optimized linked list approaches. Includes dry runs, edge cases, complexity analysis, and common mistakes.

Read Article
Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

Learn Quick Sort with detailed intuition, partition logic, Java code, dry run, and complexity analysis. Perfect for coding interviews and DSA.

Read Article
Ai Assistant Kas