DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 153. Find Minimum in Rotated Sorted Array (javascript solution)

Description:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,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 of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Solution:

Time Complexity : O(log(n))
Space Complexity: O(1)

// Binary Search 
var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    while(left < right) {
        const mid = left + Math.floor((right-left)/2)
        // Move right pointer if num at mid is less than or equal to num at right. This means that the smallest number must be on the left side of mid including mid.
        if(nums[right] >= nums[mid]) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return nums[left]
};
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
qurashieman profile image
Tuba Inam

I found that solution is very popular and helpful: youtu.be/Eww5UFfjxsc