Problem

In a Google Photos mobile client, event timestamps may arrive unsorted after local batching. Given an integer array timestamps and an integer target, return the index of the first occurrence of target after sorting the array in non-decreasing order. If target does not exist, return -1.

Formal Specification

• Input: timestamps is a list of integers. target is an integer.
• Output: Return an integer representing the leftmost index of target in the sorted version of timestamps, or -1 if not found.

Examples

Example 1

• Input: timestamps = [8, 3, 5, 3, 10], target = 3
• Output: 0
• Explanation: After sorting, the array becomes [3, 3, 5, 8, 10]. The first 3 is at index 0.

Example 2

• Input: timestamps = [12, 7, 9, 1], target = 8
• Output: -1
• Explanation: After sorting, the array becomes [1, 7, 9, 12]. The value 8 is not present.

Constraints

• 1 <= len(timestamps) <= 10^5
• -10^9 <= timestamps[i] <= 10^9
• -10^9 <= target <= 10^9
• You should solve the search step in O(log n) after sorting.