Skip to main content

Sorted Rotation Pivot Locator

easy
ArrayBinary SearchBinary Search Rotated
Asked atAmazonMicrosoftGoogleMeta

Problem Description

You are given a sorted array of distinct integers that has been rotated at some unknown pivot index. Your task is to find the index of the **minimum element** (the pivot point).

For example, the sorted array `[2, 4, 7, 10, 13]` rotated at index 3 becomes `[10, 13, 2, 4, 7]`. The minimum element is `2` at index `2`.

You must solve this in **O(log n)** time.

**Example 1:**
```
Input: rotated = [6, 9, 12, 1, 3]
Output: 3
Explanation: The minimum element is 1, located at index 3.
```

**Example 2:**
```
Input: rotated = [4, 5, 6, 7, 0, 1, 2]
Output: 4
Explanation: The minimum element is 0, located at index 4.
```

Constraints

  • 1 <= rotated.length <= 5000
  • All elements in rotated are distinct
  • -10^4 <= rotated[i] <= 10^4
  • rotated was originally sorted in ascending order before rotation

Follow-up

What if the array may contain duplicate values? How does that change the worst-case time complexity?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.