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

Concept Flow - Find Minimum in Rotated Sorted Array

Start with full array

↓

Check if array is rotated?

↓

Use binary search

↓

Find mid element

↓

Compare mid with right

↓

Search right half

↓

Repeat until left == right

↓

Return element at left

Start by checking if array is rotated. If yes, use binary search comparing mid and right elements to narrow down the minimum until left meets right.

Execution Sample

DSA Javascript

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

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

Execution Table

Step	Operation	Left Index	Right Index	Mid Index	Compare nums[mid] and nums[right]	Pointer Changes	Array State	Current Minimum Candidate
1	Initialize pointers	0	6	-	-	left=0, right=6	[4,5,6,7,0,1,2]	N/A
2	Calculate mid	0	6	3	nums[3]=7 > nums[6]=2	left = mid + 1 = 4	[4,5,6,7,0,1,2]	N/A
3	Calculate mid	4	6	5	nums[5]=1 <= nums[6]=2	right = mid = 5	[4,5,6,7,0,1,2]	N/A
4	Calculate mid	4	5	4	nums[4]=0 <= nums[5]=1	right = mid = 4	[4,5,6,7,0,1,2]	N/A
5	Check loop condition	4	4	-	-	left == right, loop ends	[4,5,6,7,0,1,2]	nums[4] = 0

💡 left equals right at index 4, minimum element found at nums[4] = 0

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
left	0	4	4	4	4
right	6	6	5	4	4
mid	-	3	5	4	4

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[right] instead of nums[left]?

Comparing nums[mid] with nums[right] helps decide which half contains the minimum because the rightmost element is a reliable pivot in rotated arrays. See execution_table rows 2-4 where this comparison guides pointer moves.

Why does the loop stop when left equals right?

When left equals right, the search space is narrowed down to one element, which must be the minimum. This is shown in execution_table row 5 where left and right both are 4.

What if the array is not rotated?

If the array is not rotated, nums[mid] will always be less than or equal to nums[right], so right pointer moves left until left equals right, returning the first element. This is implied in the concept flow's 'No' branch.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'left' after step 2?

A 3

B 4

C 0

D 6

💡 Hint

Check the 'Pointer Changes' column in row 2 of execution_table.

At which step does the loop condition become false?

A Step 5

B Step 4

C Step 3

D Step 2

💡 Hint

Look at the 'Check loop condition' operation in execution_table row 5.

If nums[mid] was always less than nums[right], how would the pointers change?

A both pointers would stay the same

B left would move right

C right would move left

D left would move left

💡 Hint

Refer to pointer changes in execution_table rows 3 and 4 where nums[mid] <= nums[right].

Concept Snapshot

Find Minimum in Rotated Sorted Array
- Use binary search with left and right pointers
- Compare nums[mid] with nums[right]
- If nums[mid] > nums[right], move left to mid+1
- Else move right to mid
- Loop until left == right
- Return nums[left] as minimum

Full Transcript

This concept finds the minimum element in a rotated sorted array using binary search. We start with two pointers, left at 0 and right at the last index. We check if the array is rotated by comparing elements. Using binary search, we calculate mid and compare nums[mid] with nums[right]. If nums[mid] is greater, the minimum is in the right half, so we move left to mid+1. Otherwise, the minimum is in the left half, so we move right to mid. We repeat until left equals right, which points to the minimum element. This method efficiently narrows down the search space in logarithmic 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 count the number of rotations

C. To find the smallest element after the rotation point

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 goal

   The goal is to find the smallest element, which is the minimum after rotation.

3. Final Answer:

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

4. Quick Check:

   Minimum element = smallest after rotation [OK]

Hint: Look for the smallest element where order breaks [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to start a binary search loop in JavaScript for finding minimum in rotated sorted array nums?

easy

A. while(left < right) { ... }

B. for(let left = 0, right = nums.length - 1; left <= right; )

C. for(let i = 0; i < nums.length; i++)

D. if(nums.length === 0) return -1

Solution

1. Step 1: Identify the loop type for binary search

   Binary search typically uses a while loop with condition left < right to narrow down the search space.

2. Step 2: Check options

   while(left < right) { ... } uses while(left < right), which is correct for binary search in this problem.

3. Final Answer:

   while(left < right) { ... } -> Option A

4. Quick Check:

   Binary search loop uses while(left < right) [OK]

Hint: Use while loop with left < right for binary search [OK]

Common Mistakes:

• Using for loop incorrectly for binary search
• Using <= instead of < causing infinite loops
• Not initializing left and right properly

3. What will be the output of the following code?

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

console.log(findMin([4,5,6,7,0,1,2]));

medium

A. 1

B. 4

C. 7

D. 0

Solution

1. Step 1: Understand the binary search logic

   The code compares middle element with right element to decide which half contains the minimum.

2. Step 2: Trace the code with input [4,5,6,7,0,1,2]

   Initially left=0, right=6. Mid=3 (value 7). Since 7 > 2, left = mid+1 = 4. Now left=4, right=6. Mid=5 (value 1). 1 <= 2, so right=mid=5. Next left=4, right=5. Mid=4 (value 0). 0 <= 1, right=mid=4. Now left=4, right=4, loop ends. Return nums[4] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Minimum element found = 0 [OK]

Hint: Compare mid with right to decide search half [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing comparison direction
• Not updating pointers correctly

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

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

medium

A. The loop condition should be left < right, not left <= right

B. The mid calculation is incorrect

C. The return statement should be nums[right]

D. The comparison should be nums[mid] < nums[right]

Solution

1. Step 1: Analyze loop condition

   The loop uses left <= right, which can cause infinite loop or skip the correct minimum index.

2. Step 2: Correct loop condition

   Binary search for minimum in rotated array requires left < right to narrow search correctly without missing elements.

3. Final Answer:

   The loop condition should be left < right, not left <= right -> Option A

4. Quick Check:

   Use while(left < right) for correct binary search [OK]

Hint: Use strict less than in binary search loops [OK]

Common Mistakes:

• Using <= causing infinite loops
• Changing mid calculation unnecessarily
• Returning wrong index after loop

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

hard

A. Return nums[mid] immediately when nums[mid] == nums[right]

B. When nums[mid] == nums[right], reduce right by 1 to skip duplicate

C. Always move left to mid + 1 when nums[mid] >= nums[right]

D. Sort the array first before applying binary search

Solution

1. Step 1: Understand duplicates effect

   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], safely reduce right by 1 to skip duplicate and continue search.

3. Final Answer:

   When nums[mid] == nums[right], reduce right by 1 to skip duplicate -> Option B

4. Quick Check:

   Handle duplicates by shrinking right pointer [OK]

Hint: Skip duplicates by decrementing right when equal [OK]

Common Mistakes:

• Ignoring duplicates causing wrong minimum
• Moving left pointer incorrectly on equality
• Sorting array unnecessarily