You are given a rotated sorted list of integers.
A sorted list is rotated when some prefix of the list is moved to the end while preserving the relative order of all elements.
For example, the sorted list [1, 2, 3, 4, 5, 6, 7] can become [4, 5, 6, 7, 1, 2, 3] after rotation.
Your task is to support searching and rotation analysis on this rotated sorted list.
The list may contain duplicate values.
Class
class RotatedSortedArraySearch
The class is initialized with a rotated sorted list of integers.
Constructor
RotatedSortedArraySearch(List<Integer> numbers)
numbers is the rotated sorted list.numbers may contain duplicate values.- The constructor stores the list for all future method calls.
Methods
Search Target
int searchTarget(int target)
- Returns the index of
target in the rotated sorted list.
- If
target appears multiple times, return the smallest index where it appears.
- If
target does not exist, return -1.
- The method must correctly handle lists with duplicate values.
Find Smallest Element
int findSmallestElement()
- Returns the smallest value in the rotated sorted list.
- If the list contains duplicates, the smallest value may appear more than once.
- If the list is empty, return
-1.
Count Rotations
int countRotations()
- Returns how many times the original sorted list was rotated.
- This is equal to the smallest index where the minimum value appears.
- If the list is already sorted and not rotated, return
0.
- If the list contains only duplicate values, return
0.
- If the list is empty, return
0.
Rotation Rules
A rotation count is defined as the index of the first occurrence of the smallest value.
For example:
[4, 5, 6, 7, 1, 2, 3] has rotation count 4.[2, 2, 2, 3, 4, 1, 2] has rotation count 5.[1, 1, 2, 2, 3] has rotation count 0.
Constraints
0 ≤ numbers.size() ≤ 100,000-1,000,000 ≤ numbers[i] ≤ 1,000,000-1,000,000 ≤ target ≤ 1,000,000
Examples
Example 1: Search in rotated sorted list without duplicates
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of(4, 5, 6, 7, 0, 1, 2));
rotatedSortedArraySearch.searchTarget(target = 0) returns 4
rotatedSortedArraySearch.findSmallestElement() returns 0
rotatedSortedArraySearch.countRotations() returns 4
The value 0 is present at index 4. The smallest value is 0, and the list was rotated 4 times.
Example 2: Target does not exist
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of(4, 5, 6, 7, 0, 1, 2));
rotatedSortedArraySearch.searchTarget(target = 3) returns -1
rotatedSortedArraySearch.findSmallestElement() returns 0
rotatedSortedArraySearch.countRotations() returns 4
The value 3 is not present in the list.
Example 3: Rotated sorted list with duplicates
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of(2, 5, 6, 0, 0, 1, 2));
rotatedSortedArraySearch.searchTarget(target = 0) returns 3
rotatedSortedArraySearch.findSmallestElement() returns 0
rotatedSortedArraySearch.countRotations() returns 3
The value 0 appears at indices 3 and 4, so the smallest index 3 is returned.
Example 4: Already sorted list
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of(1, 2, 3, 4, 5));
rotatedSortedArraySearch.searchTarget(target = 4) returns 3
rotatedSortedArraySearch.findSmallestElement() returns 1
rotatedSortedArraySearch.countRotations() returns 0
The list is already sorted, so the rotation count is 0.
Example 5: All values are same
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of(7, 7, 7, 7));
rotatedSortedArraySearch.searchTarget(target = 7) returns 0
rotatedSortedArraySearch.findSmallestElement() returns 7
rotatedSortedArraySearch.countRotations() returns 0
The target appears at every index, so the smallest index 0 is returned. Since all values are the same, the rotation count is 0.
Example 6: Empty list
RotatedSortedArraySearch rotatedSortedArraySearch = new RotatedSortedArraySearch(numbers = List.of());
rotatedSortedArraySearch.searchTarget(target = 10) returns -1
rotatedSortedArraySearch.findSmallestElement() returns -1
rotatedSortedArraySearch.countRotations() returns 0
The list is empty, so no target exists, no smallest element exists, and the rotation count is 0.