Start learning free

LESSON 250 OF 348 · BINARY SEARCH

Number of Occurrences in TypeScript: O(log n) with Lower Bound

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, count the number of occurrences of a given value.

Example:

Input: nums = [1, 2, 2, 2, 4, 5], value = 2
Output: 3
Explanation: the value 2 appears 3 times in the array

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Hints:

If value exists in nums, it will occur in a subarray of consecutive elements. If we manage to find this subarray, we'll also know the number of occurences of value.

This subarray is determined by the first and last indices where value occurs in nums. How would you find the first occurence in O(log n) time?

We can find the first occurence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurence of value in nums?


We will implement a binary search and use a variable ans to store the best answer found so far, just like we did in Lower Bound. The only difference is how we handle the cases for each mid index. What shoud we do if:
  • a[mid] is greater than value?
  • a[mid] is less than or equal to value?


  • If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. set right to mid - 1
  • If a[mid] is less than or equal to value, we should set ans to mid and continue the search in nums[mid + 1...right], e.g. set left to mid + 1

STEP 1 OF 10
    Ctrl + Enter to check

    TYPESCRIPT · BINARY SEARCH

    Number Of Occurrences in TypeScript, explained

    Problem overview

    The method count receives a sorted array of integers, nums, and a number, value. It returns how many times value appears in nums. The statement asks for O(log n) time and O(1) extra space, so walking through the array and counting is not allowed: that takes O(n).

    In the example, nums = [1, 2, 2, 2, 4, 5] and value = 2. The 2 sits at indices 1, 2 and 3, so the answer is 3.

    Approach: two lower bounds

    Because the array is sorted, equal values are neighbours. All the 2s form one block, so if you know where the block starts and where it ends, the count is the length of the block.

    The lower bound of a value is the first index whose element is not less than it. If the value is missing, it is the index where the value would be inserted to keep the array sorted. Binary search finds it in O(log n).

    The trick is to call the lower bound twice:

    • the lower bound of value is the index where the block of value starts;
    • the lower bound of value + 1 is the first index holding something greater than value, which is the index just past the block.

    The difference between the two is the block's length. When value does not occur, both calls return the same index and the difference is 0, so no special case is needed.

    On the example, the lower bound of 2 is index 1, and the lower bound of 3 is index 4 (the element 4 is the first one that is not less than 3). Then 4 - 1 gives 3.

    Step by step

    1. Find where the block starts. In count, call this.lowerBound(nums, value) and keep the result in low. Writing count first, with lowerBound still to come, keeps attention on the idea.
    2. Find where the block ends. Call lowerBound again with value + 1 and keep it in high. This works because the array holds integers: nothing lies between value and value + 1.
    3. Return high - low.
    4. Declare the helper above count: lowerBound(nums: number[], value: number): number.
    5. Set the search window to the whole array: left is 0 and right is nums.length - 1.
    6. Loop while the window is non-empty, that is, while left <= right.
    7. Take the middle as Math.floor((left + right) / 2). The rounding matters because / on numbers can give a fraction, and nums[2.5] is undefined.
    8. If nums[middle] is less than value, the middle element and everything to its left are too small, so move left to middle + 1.
    9. Otherwise the middle element is at least value, so the answer is at middle or to its left. Move right to middle - 1.
    10. Return left after the loop. At that point left is the first index whose element is at least value, or nums.length if there is no such element.

    The solution in TypeScript

    class Solution {
    lowerBound(nums: number[], value: number): number {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let middle = Math.floor((left + right) / 2);
            if (nums[middle] < value) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return left;
    }

    count(nums: number[], value: number): number {
        let low = this.lowerBound(nums, value);
        let high = this.lowerBound(nums, value + 1);
        return high - low;
    }
}

    Some TypeScript details:

    • Division does not round. In TypeScript number is a double, so (0 + 5) / 2 is 2.5. Math.floor turns it into a valid index.
    • Calling a sibling method. Inside a class, count reaches lowerBound through this. Writing the bare name lowerBound(...) would look for a variable or function with that name and fail.
    • Type annotations are only for the compiler. number[] and : number are erased when TypeScript is compiled to JavaScript. They do not check what a caller really passes at run time.
    • The value + 1 trick needs integers. With fractions it breaks: for [1.5, 2, 2.5, 2.5] and value = 1.5 the function returns 2, although 1.5 appears once. The lesson promises integers, so it is fine here.

    Complexity

    Time: O(log n). Each pass of the loop halves the window, so lowerBound runs about log2(n) times, and count calls it twice. Two times O(log n) is still O(log n).

    Space: O(1). Only a few numbers are stored, whatever the size of the array.

    Edge cases and common mistakes

    • Value missing. For the example array and value = 3, both lower bounds are 4, so the result is 0.
    • Value larger than everything. With value = 5 in the example array, the lower bounds are 5 and 6. The second one is nums.length, which is a valid answer for a lower bound, and the count is 1.
    • Value smaller than everything. Both calls return 0, and the count is 0.
    • Empty array. right starts at -1, the loop never runs, both calls return 0, and the count is 0.
    • Every element equal to the value. For [7, 7, 7] and value = 7, the lower bounds are 0 and 3, so the count is 3.
    • Using middle instead of middle - 1. When the window shrinks to one element, the loop would never end.
    • Unsorted input. Binary search silently gives wrong answers on an unsorted array.

    Testing

    • nums = [1, 2, 2, 2, 4, 5], value = 2 gives 3.
    • The same array with value = 3 gives 0.
    • The same array with value = 5 gives 1.
    • nums = [], value = 1 gives 0.
    • nums = [7, 7, 7], value = 7 gives 3.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free