[leetcode #154] Find Minimum in Rotated Sorted Array II

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,4,4,5,6,7] might become:

・ [4,5,6,7,0,1,4] if it was rotated 4 times.
・ [0,1,4,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 that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

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

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

・ n == nums.length
・ 1 <= n <= 5000
・ -5000 <= nums[i] <= 5000
・ nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

Idea

153번 문제인 Find Minimum in Rotated Sorted Array와 상당히 유사하다. 이 문제가 Hard로 된 건 array를 구성하는 수들이 unique하지 않을 수 있다는 것 때문이다.

마찬가지로 Binary Search를 이용해서 풀면 되는데, binary search 도중 크기가 역전되는 index (경계)를 찾지 못 했을 때 처리하는 것이 관건이다. Array를 구성하는 수들이 전부 동일할 경우 153번과 같은 방식으로 문제를 풀 수 없다. 그래서 재귀함수에서 경계를 끝까지 찾지 못 하고 하나의 수만 남는 경우 해당 수를 리턴하도록 했다. 그리고 재귀함수에서 왼쪽과 오른쪽으로 나눈 뒤 해당 함수가 리턴하는 값들 중 더 작은 값을 리턴하게 했다. 물론 연산하는 도중 경계값을 찾으면 곧바로 리턴하도록 한다.

대부분의 풀이도 시간이 0ms로 그렇게 오래 걸리지 않겠지만, 이번 풀이는 메모리를 아주 작게 사용해서 놀랐다!

Solution

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

    private int findBorder(int[] nums, int startIndex, int endIndex) {
        int midIndex = startIndex + (endIndex - startIndex) / 2;
    
        if (nums[endIndex] > nums[startIndex] || startIndex == endIndex)
            return nums[startIndex];
    
        if (nums[midIndex] > nums[midIndex+1])
            return nums[midIndex+1];
    
        if (midIndex-1 >= 0 && nums[midIndex-1] > nums[midIndex])
            return nums[midIndex];
    
        int left = findBorder(nums, startIndex, midIndex-1 < startIndex ? startIndex : midIndex-1);
        int right = findBorder(nums, midIndex+1, endIndex);
    
        return Math.min(left, right);
    }
}

Reference

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/