Find Minimum in Rotated Sorted Array in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the minimum element output in a rotated sorted array

What is the output of the following Java code that finds the minimum element in a rotated sorted array?

DSA Java

public class Solution {
    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];
    }

    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        System.out.println(findMin(nums));
    }
}

A 1

B 7

C 4

D 0

💡 Hint

Focus on how the binary search narrows down the minimum element by comparing mid and right elements.

The code uses binary search to find the smallest element in the rotated sorted array. Since the array is rotated, the minimum element is the only element where the previous element is greater. The algorithm compares nums[mid] with nums[right] to decide which half to search next. The output is 0, the smallest element.

❓ Predict Output

intermediate

Output of minimum finder on a non-rotated sorted array

What will be the output of the minimum finder code when the input array is not rotated but sorted?

DSA Java

public class Solution {
    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];
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        System.out.println(findMin(nums));
    }
}

A 1

B 7

C 4

D 0

💡 Hint

Consider that the array is already sorted and not rotated.

When the array is sorted and not rotated, the minimum element is the first element. The binary search will keep narrowing down to the leftmost element, which is 1.

🔧 Debug

advanced

Identify the error in this minimum finder code

What error will this code produce when trying to find the minimum in a rotated sorted array?

DSA Java

public class Solution {
    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 - 1;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] nums = {4,5,0,1,2};
        System.out.println(findMin(nums));
    }
}

A ArrayIndexOutOfBoundsException

B Compiles but throws NullPointerException

C Returns wrong minimum value

D Infinite loop

💡 Hint

Check the loop condition and how left and right pointers are updated.

The loop condition uses <= (should be <) and the right pointer is updated to mid - 1 (should be mid), which causes the code to skip the mid element that could be the minimum, returning wrong value. For {4,5,0,1,2}, it returns 4 instead of 0.

🧠 Conceptual

advanced

Why binary search works in rotated sorted arrays for finding minimum

Why does binary search work to find the minimum element in a rotated sorted array?

A Because the array elements are all unique and binary search requires unique elements

B Because the array is partially sorted and comparing mid with right helps decide which half contains the minimum

C Because the array is fully sorted and binary search always works on sorted arrays

D Because the minimum element is always at the middle index after rotation

💡 Hint

Think about how rotation affects sorting and how comparisons guide the search.

The rotated sorted array is partially sorted. By comparing the middle element with the rightmost element, we can determine which half contains the minimum element and discard the other half, making binary search effective.

❓ Predict Output

expert

Output of minimum finder with duplicates in rotated sorted array

What is the output of the following code when the rotated sorted array contains duplicates?

DSA Java

public class Solution {
    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 if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] nums = {2,2,2,0,1,2};
        System.out.println(findMin(nums));
    }
}

A 0

B 1

C 2

D ArrayIndexOutOfBoundsException

💡 Hint

Duplicates require an extra step to reduce the search space safely.

When duplicates exist, if nums[mid] equals nums[right], we reduce right by one to shrink the search space without missing the minimum. The minimum element is 0 in the given array.

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