Find Minimum in Rotated Sorted Array in DSA Typescript

Mental Model

A rotated sorted array is like a sorted list that got shifted. The smallest number is where the shift happened.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock, the smallest number is where the clock starts again after the rotation.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> null

Rotated array example:
[4] -> [5] -> [1] -> [2] -> [3] -> null
↑ (rotation point, smallest element)

Dry Run Walkthrough

Input: array: [4, 5, 1, 2, 3]

Goal: Find the smallest number in the rotated sorted array

Step 1: Set left=0, right=4 (start and end indices)

array: [4, 5, 1, 2, 3], left=0, right=4

Why: We start searching between the whole array

Step 2: Calculate mid = (0 + 4) // 2 = 2, check array[mid]=1

array: [4, 5, 1, 2, 3], left=0, mid=2, right=4

Why: Mid helps us decide which half to search next

Step 3: Compare array[mid]=1 with array[right]=3; since 1 < 3, move right to mid=2

array: [4, 5, 1, 2, 3], left=0, right=2

Why: Minimum must be at mid or to the left because mid is smaller than right

Step 4: Calculate mid = (0 + 2) // 2 = 1, check array[mid]=5

array: [4, 5, 1, 2, 3], left=0, mid=1, right=2

Why: Narrowing down the search to find the smallest element

Step 5: Compare array[mid]=5 with array[right]=1; since 5 > 1, move left to mid+1=2

array: [4, 5, 1, 2, 3], left=2, right=2

Why: Minimum must be to the right of mid because mid is greater than right

Result:

array: [4, 5, 1, 2, 3], left=2, right=2 -> minimum is array[2] = 1

Annotated Code

DSA Typescript

class RotatedSortedArray {
  static findMin(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] > nums[right]) {
        left = mid + 1; // minimum is in right half
      } else {
        right = mid; // minimum is at mid or left half
      }
    }
    return nums[left];
  }
}

// Driver code
const arr = [4, 5, 1, 2, 3];
console.log(RotatedSortedArray.findMin(arr));

while (left < right) {

loop until search space narrows to one element

const mid = Math.floor((left + right) / 2);

find middle index to split search space

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

if mid element is greater than right, minimum is in right half

left = mid + 1; // minimum is in right half

move left pointer to mid+1 to discard left half

else { right = mid; // minimum is at mid or left half }

otherwise, minimum is at mid or left half, move right pointer

return nums[left];

left points to minimum element after loop ends

Output

1

Complexity Analysis

Time: O(log n) because the search space halves each step using binary search

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach scans all elements O(n), this binary search approach is faster for large arrays

Edge Cases

Array not rotated (e.g., [1, 2, 3, 4, 5])

Algorithm returns the first element as minimum correctly

DSA Typescript

while (left < right) {

Array with one element (e.g., [10])

Returns the single element as minimum without entering loop

DSA Typescript

while (left < right) {

Array rotated at last element (e.g., [2, 3, 4, 5, 1])

Algorithm finds the minimum at the last index correctly

DSA Typescript

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

When to Use This Pattern

When you see a sorted array that might be rotated and need the smallest element, use binary search on the rotation point to find it efficiently.

Common Mistakes

Mistake: Comparing nums[mid] with nums[left] instead of nums[right]
Fix: Compare nums[mid] with nums[right] to decide which half contains the minimum

Mistake: Using <= instead of < in while loop causing infinite loop
Fix: Use while (left < right) to ensure loop ends when pointers meet

Summary

Finds the smallest element in a rotated sorted array using binary search.

Use when you have a sorted array shifted and want to find the rotation point quickly.

The smallest element is where the order breaks; binary search narrows down this point efficiently.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array like [4, 5, 6, 7, 0, 1, 2]?

easy

A. To find the smallest number where the rotation happened

B. To find the largest number in the array

C. To count how many times the array was rotated

D. To sort the array again

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is originally sorted but then shifted. The smallest number is where the rotation happened.

2. Step 2: Identify the minimum element

   The minimum element is the smallest number, marking the rotation point.

3. Final Answer:

   To find the smallest number where the rotation happened -> Option A

4. Quick Check:

   Minimum = smallest number at rotation [OK]

Hint: Look for the smallest number after rotation point [OK]

Common Mistakes:

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

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

easy

A. function findMin(nums) -> number {}

B. func findMin(nums: number[]): number {}

C. def findMin(nums: number[]): number {}

D. function findMin(nums: number[]): number {}

Solution

1. Step 1: Recognize TypeScript function syntax

   TypeScript uses function keyword with typed parameters and return type.

2. Step 2: Check each option

   function findMin(nums: number[]): number {} uses correct TypeScript syntax. The other options use keywords from other languages or invalid arrow syntax.

3. Final Answer:

   function findMin(nums: number[]): number {} -> Option D

4. Quick Check:

   TypeScript function syntax = function findMin(nums: number[]): number {} [OK]

Hint: Use 'function' keyword with typed parameters in TypeScript [OK]

Common Mistakes:

• Using Python or other language keywords
• Missing type annotations
• Incorrect arrow syntax in function declaration

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

function findMin(nums: number[]): number {
  let left = 0;
  let 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([3,4,5,1,2]));

medium

A. 3

B. 1

C. 5

D. 2

Solution

1. Step 1: Understand the binary search logic

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

2. Step 2: Trace the code with input [3,4,5,1,2]

   Initial left=0, right=4, mid=2 (value 5). Since 5 > 2, left = mid+1 = 3. Now left=3, right=4, mid=3 (value 1). Since 1 <= 2, right = mid = 3. Loop ends as left == right == 3. Return nums[3] = 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Minimum found = 1 [OK]

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

Common Mistakes:

• Returning mid instead of nums[left]
• Confusing left and right updates
• Not using floor for mid calculation

4. Identify the bug in this TypeScript function to find the minimum in a rotated sorted array:

function findMin(nums: number[]): number {
  let left = 0;
  let 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' instead of 'left <= right'

B. The mid calculation is incorrect

C. The return statement should be nums[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.

2. Step 2: Correct loop condition for binary search

   Using 'left < right' ensures the loop stops when left meets right, correctly identifying minimum.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use 'left < right' for binary search loops [OK]

Common Mistakes:

• Using <= causes infinite loops
• Changing mid calculation unnecessarily
• Returning wrong index value

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

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

hard

A. Sort the array before searching

B. Increase left by one when nums[mid] equals nums[right]

C. Decrease right by one when nums[mid] equals nums[right]

D. Return nums[mid] immediately when equal

Solution

1. Step 1: Understand duplicates effect

   Duplicates can make it unclear which side to search when nums[mid] == nums[right].

2. Step 2: Modify binary search to handle duplicates

   When equal, safely reduce right by one to shrink search space without missing minimum.

3. Final Answer:

   Decrease right by one when nums[mid] equals nums[right] -> Option C

4. Quick Check:

   Handle duplicates by right-- when equal [OK]

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

Common Mistakes:

• Increasing left instead of decreasing right
• Returning mid too early
• Ignoring duplicates and failing on edge cases