Why it works
- Finding one 3 is not enough: the answer is the edges of the block of 3s. So on a match the run writes the index down and keeps going, left in the first search and right in the second.
- In the first search everything left of lo is smaller than the target, and everything right of hi is the target or bigger. When lo passes hi, the last match written down is the leftmost one. The second search is its mirror.
- Stopping at a match and stepping outwards one by one would take O(n) on an array of nothing but 3s. Two searches take O(log n) whatever the block.
Complexity
Time O(log n): two binary searches, one after the other. Memory O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗