Detecting Price Floor in Fluctuating Market — Problem Statement & Solution Guide
Problem Description
Given an integer array nums that was originally sorted in strictly increasing order and then rotated at an unknown index, locate and return the smallest value. The rotation moves a suffix of the original sorted array to the front while preserving internal order. Your algorithm must run in O(log n) time and O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Detecting Price Floor in Fluctuating Market"
WHY DOES IT MATTER?
This pattern is essential because it demonstrates how to apply binary search to non-standard sorted structures. It teaches the critical skill of identifying local invariants in globally disordered data, a skill frequently tested in interviews for roles involving search, optimization, and data integrity.
OPTIMIZATION CHALLENGE
The key insight is recognizing that while the entire array is not sorted, one of the two halves created by the midpoint is always sorted. By comparing the midpoint with the right boundary, we can determine which half is sorted and which half contains the rotation point (and thus the minimum).
REAL-WORLD CONNECTION
This is analogous to finding the minimum timestamp in a circular log buffer or identifying the start of a sequence in a ring buffer used in high-throughput network packet processing. In distributed systems, it resembles finding the leader in a ring of nodes where the 'sorted' order is logical but the physical arrangement is rotated.
During the interview, explicitly state the invariant: 'At least one half is sorted.' Then, explain why comparing with the right end is safer than the left end. This shows deep understanding of edge cases and prevents the common mistake of infinite loops or incorrect discarding of the minimum.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The problem of finding the minimum in a rotated sorted array is a classic application of binary search, but with a modified comparison logic. In a standard sorted array, binary search relies on the invariant that the middle element is either the target or splits the array into two halves where one half is entirely smaller and the other entirely larger. In a rotated array, this global monotonicity is broken at the rotation point. However, a crucial property remains: at any step, at least one half of the current search space (left or right of the midpoint) is strictly sorted. This local monotonicity allows us to determine which half contains the minimum by comparing the midpoint value with the rightmost element of the current window.
Interview Questions on This Problem
Q1How would you adapt this algorithm if the array contained duplicate values, and how does that affect the time complexity?
With duplicates, the comparison between the midpoint and the rightmost element becomes ambiguous when they are equal. In that case, we cannot definitively discard a half, so we must shrink the search space by one step (e.g., high = high - 1). This degrades the worst-case time complexity from O(log n) to O(n) in scenarios where all elements are identical, though the average case remains O(log n).
Q2Why do we compare the midpoint with the rightmost element (nums[high]) instead of the leftmost element (nums[low])?
Comparing with the rightmost element allows us to correctly identify the sorted half even when the rotation point is in the left half. If we compared with the leftmost element, we might incorrectly discard the half containing the minimum when the rotation point lies between the low and mid indices. Comparing with the right end ensures that if nums[mid] > nums[high], the minimum must be in the right half, and if nums[mid] < nums[high], the minimum is in the left half (including mid).
Q3Can this approach be generalized to find the rotation index (the pivot point) rather than just the minimum value?
Yes. The minimum value in a rotated sorted array is always located at the pivot index (the point where the rotation occurred). Therefore, the index of the minimum value is the rotation index. The same binary search logic applies; we simply return the index where the minimum is found instead of the value itself.
Examples
Input
[7,9,2,4,5]
Output
2
Explanation: The original sorted order would be [2,4,5,7,9]; after rotation the array becomes [7,9,2,4,5]. The first position where an element is smaller than its predecessor is at index 2 (value 2), which is the minimum.
Input
[3,4,5,1,2]
Output
1
Explanation: Rotation moved the tail [1,2] to the front of the sorted sequence [1,2,3,4,5]. The element at index 3 (value 1) is the first that breaks the increasing trend and is the global minimum.
Input
[10]
Output
10
Explanation: A single‑element array is trivially sorted and rotated; the only element is the minimum.
Constraints
- 1 <= nums.length <= 200000
- -1000000000 <= nums[i] <= 1000000000
- All elements are distinct
- nums was sorted in strictly increasing order before a single rotation
Optimal Approach & Strategy
Use binary search to compare the middle element with the rightmost element of the current search window. If the middle element is greater than the rightmost, the minimum is in the right half; otherwise, it is in the left half. This reduces the search space by half each iteration, achieving O(log n) time complexity.
Brute Force Approach
Iterate through the entire array and keep track of the minimum value encountered. This approach is simple but inefficient, taking O(n) time complexity, which is suboptimal for large datasets.
Verified Code Solutions
function findMin(nums) {
if(nums.length===0) return 0;
let left = 0, right = nums.length - 1;
while(left < right) {
const mid = left + Math.floor((right - left) / 2);
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
const n = input[0];
const arr = input.slice(1,1+n);
console.log(findMin(arr));
}#include <bits/stdc++.h>
using namespace std;
int findMin(const vector<int>& nums) {
if(nums.empty()) return 0;
int left = 0, right = (int)nums.size() - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n; if(!(cin>>n)) return 0;vector<int> a(n);for(int i=0;i<n;++i)cin>>a[i];cout<<findMin(a);return 0;}import java.io.*;
import java.util.*;
public class Main {
public static int findMin(int[] nums) {
if(nums.length==0) return 0;
int left = 0, right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) {
while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
nums[i] = Integer.parseInt(st.nextToken());
}
System.out.print(findMin(nums));
}
}import sys
def find_min(nums):
if not nums:
return 0
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(find_min(nums))
if __name__ == "__main__":
main()function findMin(nums) {
if(nums.length===0) return 0;
let left = 0, right = nums.length - 1;
while(left < right) {
const mid = left + Math.floor((right - left) / 2);
if(nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length){
const n = input[0];
const arr = input.slice(1,1+n);
console.log(findMin(arr));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.