Count Elements Less Than or Equal to x in a Sorted Rotated Array

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

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:

Left Segment: arr[pivot ... n - 1]
Right Segment: arr[0 ... pivot - 1]

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 stores the last index where arr[mid] ≤ x.
Number of valid elements:

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:

Step 3: Process Right Segment

Segment:

[4, 5, 8]

Count of elements ≤ 6:

Total Count

2 + 2 = 4

Complexity Analysis

Time Complexity

Find Pivot: O(log n)
Binary Search in First Segment: O(log n)
Binary Search in Second Segment: O(log n)

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.