6-lines C/C++/Python Solutions


  • 0

    As explained in the Solution tag, the key to solving this problem is to use invariants. We set two pointers: l for the left and r for the right. One key invariant is nums[l] > nums[r]. If this invariant does not hold, then we know the array has not been rotated and the minimum is just nums[l]. Otherwise, we reduce the search range by a half each time via comparisons between nums[l], nums[r] and nums[(l + r) / 2], denoted as nums[mid]:

    1. If nums[mid] > nums[r], then mid is in the first larger half and r is in the second smaller half. So the minimum will be right to mid, update l = mid + 1;
    2. If nums[mid] <= nums[r], then the minimum is at least nums[mid] and elements right to mid cannot be the minimum. So update r = mid (note that it is not mid - 1 since mid may also be the index of the minimum).

    When l == r or the invariant does not hold, we have found the answer, which is just nums[l].

    Putting these togerther, we have the following codes.


    C (0ms)

    int findMin(int* nums, int numsSize) {
        int l = 0, r = numsSize - 1;
        while (l < r && nums[l] > nums[r]) {
            int mid = (l & r) + ((l ^ r) >> 1);
            if (nums[mid] > nums[r]) l = mid + 1;
            else r = mid; 
        }
        return nums[l];
    }
    

    C++ (4ms)

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int l = 0, r = nums.size() - 1;
            while (l < r && nums[l] > nums[r]) {
                int mid = (l & r) + ((l ^ r) >> 1); 
                if (nums[mid] > nums[r]) l = mid + 1;
                else r = mid;
            }
            return nums[l];
        }
    };
    

    Python (48ms)

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def findMin(self, nums):
            l, r = 0, len(nums) - 1
            while l < r and nums[l] > nums[r]:
                mid = (l & r) + ((l ^ r) >> 1)
                if nums[mid] > nums[r]:
                    l = mid + 1
                else:
                    r = mid
            return nums[l]
    

    A final remark, I don't know why this algorithm gives almost best running time for C and C++ but just medium performance for Python.


  • 1

    I don't know why this algorithm gives almost best running time for C and C++ but just medium performance for Python.

    Fastest C time is 0ms and 90% of submissions reach it. How do you know you're not among the slowest of those? Same for C++ with 4ms.

    Maybe it's because you access nums so often. It's not necessary to check it in the while condition.

    Fastest recent Python time is btw 36ms, and I just managed to achieve that with this solution:

    class Solution:
        findMin = min
    

    First time I've seen (l & r) + ((l ^ r) >> 1) actually being used (I only know it from some article). Does it have an advantage over l + (r - l) / 2?


  • 0

    Wow, findMin = min is really... nom nom nom :-) I know nothing about such an implementation... I try to write as

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def findMin(self, nums):
            return min(nums) 
    

    And it takes 50 ms.

    For (l & r) + ((l ^ r) >> 1), I just learn it from the code of one of my seniors. And then I keep this golfing habit :-) Well, regarding its advantage, perhaps it involves less arithmetic operations and thus may be faster?

    BTW, Stefan, could you please give some hints of how to avoid accessing nums in the while condition? Thanks~


  • 0

    Yeah, I still don't fully know why findMin = min works, asked on StackOverflow but haven't taken the time to learn enough to understand it well.

    I think return min(nums) is about the same speed (except when calling tons of times with tiny inputs), the time difference is just the variance of the judge system.

    Heh, (l & r) + ((l ^ r) >> 1) is certainly no golfing habit. Maybe an anti-golfing habit :-). Or do you mean something other than code golf, which goes for shortest code?

    Here's my solution. My invariant is just that nums[lo:hi+1] contains the minimum.

    def findMin(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) / 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]
    

  • 0

    Haha, I just realized that our solutions are actually exactly the same except for your extra test. So the answer to your question of how to avoid that extra test is literaly "just remove it" :-P


  • 0

    Hi, Stefan. Well, I just misunderstand code golfing. I originally suppose that it refers to all the unusual habits of writing an easy code, like making it shortest or writing it in a very "strange" way.

    Well, your code is much concise. However, aftering removing the extra check in the while condition, the code takes more time, from 48ms to now 52ms...


  • 0

    Yeah, golfing does often get "strange" in order to be short :-)

    I just tried submitting yours a couple more times:

    • With the check: 52, 48, 56
    • Without the check: 40, 48, 36

    But three minutes later, this time the other way around:

    • Without the check: 56, 72, 44
    • With the check: 44, 44, 44

    Not exactly reliable...


Log in to reply
 

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