Find Minimum in Rotated Sorted Array in DSA Java - Execution Trace

Concept Flow - Find Minimum in Rotated Sorted Array

Start with full array

↓

Set low=0, high=n-1

↓

While low < high

↓

Find mid = (low+high)/2

↓

Compare nums[mid

↓

mid

↓

Loop until low == high

↓

Return nums[low

We use two pointers low and high to narrow down the search space by comparing middle and high elements until low meets high, which points to the minimum.

Execution Sample

DSA Java

int findMin(int[] nums) {
  int low = 0, high = nums.length - 1;
  while (low < high) {
    int mid = (low + high) / 2;
    if (nums[mid] > nums[high]) low = mid + 1;
    else high = mid;
  }
  return nums[low];
}

This code finds the minimum element in a rotated sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	nums[mid]	nums[high]	Pointer Changes	Visual State
1	Initialize pointers	0	6	-	-	-	low=0, high=6	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	7	2	-	[4,5,6,7,0,1,2]
3	Compare nums[mid] > nums[high]	0	6	3	7	2	7 > 2 is True	[4,5,6,7,0,1,2]
4	Update low = mid + 1	4	6	-	-	-	low=4	[4,5,6,7,0,1,2]
5	Calculate mid	4	6	5	1	2	-	[4,5,6,7,0,1,2]
6	Compare nums[mid] > nums[high]	4	6	5	1	2	1 > 2 is False	[4,5,6,7,0,1,2]
7	Update high = mid	4	5	-	-	-	high=5	[4,5,6,7,0,1,2]
8	Calculate mid	4	5	4	0	1	-	[4,5,6,7,0,1,2]
9	Compare nums[mid] > nums[high]	4	5	4	0	1	0 > 1 is False	[4,5,6,7,0,1,2]
10	Update high = mid	4	4	-	-	-	high=4	[4,5,6,7,0,1,2]
11	Check low < high	4	4	-	-	-	4 < 4 is False	[4,5,6,7,0,1,2]
12	Return nums[low]	4	4	-	0	-	-	Minimum found at index 4: 0

💡 Loop ends when low equals high; nums[low] is the minimum element.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	Final
low	0	4	4	4	4
high	6	6	5	4	4
mid	-	3	5	4	-
nums[mid]	-	7	1	0	-
nums[high]	-	2	2	1	-

Key Moments - 3 Insights

Why do we update low to mid + 1 when nums[mid] > nums[high]?

Because nums[mid] is greater than nums[high], the minimum must be to the right of mid, so we move low to mid + 1 (see step 4 in execution_table).

Why do we update high to mid when nums[mid] <= nums[high]?

Because nums[mid] could be the minimum or it lies to the left, so we move high to mid to include mid in the search (see step 7 and 10).

Why does the loop stop when low equals high?

When low equals high, the search space is one element, which must be the minimum (see step 11).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of low?

A 4

B 3

C 0

D 6

💡 Hint

Check the 'Pointer Changes' and 'low' column at step 4 in execution_table.

At which step does the condition low < high become false?

A Step 10

B Step 11

C Step 12

D Step 9

💡 Hint

Look at the 'Check low < high' operation and condition result in execution_table.

If nums[mid] was always less than or equal to nums[high], how would the pointer updates change?

A low would always increase

B high would always move to mid

C low and high would not change

D low would move to mid + 1

💡 Hint

Refer to the condition and pointer update rules in execution_table steps 6 and 9.

Concept Snapshot

Find Minimum in Rotated Sorted Array
- Use binary search with low and high pointers
- Calculate mid = (low + high) / 2
- If nums[mid] > nums[high], move low to mid + 1
- Else move high to mid
- Loop until low == high
- nums[low] is the minimum element

Full Transcript

This concept shows how to find the minimum element in a rotated sorted array using a binary search approach. We start with two pointers, low at 0 and high at the last index. We calculate the middle index and compare the middle element with the element at high. If the middle element is greater, the minimum must be to the right, so we move low to mid + 1. Otherwise, the minimum is at mid or to the left, so we move high to mid. We repeat this until low equals high, which points to the minimum element. The execution table traces each step, showing pointer updates and comparisons. Key moments clarify why we update pointers this way and when the loop ends. The visual quiz tests understanding of pointer values and loop termination. This method efficiently finds the minimum in O(log n) time.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array?

easy

A. To find the largest element in the array

B. To find the smallest element after the rotation point

C. To count the number of rotations

D. To sort the array again

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is a sorted array shifted at some pivot. The smallest element is the rotation point.

2. Step 2: Identify the minimum element

   The minimum element is the smallest value after the rotation, which is the point where the order breaks.

3. Final Answer:

   To find the smallest element after the rotation point -> Option B

4. Quick Check:

   Minimum element = smallest after rotation [OK]

Hint: Look for the point where order breaks to find minimum [OK]

Common Mistakes:

• Confusing minimum with maximum element
• Trying to count rotations instead of finding minimum
• Assuming array is fully sorted without rotation

2. Which Java syntax correctly declares a method to find the minimum in a rotated sorted array?

easy

A. public int findMin(int[] nums) {}

B. int findMin(int nums) {}

C. void findMin(int[] nums) {}

D. public static findMin(int[] nums) {}

Solution

1. Step 1: Check method return type and parameters

   The method should return an int (the minimum value) and accept an int array parameter.

2. Step 2: Validate Java method syntax

   public int findMin(int[] nums) {} uses 'public int findMin(int[] nums) {}' which is correct Java syntax for this method.

3. Final Answer:

   public int findMin(int[] nums) {} -> Option A

4. Quick Check:

   Correct method signature = public int findMin(int[] nums) {} [OK]

Hint: Method must return int and accept int array parameter [OK]

Common Mistakes:

• Missing return type or using void incorrectly
• Incorrect parameter syntax
• Missing access modifier or static keyword incorrectly

3. What is the output of the following code snippet?

int[] nums = {4,5,6,7,0,1,2};
System.out.println(findMin(nums));

public static int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

medium

A. 2

B. 4

C. 7

D. 0

Solution

1. Step 1: Understand the binary search logic

   The code uses binary search to find the minimum by comparing middle and right elements, narrowing the search space.

2. Step 2: Trace the loop with given array

   Array: [4,5,6,7,0,1,2] - mid=3 (value 7), 7 > 2, so left = mid+1 = 4 - left=4, right=6 - mid=5 (value 1), 1 <= 2, so right = mid = 5 - left=4, right=5 - mid=4 (value 0), 0 <= 1, so right = mid = 4 Loop ends when left == right == 4, nums[4] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Minimum element found = 0 [OK]

Hint: Compare mid and right to narrow search for minimum [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing comparison direction in binary search
• Not updating left or right correctly

4. Identify the error in this code snippet for finding minimum in rotated sorted array:

public static int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

medium

A. The return statement should be 'nums[right]'

B. The mid calculation is incorrect

C. The loop condition should be 'left < right' instead of 'left <= right'

D. The array should be sorted before searching

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'left <= right', which can cause infinite loop or index errors because left can go beyond right.

2. Step 2: Correct the loop condition

   Changing the condition to 'left < right' ensures the loop stops when left meets right, correctly identifying the minimum index.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right' -> Option C

4. Quick Check:

   Loop condition must be 'left < right' [OK]

Hint: Use 'left < right' to avoid infinite loops in binary search [OK]

Common Mistakes:

• Using 'left <= right' causing infinite loops
• Incorrectly adjusting right pointer
• Returning wrong array element after loop

5. Given a rotated sorted array that may contain duplicates, which modification is needed in the binary search to find the minimum correctly?

int[] nums = {2,2,2,0,1,2};

hard

A. Add a condition to reduce right by one when nums[mid] equals nums[right]

B. Ignore duplicates and proceed as usual

C. Sort the array before searching

D. Use linear search instead of binary search

Solution

1. Step 1: Understand the effect of duplicates

   Duplicates can cause ambiguity when nums[mid] equals nums[right], making it unclear which side to search.

2. Step 2: Modify binary search to handle duplicates

   When nums[mid] == nums[right], reduce right by one to shrink search space safely without missing minimum.

3. Final Answer:

   Add a condition to reduce right by one when nums[mid] equals nums[right] -> Option A

4. Quick Check:

   Handle duplicates by shrinking right pointer [OK]

Hint: When equal, reduce right pointer to handle duplicates [OK]

Common Mistakes:

• Ignoring duplicates causing wrong minimum
• Sorting array which is inefficient
• Switching to linear search unnecessarily