Java Interview Question - Find Minimum Version in Rotated Release History
When math keeps cutting things in half until it gets bored
Context
You are working at a large SaaS company that maintains deployment versions across distributed regions.
Due to a global rollout strategy, version IDs are stored in a sorted order:
[1001, 1002, 1003, 1004, 1005, 1006]However, due to a regional failover + replication lag, the array gets rotated at an unknown point before being sent to downstream services.
A monitoring service receives this rotated version list:
[1004, 1005, 1006, 1001, 1002, 1003]Each number represents a release version timestamp (or build ID).
The system needs to find the oldest deployed version (minimum version) quickly.
📢 Get actionable Java and Spring Boot insights every week, including practical code tips and real-world, use-case-based interview questions, to help you level up your backend skills—join 7300+ subscribers for hand-crafted, no-fluff content.
First 100 paid subscribers will get the annual membership at $50/year forever that is ~ $4/mo ( 89 already converted to paid, 11 sport remaining)
Testimonials
Whats the easiest approach come to your mind?
A naive approach would be to scan the each element in the array and maintain the min among all the elements.
Time Complexity: O(n)
Do you think we can utilize partial sorted property to our advantage?
yes we can use partial sorted information to find the pivot point because at the pivot point
nums[i] < nums[i - 1]at that point we can early return which save us to traverse whole array
Time Complexity: O(n)
time complexity is still O(n) because in worst case our pivot point can be at the last position.
Can we use some other technique here to optimize time?
One another idea is to use binary search, but binary search works very well on fully sorted data, we will have to tweak it little bit to work on our roated /sorted array.
Basic logic is:
If nums[mid] > nums[right] , then we know min would definitely lies between [nums[mid] … nums[right]], hence we should search on right side.
otherwise min lies between [nums[0]…nums[mid]], hence we should search on left side.
Time Complexity: O(log N), why? because at each stage we divide the array in half and find relevant subarray , which we keep shorten on every iteration.
n/2, n/4, n/8….
after k steps, n/2^k.
once we find the element, n/2^k = 1.
2^k = n
k = log2(n)Final complexity: O(log n)
Thats all for this question! Thanks for reading this far. If you liked it please share with your network.
Happy Coding 🚀
Suraj
Subscribe | Sponsor us | LinkedIn | Twitter