Find minimum in Rotated Sorted Array
Goldman Sachs
ServiceNowThe problem
Given an integer array nums of size N, sorted in ascending order with distinct values, and then rotated an unknown number of times (between 1 and N), find the minimum element in the array.
Input : nums = [4, 5, 6, 7, 0, 1, 2, 3] Output: 0 Explanation: Here, the element 0 is the minimum element in the array.
Input : nums = [3, 4, 5, 1, 2] Output: 1 Explanation:Here, the element 1 is the minimum element in the array.
Input : nums = [4, 5, 6, 7, -7, 1, 2, 3]
- n == nums.length
- 1 <= n <= 104
- -104 <= nums[i] <= 104
- All the integers of nums are unique.
- nums is sorted and rotated between 1 and n times.
cpp
class Solution {
public:
int findMin(vector<int> &arr) {
}
};java
class Solution {
public int findMin(ArrayList<Integer> arr) {
}
}python
class Solution:
def findMin(self, arr):javascript
class Solution {
findMin(arr) {
}
}csharp
public class Solution {
public int findMin(int[] arr) {
// Write your logic here
}
}go
func findMin(arr []int) int {
}Stuck? Show a way to structure it+
- 01Set low and high to the array ends.
- 02If the interval is already sorted, return its first value.
- 03Compare the middle value with the high value.
- 04Move low right of middle when middle belongs to the left sorted run.
- 05Otherwise keep middle as the minimum candidate.
Reference answer
Then expect these follow-ups
How would you support duplicate values?
Tests: follow-up reasoning
How do you return the pivot index instead of its value?
Tests: implementation extension
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question