Problem

Find the minimum element in the rotated sorted array.

For example, the array a = [0, 1, 2, 4, 6, 8, 10] might become:

  • [8, 10, 0, 1, 2, 4, 6] if it was rotated 2 times.
  • [4, 6, 8, 10, 0, 1, 2] if it was rotated 4 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]].

Example

Example 1:

Input: nums = [5, 7, 9, 1, 3]
Output: 1
Explanation: The original array was [1, 3, 5, 7, 9] rotated 3 times.

Example 2:

Input: nums = [4, 6, 8, 10, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 6, 8, 10] and it was rotated 4 times.

Example 3:

Input: nums = [5, 10, 15, 20]
Output: 5
Explanation: The original array was [15, 10, 15, 20] and it was rotated 4 times.

Solution

The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

If we pick the middle element, we can compare the middle element with the leftmost (or rightmost) element. If the middle element is less than leftmost, the left half should be selected; if the middle element is greater than the leftmost (or rightmost), the right half should be selected. Using recursion or iteration, this problem can be solved in time log(n).

Method 1 - Recursion

Define a helper function, otherwise, we will need to use Arrays.copyOfRange() function, which may be expensive for large arrays.

class Solution {

	public int findMin(int[] nums) {
		return findMin(nums, 0, nums.length - 1);
	}

	private int findMin(int[] num, int left, int right) {
		if (left == right) {
			return num[left];
		}

		if ((right - left) == 1) {
			return Math.min(num[left], num[right]);
		}

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

		// sorted array now - so not rotated
		if (num[left]<num[right]) {
			return num[left];

			// go right side
		} else if (num[middle] > num[left]) {
			return findMin(num, middle, right);

			// go left side
		} else {
			return findMin(num, left, middle);
		}
	}
}

Complexity

  • ⏰ Time complexity: O(log n)
  • 🧺 Space complexity: O(1)

Method 2 - Iterative Solution

Code

Java
class Solution {
	/*
	To understand the boundaries, use the following 3 examples:
	[2,1], [2,3,1], [3,1,2]
	*/

	public int findMin(int[] nums) {
		if (nums == null || nums.length == 0) {
			return -1;
		}

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

		while (left <= right) {
			if (nums[left] <= nums[right]) {
				return nums[left];
			}

			int mid = (left + right) / 2;

			if (nums[mid] >= nums[left]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return -1;
	}
}

Making above code smaller:

class Solution {

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

		while (left < right && nums[left] > nums[right]) {
			int mid = left + (right - left) / 2;

			if (nums[mid] > nums[end]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return nums[left];
	}
}