Find Minimum in Rotated Sorted Array in DSA Java - Build from Scratch

Find Minimum in Rotated Sorted Array

📖 Scenario: You have a list of numbers that was originally sorted from smallest to largest. Then, someone rotated it at some point, moving some numbers from the front to the back. Your task is to find the smallest number in this rotated list.Imagine a clock face where the numbers have been shifted but still keep their order around the clock. You want to find the smallest number quickly.

🎯 Goal: Build a Java program that finds the minimum number in a rotated sorted array using a simple loop.

📋 What You'll Learn

Create an integer array called nums with the exact values {4, 5, 6, 7, 0, 1, 2}.

Create an integer variable called min and set it to the first element of nums.

Use a for loop with variable i to go through each element in nums starting from index 1.

Inside the loop, update min if the current element is smaller than min.

Print the value of min.

💡 Why This Matters

🌍 Real World

Finding the minimum in a rotated sorted array is useful in systems where data is shifted or rotated, such as circular buffers or rotated logs.

💼 Career

This problem is a common interview question that tests understanding of arrays, loops, and searching techniques.

1

Create the rotated sorted array

Create an integer array called nums with these exact values: {4, 5, 6, 7, 0, 1, 2}.

DSA Java

// Create the array nums with the given values
// Your code here

Hint

Use int[] nums = {4, 5, 6, 7, 0, 1, 2}; to create the array.

2

Set initial minimum value

Create an integer variable called min and set it to the first element of nums (that is, nums[0]).

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        // Create min and set it to nums[0]
        // Your code here
    }
}

Hint

Use int min = nums[0]; to set the initial minimum.

3

Find the minimum using a loop

Use a for loop with variable i starting from 1 to go through each element in nums. Inside the loop, if nums[i] is smaller than min, update min to nums[i].

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int min = nums[0];
        // Use a for loop from i = 1 to nums.length - 1
        // Inside, update min if nums[i] < min
        // Your code here
    }
}

Hint

Use a for loop starting at 1 and an if statement to compare and update min.

4

Print the minimum value

Print the value of min using System.out.println(min);.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
        }
        // Print the min value
        // Your code here
    }
}

Hint

Use System.out.println(min); to show the smallest number.

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