Find Minimum in Rotated Sorted Array – LeetCode Problems: A Complete Series

Problem Statement: Find Minimum in Rotated Sorted Array

Suppose an array is sorted in ascending order, but then rotated at an unknown pivot. Given such an array, your task is to find the minimum element in the array.

Example:

Input: nums = [3, 4, 5, 1, 2]
Output: 1

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Input:

• An array nums of n integers where n > 0.

Output:

• An integer representing the minimum element in the rotated sorted array.

Approach to the Problem:

To efficiently find the minimum in a rotated sorted array, we can use a modified binary search approach. Here’s how:

1. Initialization: Set two pointers, left and right, to the start and end of the array, respectively.
2. Binary Search: While left is less than right, calculate the midpoint:

• If the element at mid is greater than the element at right, it means the minimum must be in the right half, so move left to mid + 1.
• If the element at mid is less than or equal to the element at right, it means the minimum is in the left half, so move right to mid.

1. Result: When the loop ends, left will point to the minimum element.

Code Implementation:

public class FindMinimumInRotatedSortedArray {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // If mid element is greater than the rightmost element
            if (nums[mid] > nums[right]) {
                left = mid + 1; // Minimum is in the right half
            } else {
                right = mid; // Minimum is in the left half (or it could be mid)
            }
        }

        return nums[left]; // The minimum element
    }
}

Step-by-Step Explanation:

1. Initialization (Line 5):

int left = 0, right = nums.length - 1;

• We initialize left to the start of the array and right to the end of the array.

2. Binary Search Loop (Line 7):

while (left < right) {

• The loop continues until left is no longer less than right.

3. Calculate Midpoint (Line 8):

int mid = left + (right - left) / 2;

• We calculate the midpoint to avoid potential overflow with large indices.

4. Condition to Check (Lines 11-15):

if (nums[mid] > nums[right]) {
    left = mid + 1; // Minimum is in the right half
} else {
    right = mid; // Minimum is in the left half (or it could be mid)
}

• If the mid element is greater than the right element, it means the minimum element is in the right half. So, we adjust left to mid + 1.
• Otherwise, the minimum is in the left half or could be at mid, so we set right to mid.

5. Returning the Result (Line 18):

return nums[left]; // The minimum element

• Once the loop ends, left will point to the minimum element in the array.

Time and Space Complexity:

• Time Complexity: O(log n), because we are using binary search which divides the search space in half each time.
• Space Complexity: O(1), since we are using a constant amount of space for the pointers.

Example Execution:

Let’s take the example input:

Input: nums = [4, 5, 6, 7, 0, 1, 2]

Execution Steps:

1. Initial State: left = 0, right = 6 (array length is 7).
2. First Iteration:

• mid = 3, nums[mid] = 7, nums[right] = 2
• Since 7 > 2, move left to mid + 1 → left = 4.

1. Second Iteration:

• mid = 5, nums[mid] = 1, nums[right] = 2
• Since 1 <= 2, move right to mid → right = 5.

1. Third Iteration:

• mid = 4, nums[mid] = 0, nums[right] = 1
• Since 0 <= 1, move right to mid → right = 4.

1. End Condition: left = 4, right = 4, loop ends.

The minimum element is at nums[4], which is 0.

Output:

Output: 0

For any further help or modifications, feel free to reach out to Divi Tech HR Solution (info@divisolutions.in). Don’t forget to like and comment on this blog to share your feedback and support! Keep practicing these highly-rated LeetCode problems for interview preparation!