We are given a sorted rotated array containing distinct non-negative integers and a number x. The task is to count all elements that are less than or equal to x.
A rotated array is an array that was originally sorted in ascending order and then rotated at some pivot.
Example
Original Array
[1, 3, 4, 5, 8]
Rotated Array
[4, 5, 8, 1, 3]
Problem Understanding
Input
arr = [4, 5, 8, 1, 3]
x = 6
Elements ≤ 6
1, 3, 4, 5
Count
4
Naive Approach
We can scan the array and count the elements that satisfy the condition.
count = 0
for i = 0 to n - 1:
if arr[i] <= x:
count++
Time Complexity
O(n)
However, the array is sorted before rotation, so we can do better using binary search.
Efficient Approach (O(log n))
Key Idea
A rotated sorted array consists of two sorted subarrays.
For example:
[4, 5, 8] and [1, 3]
If we can find the pivot (the index of the smallest element), we can split the array into two sorted ranges.
Then we can perform binary search in both ranges to count elements less than or equal to x.
Step 1: Find the Pivot
The pivot is the index of the smallest element.
Cases
If the array is not rotated, pivot = 0.
Otherwise, the pivot separates the two sorted segments.
Binary Search for Pivot
low = 0
high = n - 1
while low < high:
mid = low + (high - low) / 2
if arr[mid] > arr[high]:
low = mid + 1
else:
high = mid
pivot = low
Complexity
O(log n)
Step 2: Binary Search in Both Sorted Segments
After finding the pivot:
Count elements less than or equal to x in both segments separately.
Binary Search for Counting Elements ≤ x
function countLessEqualSorted(arr, low, high, x):
ans = -1
while low <= high:
mid = low + (high - low) / 2
if arr[mid] <= x:
ans = mid
low = mid + 1
else:
high = mid - 1
return ans - startIndex + 1
Observation
ans - startIndex + 1
Java Implementation
class Solution {
public int countLessEqual(int[] arr, int x) {
int n = arr.length;
int pivot = findPivot(arr);
// Count in first part
int count1 = 0;
if (pivot < n) {
int idx = countLessEqualSorted(arr, pivot, n - 1, x);
if (idx != -1)
count1 = idx - pivot + 1;
}
// Count in second part
int count2 = 0;
if (pivot > 0) {
int idx = countLessEqualSorted(arr, 0, pivot - 1, x);
if (idx != -1)
count2 = idx + 1;
}
return count1 + count2;
}
private int findPivot(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high])
low = mid + 1;
else
high = mid;
}
return low;
}
private int countLessEqualSorted(int[] arr, int low, int high, int x) {
int ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] <= x) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
}
Example Dry Run
Input
arr = [4, 5, 8, 1, 3]
x = 6
Step 1: Find Pivot
pivot = 3
arr[3] = 1
Step 2: Process Left Segment
Segment:
[1, 3]
Count of elements ≤ 6:
2
Step 3: Process Right Segment
Segment:
[4, 5, 8]
Count of elements ≤ 6:
2
Total Count
2 + 2 = 4
Complexity Analysis
Time Complexity
Overall:
O(log n)
Space Complexity
O(1)
Only constant extra space is used.
Why This Works
A rotated sorted array can always be viewed as two independently sorted arrays separated by the pivot.
Once the pivot is known:
Each segment remains sorted.
Binary search can efficiently determine how many elements are less than or equal to x.
The counts from both segments can be added together to obtain the final answer.
Key Insight
A rotated sorted array should not be treated as a completely unsorted array. By identifying the pivot, the array can be split into two sorted portions, allowing binary search to be applied efficiently. This reduces the complexity from O(n) to O(log n) and makes the solution suitable for large inputs.
Summary
To count elements less than or equal to x in a sorted rotated array, first locate the pivot using binary search. The pivot divides the array into two sorted segments. Perform binary search on each segment to find how many elements are less than or equal to x, then add the results. This approach achieves O(log n) time complexity with O(1) extra space.