Start learning free

LESSON 274 OF 414 · BINARY SEARCH

Number of Occurrences in a Sorted Array in Scala: O(log n)

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 occurrences of value.

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

We can find the first occurrence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurrence 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 should we do if:
  • the element at index mid is greater than value?
  • the element at index mid is less than or equal to value?


  • If the element at index mid is greater than value, we should continue the search in the part of nums from left to mid - 1, e.g. set right to mid - 1
  • If the element at index mid is less than or equal to value, we should set ans to mid and continue the search in the part of nums from mid + 1 to right, e.g. set left to mid + 1

STEP 1 OF 10
    Ctrl + Enter to check

    SCALA · BINARY SEARCH

    Number Of Occurrences in Scala, explained

    Problem overview

    The method count receives a sorted Array[Int] named nums and an Int named value. It returns how many times value appears in the array. For nums = [1, 2, 2, 2, 4, 5] and value = 2, the answer is 3.

    Counting with a loop takes O(n) time. The statement asks for O(log n) time and O(1) extra space, so the array has to be searched by halving, not scanned.

    Approach: two lower bounds

    Because the array is sorted, all copies of value sit next to each other in one block. If you know where the block starts and where it ends, the count is the difference of the two positions.

    The lower bound of a number is the first index whose element is not less than that number. It is also the index where the number would be inserted. Two calls give both ends of the block:

    • lowerBound(nums, value) is the index of the first copy of value. If value is missing, it is the position where it would go.
    • lowerBound(nums, value + 1) is the index of the first element greater than value. The array holds integers, so "greater than value" and "at least value + 1" mean the same thing. This index is just past the last copy.

    With [1, 2, 2, 2, 4, 5] and value = 2, the first call returns 1 and the second returns 4 (the lower bound of 3 is the position of 4). The block is indices 1, 2 and 3, and 4 - 1 = 3.

    When value is absent, both calls return the same index, because there is nowhere for the two boundaries to differ, and the difference is 0. Each call is an O(log n) binary search, so the total stays O(log n).

    Another way to find the end of the block is to write a second binary search that looks for the last occurrence. Reusing lowerBound avoids that: one tested routine does both jobs, and the only new idea is to ask it about value + 1.

    Step by step

    1. In count, store lowerBound(nums, value) in a val named low.
    2. Store lowerBound(nums, value + 1) in a val named high.
    3. Return high - low.
    4. Write lowerBound above count. It keeps a window [left, right] in two vars, starting at 0 and nums.length - 1.
    5. Loop while left <= right, so a window holding one element is still examined.
    6. Take middle = (left + right) / 2. Integer division rounds down, so it is a valid index.
    7. If nums(middle) < value, everything up to middle is too small, so set left = middle + 1.
    8. Otherwise nums(middle) is at least value, so the boundary is middle or further left. Set right = middle - 1.
    9. After the loop, return left. It is the first index whose element is at least value, or nums.length if there is none.

    The solution in Scala

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

    def count(nums: Array[Int], value: Int): Int = {
        val low = lowerBound(nums, value)
        val high = lowerBound(nums, value + 1)
        return high - low
    }
}

    Scala details

    Arrays are indexed with parentheses: nums(middle). Parameters are immutable, so the search copies the bounds into var variables, while middle, low and high never change after creation and are vals.

    Scala methods return the value of their last expression, so return is rarely needed, but it is allowed. Here return left and return high - low are the last statements, so they behave exactly like the bare expressions left and high - low would.

    Both methods live in the same class, and the order of definitions inside a class does not matter, so count could also come first.

    An Int is 32 bits and overflow wraps silently. That is relevant to value + 1, as the edge cases below show.

    Complexity

    Each lowerBound call halves its window at every step, which takes at most about log n iterations. count makes two calls, so the time is O(log n). Only a handful of Int variables are used, so the extra space is O(1).

    Edge cases and common mistakes

    • Value not present. For [1, 2, 2, 2, 4, 5] and value = 3, both lower bounds are 4, so the result is 0.
    • Value at the end. For the same array and value = 5, the lower bounds are 5 and 6 (the array length), so the result is 1. The second index can legitimately equal nums.length.
    • Value larger than every element. Both calls return nums.length, and the result is 0.
    • All elements equal. For [7, 7, 7] and value = 7, the bounds are 0 and 3, giving 3.
    • Empty array. Both searches return 0, so the count is 0.
    • Overflow at the top of the range. If value is Int.MaxValue, then value + 1 wraps around to Int.MinValue. For Array(1, Int.MaxValue) and value = Int.MaxValue, the second lower bound is 0 and the method returns -1 instead of 1. If values can reach that limit, handle it separately, for example by computing the upper end with a search for the first element greater than value instead of using value + 1.
    • Using a strict comparison for both ends. The trick only works because both ends use the same lower-bound search, which treats equal elements as "not too small". Searching for value with an exact-match binary search would find one copy, not the boundaries.

    Testing

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