Count elements less than or equal to k in a sorted rotated array

JavaView on GFG

Intuition

Count elements <= k in sorted rotated array. Binary search to handle rotation.

Algorithm

1Find rotation pivot. Two binary searches on two sorted halves. Count elements <= k in each half.

Common Pitfalls

•Sorted rotated array splits into two sorted runs. Apply upper_bound on each half and sum counts.

Count elements less than or equal to k in a sorted rotated array.java

Java

// Approach: Binary search to find the position where elements become > k.
// Time: O(log n) Space: O(1)
class Solution {
    public int countLessEqual(int[] arr, int x) {
        int pivot = getPivot(arr);
        int leftSide = getLessEqual(arr, x, 0, pivot - 1);
        int rightSide = getLessEqual(arr, x, pivot, arr.length - 1);

        return leftSide + rightSide;
    }

    private int getLessEqual(int[] arr, int x, int l, int r) {
        int origL = l;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > x)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return l - origL;
    }

    private int getPivot(int[] arr) {
        int l = 0, r = arr.length - 1;

        while (l < r) {
            int mid = l + (r - l) / 2;

            // If mid element is greater than the
            // rightmost element,
            // pivot must be in the right half
            if (arr[mid] > arr[r])
                l = mid + 1;
            else // Otherwise, pivot is in left half (including mid)
                r = mid;
        }

        return l; // l will point to the minimum element
    }
}

Was this solution helpful?