Implement rotated array binary search with duplicates
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array nums that is a non-decreasing array rotated an unknown number of times. Duplicates may exist. Implement a function that returns a pair: (rotation_count, leftmost_index_of_target) where rotation_count is the index of the rotation point and leftmost_index_of_target is the smallest index i such that nums[i] == target or -1 if absent.
Definitions and constraints:
- Rotation point is the smallest index r such that nums[r] < nums[(r-1+n)%n]. If no such r exists (array already sorted or all equal), rotation_count = 0.
- Time: O(log n) expected; discuss and handle worst-case O(n) when duplicates make direction ambiguous.
- Space: O(1).
- Edge cases: all elements equal; target duplicated across the rotation boundary; n=1; empty array.
- Example: nums = [4,5,5,6,6,1,2,3,3], target=3 → rotation_count=5, leftmost_index_of_target=7.
- Provide: (a) algorithm idea; (b) correctness argument; (c) complexity; (d) thorough unit tests covering edge cases.
Quick Answer: This question evaluates algorithm design and analysis skills, focusing on binary-search variants, handling duplicates in rotated non-decreasing arrays, rotation-index reasoning, and rigorous edge-case analysis; domain: Coding & Algorithms, specifically search algorithms and array manipulation.
Given an integer array `nums` that is a non-decreasing array rotated an unknown number of times (duplicates may exist), return a pair `(rotation_count, leftmost_index_of_target)`.
- `rotation_count` is the rotation point: the smallest index `r` such that `nums[r] < nums[(r-1+n)%n]`. If no such `r` exists (the array is already sorted or all elements are equal), `rotation_count = 0`. This equals the index of the minimum element (the wrap point).
- `leftmost_index_of_target` is the smallest index `i` such that `nums[i] == target`, or `-1` if `target` is absent.
Return the answer as a two-element pair/array `[rotation_count, leftmost_index_of_target]`.
Algorithm idea: The wrap point is the unique 'drop' where a later element is smaller than the element before it; a modified binary search on `nums` locates it in O(log n) expected time, falling back to a linear scan in the worst case when duplicates make the comparison `nums[mid] == nums[hi]` ambiguous (you must then shrink the window by one, giving O(n) worst case — e.g. `[2,2,2,0,2]`). The leftmost occurrence of `target` can be found with a leftmost-binary-search within the appropriate rotated half, again degrading to O(n) with heavy duplicates.
Example: `nums = [4,5,5,6,6,1,2,3,3]`, `target = 3` → `rotation_count = 5`, `leftmost_index_of_target = 7`.
Constraints
- 0 <= n <= 10^5
- Duplicates may exist in nums
- nums is a non-decreasing array rotated an unknown number of times
- If the array is already sorted or all elements are equal, rotation_count = 0
- Return -1 for leftmost_index_of_target when target is absent
- Target space complexity O(1)
Examples
Input: ([4,5,5,6,6,1,2,3,3], 3)
Expected Output: (5, 7)
Explanation: Drop occurs at index 5 (1 < 6), so rotation_count=5. Threes are at indices 7 and 8; leftmost is 7.
Input: ([1,2,3,4,5], 3)
Expected Output: (0, 2)
Explanation: Already sorted, no drop, so rotation_count=0. Target 3 is at index 2.
Hints
- The rotation point is the unique index where a value drops below its predecessor (cyclically). It is the index of the minimum element. If there is no drop, the array is sorted and rotation_count = 0.
- With duplicates, a binary search can hit nums[mid] == nums[hi], making it impossible to tell which half holds the wrap point — shrink the window by one (hi -= 1) and continue. This is what forces O(n) worst case.
- For the leftmost occurrence of target, do not stop at the first match found by binary search; keep searching to the left (continue toward lower indices) until you find the smallest matching index.