Discussion : the best possible solution has O(n) worst case running time.


  • 0
    S

    I see that some people are trying to find an O(log n) solution to the above problem , but let me show you why it is not possible.

    In the case when the first element , the last element and the middle element are equal, you cannot claim anything about the minimum. It may lie in (first, mid) or(mid, last)

    In some inputs it will always be the case.

    eg take input: 12111111111111111111111111111
    or 21222222222222222222222222222
    or 111111111111111111111111111111

    In this case you have to search for minimum in both (first, mid) and (mid, last) . So the running time is
    T(N) = 2T(N/2) +O(1)

    which gives O(N) runnig time.

    Does this mean it is better to use the naive method and simply iterate over the array from start to end?
    NO , because in that case the running time is O(n) even in the best case .

    Here's my code for the problem which gives the best possible running time.

    class Solution {
    public:
        int findmin(vector<int>& nums, int i , int j)
        {
            if(i>=j) return nums[i];
            if(j-i==1 && nums[i]==nums[j]) return nums[i];
            int mid= i+ (j-i) / 2 ;
            if(nums[mid]==nums[j])
            {
                if(nums[i]!=nums[mid])return findmin(nums, i , mid );
                else return min(findmin(nums, mid+1 , j ), findmin(nums, i+1 , mid-1 ) );
            }
            if(nums[mid]>nums[j]) return findmin(nums, mid+1 , j );
            if(nums[mid]<nums[j]) return findmin(nums, i , mid );
            
        }
        int findMin(vector<int>& nums) {
            int n= nums.size();
            if(n==0) return 0;
            return findmin(nums, 0 , n-1);
        }
    
    };

Log in to reply
 

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