NeetCode 150: Find Minimum in Rotated Sorted Array

Table of contents

The Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

The Approach

The goal is to locate the point of inflection (POI), which is the point where all the elements to its left > nums[0] & all the elements to its right is < nums[0]. nums[0] is assumed to be the smallest value before searching for the minimum.

To optimize the search, we then apply Binary Search to find the POI, comparing it to nums[0] for each iteration.

My Solution

class Solution {
    public int findMin(int[] nums) {
        int maxBound = nums.length - 1;
        int minBound = 1;
            
        // The point of inflection (POI) is the smallest value. We then apply Binary Search to 
        // locate this value, comparing every midValue's element to smallestValueSeen & 
        // updating it if required.
        int smallestValueSeen = nums[0];
        while (maxBound >= minBound) {
            int midValue = (maxBound + minBound) / 2;
            
            // The POI lies in the forward direction.
            if (nums[midValue] >= nums[0]) {
                minBound = midValue + 1;
                smallestValueSeen = getSmallerValue(nums[midValue], smallestValueSeen);

            // The POI lies in the backwards direction.
            } else {
                maxBound = midValue - 1;
                smallestValueSeen = getSmallerValue(nums[midValue], smallestValueSeen);
            }
        }
        return smallestValueSeen;
    }

    // Returns the smaller value.
    private int getSmallerValue(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }
}

We then initialize maxBound & minBound, at the opposite ends of the array. Note that minBound = 1 as nums[0] is the value that nums[midValue] is being compared to.

For example, 1 is the POI for this array, [4,5,1,2,3].

For each iteration of the loop, we determine the midValue. This value is then compared to nums[0] & there are two outcomes:

• If nums[midValue] >= nums[0]: The POI lies in the forward direction, set minBound = midValue + 1.
• If nums[midValue] < nums[0]: The POI lies in the backward direction, set maxBound = midValue - 1.

smallestValueSeen is updated if necessary.

At the end of the Binary Search, smallestValueSeen is returned.