BudiBadu Logo

Count of Elements Less Than Target

Sorting Easy 33 views
Like29

You’re given a list of integers sorted in ascending order and a target value. In Count of Elements Less Than Target, your task is to determine exactly how many numbers are strictly smaller than that target. You aren't finding a position; you're returning a count of the values that sit below the line on the number line.

The "secret sauce" here is taking advantage of the Sorted Order. While you could count one by one (O(N)), using Binary Search allows you to find the first index that hits or exceeds the target in O(log N) time! That index then tells you exactly how many elements came before it. If the target is smaller than the first element, the count is zero; if it's larger than the last, the count equals the list length. Duplicates that are less than the target should be included in your tally. This is the absolute gold standard for efficient range-based queries in large, professional datasets!

Examples

Example 1
Input
nums = [], target = 10
Output
0
Explanation

The list is empty, so the count is 0.

Example 2
Input
nums = [1, 2, 4, 4, 7], target = 4
Output
2
Explanation

Only 1 and 2 are strictly less than 4, so the count is 2.

Example 3
Input
nums = [3, 3, 3], target = 3
Output
0
Explanation

No element is strictly smaller than 3.

Algorithm Flow

Recommendation Algorithm Flow for Count of Elements Less Than Target - Budibadu
Recommendation Algorithm Flow for Count of Elements Less Than Target - Budibadu

Best Answers

java
import java.util.List;
class Solution {
    public int count_less_than(Object nums, Object target) {
        int t = (int) target;
        int count = 0;
        if (nums instanceof int[]) {
            for (int n : (int[])nums) {
                if (n < t) count++;
            }
        } else if (nums instanceof List) {
            for (Object n : (List)nums) {
                if ((int)n < t) count++;
            }
        }
        return count;
    }
}