Find Minimum in Rotated Sorted Array in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we just scan the entire rotated sorted array to find the minimum?

Scanning the entire array takes O(n) time, which is slower. Using the special property of rotation, we can find the minimum in O(log n) time using a binary search approach.

intermediate

In the binary search for minimum in rotated sorted array, what does it mean if the middle element is greater than the rightmost element?

It means the minimum is in the right half of the array because the rotation point is to the right of mid.

beginner

What is the stopping condition in the binary search to find the minimum in a rotated sorted array?

When the search space reduces to one element, that element is the minimum.

intermediate

Show the binary search steps to find the minimum in [4,5,6,7,0,1,2].

Start: left=0, right=6 mid=3 (value=7) > right=6 (value=2) → minimum in right half → left=mid+1=4 Now left=4, right=6 mid=5 (value=1) < right=6 (value=2) → minimum in left half including mid → right=mid=5 Now left=4, right=5 mid=4 (value=0) < right=5 (value=1) → right=mid=4 left=4, right=4 → stop, minimum=0 at index 4

What is the time complexity of finding the minimum in a rotated sorted array using binary search?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Binary search divides the search space in half each time, leading to O(log n) time.

If the middle element is less than the rightmost element in the rotated array, where is the minimum?

A Cannot determine

B In the right half excluding mid

C At the middle element only

D In the left half including mid

If mid < right, the minimum lies in the left half including mid.

What does it mean if the array is not rotated?

A The last element is the minimum

B The first element is the minimum

C The middle element is the minimum

D The array is empty

If the array is sorted and not rotated, the first element is the smallest.

Which of these arrays is a rotated sorted array?

A [5,4,3,2,1]

B [1,2,3,4,5]

C [3,4,5,1,2]

D [2,1,3,4,5]

A is descending sorted; B is sorted but not rotated; C is rotated sorted ascending; D is unsorted.

What is the minimum element in [6,7,1,2,3,4,5]?

A 1

B 6

C 7

D 5

1 is the smallest element after rotation.

Explain how binary search helps find the minimum in a rotated sorted array.

Think about how rotation affects order and how to narrow down the search.

Describe the characteristics of a rotated sorted array and how it differs from a normal sorted array.

Imagine a sorted list shifted like a clock hand.

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