Start learning free

LESSON 250 OF 348 · BINARY SEARCH

Number of Occurrences in Kotlin: O(log n) with Two Lower Bounds

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

    KOTLIN · BINARY SEARCH

    Number Of Occurrences in Kotlin, explained

    Problem overview

    The function count receives a sorted IntArray called nums and an Int called 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 too slow: that takes O(n).

    In the example, nums = [1, 2, 2, 2, 4, 5] and value = 2. The 2s sit at indices 1, 2 and 3, so the answer is 3. If the value is missing, the answer is 0.

    Approach: two lower bounds

    Because the array is sorted, equal values are neighbours. All the occurrences of value form one block of consecutive indices, and the block's length is the count. To measure the block you need only its two ends: the first index holding value and the first index after the block.

    Both ends come from the same tool, the lower bound: the first index whose element is not less than a given number. If the number is absent, the lower bound is the index where it would be inserted to keep the array sorted.

    • lowerBound(nums, value) is the start of the block.
    • lowerBound(nums, value + 1) is the first index whose element is at least value + 1. The array holds integers, so that is the first element greater than value, which is one past the end of the block.

    The count is the difference. On the example, lowerBound(nums, 2) is 1 and lowerBound(nums, 3) is 4, so the answer is 4 - 1 = 3. For a missing value such as 3, both calls return 4 and the difference is 0, with no special case needed.

    Each lower bound is a binary search, O(log n), and two of them are still O(log n). Another way to say it: the first occurrence and the last occurrence can each be found by a binary search, and this lesson turns the second search into a second lower bound to reuse the code.

    Step by step

    1. Call lowerBound for the value. Store the result in low, a val because it never changes. The helper doesn't exist yet; the lesson writes the caller first.
    2. Call it again for value + 1 and store the result in high. Together, low and high - 1 bracket every occurrence.
    3. Return high - low. That is the length of the block.
    4. Declare the helper above count as fun lowerBound(nums: IntArray, value: Int): Int.
    5. Set up the window. Two vars, left = 0 and right = nums.size - 1, mark the first and last indices still in play. They change as the search narrows, so they are var.
    6. Loop while the window has an element: left <= right.
    7. Probe the middle with (left + right) / 2. Integer division rounds down, so middle is always a valid index.
    8. If nums[middle] is less than value, the middle and everything before it are too small, so the answer lies to the right: left = middle + 1.
    9. Otherwise nums[middle] is at least value, so the lower bound is at middle or earlier. Set right = middle - 1.
    10. Return left after the loop. At that point left has moved past every element that is less than value, so it is the first index whose element is not less, or nums.size if there is none.

    The solution in Kotlin

    class Solution {
    fun lowerBound(nums: IntArray, value: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left <= right) {
            val middle = (left + right) / 2
            if (nums[middle] < value) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
        return left
    }

    fun count(nums: IntArray, value: Int): Int {
        val low = lowerBound(nums, value)
        val high = lowerBound(nums, value + 1)
        return high - low
    }
}

    A few Kotlin details:

    • val and var. low, high and middle are assigned once per call or iteration, so they are val. left and right are reassigned inside the loop, so they must be var. The compiler rejects reassigning a val.
    • Parameters are read-only. That is why the search keeps its moving bounds in new variables instead of changing nums or value.
    • Integer division. With two Int operands, / drops the fraction, so (0 + 5) / 2 is 2.
    • Methods call each other freely. Inside a class, count can call lowerBound even though it is declared above it; the order of members doesn't matter.
    • Arrays are passed by reference. Passing nums to lowerBound copies nothing, which keeps the extra space at O(1).

    Complexity

    Time: O(log n). Every loop iteration discards at least half of the window, so a lower bound takes at most about log2(n) + 1 iterations. count makes two such searches.

    Space: O(1). The code keeps a handful of Int variables whatever the size of nums.

    Edge cases and common mistakes

    • Empty array. right starts at -1, the loop doesn't run, lowerBound returns 0 both times, and count returns 0.
    • Missing value. Both lower bounds land on the same index, so the difference is 0. For [1, 2, 2, 2, 4, 5] and value = 3, both calls return 4.
    • Every element equals the value. For [5, 5, 5] and value = 5, the lower bounds are 0 and 3, so the count is 3. The second search runs off the end of the array and returns nums.size, which is exactly what the subtraction needs.
    • Using < in the loop condition. With left < right, a window of one element is never examined, and the search can stop one index early.
    • Returning middle on a match. That finds some occurrence, not the first one. The lower bound keeps searching left even after a hit.
    • Overflow at the top of the range. An Int wraps silently, so value + 1 becomes Int.MIN_VALUE when value is Int.MAX_VALUE. For [1, 2147483647, 2147483647] and value = 2147483647 the function returns -1 instead of 2. The tests don't use values this large, but a robust version would search for the first element greater than value directly instead of adding 1.

    Testing

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