LeetCode Problems

In this tutorial we will solve 153. Find Minimum in Rotated Sorted Array from leetcode.

Reference: 153. Find Minimum in Rotated Sorted Array

In this problem statement we are asked to find the minimum value in a sorted array `nums`

of length `n`

. The array is sorted in ascending order. We are also told that the input array can be rotated 1 to `n`

times.

For example if the input array is `[1,2,3,4,5]`

and we rotate 1 time then the new array will be [5,1,2,3,4].

Similarly, if the input array is rotated 3 times then the new array will be [3,4,5,1,2].

Watch this video for Binary Search.

Example from leetcode.

```
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
```

```
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
```

To solve this problem we will use Binary Search. We will start by pointing the `start`

pointer to the 0th index and the `end`

pointer to the last index of the array. Then we will loop as long as the `start`

is less than or equal to the `end`

. In each iteration we will find the middle index `mid`

and check if the middle element is less than the end element. If it is then we will set the `end`

to the `mid`

index. Else, we will move the `start`

index to `mid + 1`

. After the loop ends we will have the minimum value at index `start - 1`

.

Let us look at the first input [3,4,5,1,2].

```
n = 5
start = 0
end = 4
mid = floor((start + end) / 2)
= floor((0+4)/2)
= 2
index = 0 1 2 3 4
nums = [3, 4, 5, 1, 2]
^ ^ ^
s m e
is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 5 < 2 ? NO
so, we move start
start = mid + 1
= 2 + 1
= 3
end = 4
mid = floor((start + end) / 2)
= floor((3+4)/2)
= 3
index = 0 1 2 3 4
nums = [3, 4, 5, 1, 2]
^ ^
s e
m
is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 1 < 2 ? YES
so, we move end
start = 3
end = mid
= 3
mid = floor((start + end) / 2)
= floor((3+3)/2)
= 3
index = 0 1 2 3 4
nums = [3, 4, 5, 1, 2]
^
s
e
m
is start <= end ? YES
is nums[m] < nums[e] ?
i.e., 1 < 1 ? NO
so, we move start
start = mid + 1
= 3 + 1
= 4
end = 3
now start is greater than end so we stop here.
minimum value is at index = start - 1
= 4 - 1
= 3
i.e., nums[3] = 1
```

JavaScript

```
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
let start = 0;
let end = nums.length - 1;
while (start <= end) {
const mid = Math.floor((start+end)/2);
if (nums[mid] < nums[end]) {
end = mid;
} else {
start = mid + 1;
}
}
return nums[start-1];
};
```

**Time complexity: O(n)**

Binary Search is used here so the time complexity is O(logn).

**Space complexity: O(n)**

We are only using constant space so space complexity will be O(1).

ADVERTISEMENT