Simple Java solution, using recursion and binary search


  • 0
    W

    We basically do binary search, and we find our min element when start == end.

    If A[mid] > A[end], that means the pivot point (or the min element) is on right side. So we go right, else we go left.

    But since we could have duplicates, if all three positions start, mid and end have same numbers, we could not decide which side will have the pivot. So, we increment start (or equivalently decrement end) and search again.

    For worst case, such as the array with all the elements same, this could take a linear time i.e. O(n). For other general cases, where we could have some duplicate elements here and there, it essentially takes logarithmic time O(lgn). The same logic applies if have no duplicates, in which case we won't be needing the first check for equality of start, mid and end, though it won't harm keeping the check!

    public class Solution {
        public int findMin(int[] nums) {
            return findMinWithDup(nums, 0, nums.length - 1);
        }
        
        int findMinWithDup(int[] nums, int start, int end) {
            if(start == end)
                return nums[start];
            int mid = (start + end) / 2;
            if(nums[start] == nums[mid] && nums[mid] == nums[end])
                return findMinWithDup(nums, start + 1, end);
            if(nums[mid] > nums[end])   // so left side is sorted array, but pivot point is right side.. so go right
                return findMinWithDup(nums, mid + 1, end);
            return findMinWithDup(nums, start, mid);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.