Difficulty | Source | Tags | |
---|---|---|---|
Easy |
160 Days of Problem Solving |
|
The problem can be found at the following link: Problem Link
You are given a sorted array arr[]
which has been rotated at an unknown pivot. The array may contain duplicate elements. Your task is to find the minimum element in the array.
Input:
arr[] = [5, 6, 1, 2, 3, 4]
Output:
1
Explanation:
The minimum element is 1
.
Input:
arr[] = [3, 2, 2, 2]
Output:
2
Explanation:
The minimum element is 2
.
Input:
arr[] = [4, 4, 4]
Output:
4
Explanation:
The minimum element is 4
.
$1 ≤ arr.size() ≤ 10^6$ $1 ≤ arr[i] ≤ 10^9$
-
Binary Search in a Rotated Array:
- To find the minimum element in a rotated sorted array, we leverage binary search to reduce the search space efficiently.
- Use two pointers,
lo
andhi
, to represent the current range. Compare the middle element with the last element to determine the rotation point.
-
Handling Duplicates:
- When duplicates are present, special handling is required to ensure correctness. In such cases, we adjust the
hi
pointer ifarr[mid]
equalsarr[hi]
.
- When duplicates are present, special handling is required to ensure correctness. In such cases, we adjust the
-
Steps:
- Initialize two pointers,
lo
andhi
, to the start and end of the array. - If
arr[lo] < arr[hi]
, the array is not rotated, andarr[lo]
is the minimum. - Compute the middle index
mid
. - Compare
arr[mid]
witharr[hi]
:- If
arr[mid] > arr[hi]
, the minimum is in the right half (lo = mid + 1
). - If
arr[mid] < arr[hi]
, the minimum is in the left half (hi = mid
). - If
arr[mid] == arr[hi]
, decrementhi
to handle duplicates.
- If
- Return
arr[lo]
as the minimum element.
- Initialize two pointers,
- Expected Time Complexity: O(log n), as we reduce the search space by half in each iteration. In the case of duplicates, the complexity degrades to O(n).
- Expected Auxiliary Space Complexity: O(1), as we use only a constant amount of additional space.
int findMin(int* arr, int n) {
int lo = 0, hi = n - 1;
while (lo < hi) {
if (arr[lo] < arr[hi])
return arr[lo];
int mid = lo + ((hi - lo) >> 1);
if (arr[mid] > arr[hi])
lo = mid + 1;
else
hi = mid;
}
return arr[lo];
}
class Solution {
public:
int findMin(vector<int>& arr) {
int lo = 0, hi = arr.size() - 1;
while (lo < hi) {
if (arr[lo] < arr[hi])
return arr[lo];
int mid = lo + ((hi - lo) >> 1);
if (arr[mid] > arr[hi])
lo = mid + 1;
else
hi = mid;
}
return arr[lo];
}
};
class Solution {
public int findMin(int[] arr) {
int lo = 0, hi = arr.length - 1;
while (lo < hi) {
if (arr[lo] < arr[hi])
return arr[lo];
int mid = lo + ((hi - lo) >> 1);
if (arr[mid] > arr[hi])
lo = mid + 1;
else
hi = mid;
}
return arr[lo];
}
}
class Solution:
def findMin(self, arr):
lo, hi = 0, len(arr) - 1
while lo < hi:
if arr[lo] < arr[hi]:
return arr[lo]
mid = lo + ((hi - lo) // 2)
if arr[mid] > arr[hi]:
lo = mid + 1
else:
hi = mid
return arr[lo]
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐