LeetCode #153 Find Minimum in Rotated Sorted Array Solution & Explanation

LeetCode Problem

LeetCode #153 Problem
LeetCode #153 Examples
LeetCode #153 Constraints

Solution

C# Solution

⚠️First try – Easy iteration Time Complexity Problem

public class Solution {
    public int FindMin(int[] nums) {
        int min = nums[0];
        foreach(var a in nums)
        {
            if(a<min)
            {
                min = a;
            }
        }
        return min;
    }
}

In this solution, we need to iterate all the array, and the time complexity will be O(n).

But in this problem, it should be O(log n), so this is not our final answer.

Time Complexity : O(n)

Solution1 – binary search Binary search algorithm – Wikipedia

public class Solution {
    public int FindMin(int[] nums) {
        int li = 0;             //low index
        int hi = nums.Length-1; //high index
      
        while(hi>li)
        {
            int midi = li+(hi-li)/2;
            
            if (nums[midi] < nums[hi]) 
            {
                hi = midi;
            } 
            else 
            {
                li = midi+1;
            }
        }
        
        return nums[li];
    }
}

In this solution, we will search the answer from every remaining half after iteration (1/2 ➡ 1/4 ➡ 1/8 … etc )

Time Complexity : O(log n)

⚠️Another try – Linq – Enumerable.Min

public class Solution {
    public int FindMin(int[] nums) {
        return nums.Min();
    }
}

One line code, so clear and simple.

But what about it’s time complexity? I can’t found the answer on Google…

I can't find it anywhere ( Google is my whole world ❤️)

Maybe we can find something on the official document? ( *1 )

Fine.. That is not the answer I want.

Suddenly, an idea came to me. Official source code !! ( *2 )

Linq - Enumerable.Min Official  source code

Oh! Just an easy iteration, so it’s time complexity will be O(n).

Time Complexity : O(n)

Java Solution

Solution1

class Solution {
    public int findMin(int[] nums) {
        int li = 0;             //low index
        int hi = nums.length-1; //high index
      
        while(hi>li)
        {
            int midi = li+(hi-li)/2;
            
            if (nums[midi] < nums[hi]) {
                hi = midi;
            } else {
                li = midi+1;
            }
        }
        
        return nums[li]; 
    }
}

Time Complexity : O(log n)

Python3 Solution

Solution1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        li = 0             #low index
        hi = len(nums)-1   #high index
      
        while(hi>li):
            midi = int(li+(hi-li)/2)
            
            if (nums[midi] < nums[hi]):
                hi = midi
            else:
                li = midi+1
     
        return nums[li]

Time Complexity : O(log n)

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    var li = 0;             //low index
    var hi = nums.length-1; //high index

    while(hi>li)
    {
        var midi = parseInt(li+(hi-li)/2,10);

        if (nums[midi] < nums[hi]) 
        {
            hi = midi;
        } 
        else 
        {
            li = midi+1;
        }
    }
    return nums[li]; 
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : Find Minimum in Rotated Sorted Array – LeetCode

Reference

Latest Post

Leave a Reply

Your email address will not be published. Required fields are marked *