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
Hiring now
ServiceNow has 794 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Customer Success Executive
Remote
CRM Senior Solution Sales Executive
Brasilia, Brasilia, Brazil
CPQ Senior Solution Sales Executive
Sao Paulo, SAO PAULO, Brazil
Next question