LeetCode 2936 - Number of Equal Numbers Blocks

The problem is asking us to count the number of maximal contiguous blocks of equal numbers in a very large array nums. A block is maximal if it contains all consecutive occurrences of the same number, and numbers are guaranteed to appear in consecutive segments, i.e.

leetcodemediumarraybinary-searchinteractive

LeetCode Problem 2936

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Interactive

Solution

Problem Understanding

The problem is asking us to count the number of maximal contiguous blocks of equal numbers in a very large array nums. A block is maximal if it contains all consecutive occurrences of the same number, and numbers are guaranteed to appear in consecutive segments, i.e., the array is already "grouped" by value. The key challenge is that nums is extremely large - up to $10^{15}$ elements - which makes iterating through the array directly infeasible. Instead, we are provided a BigArray interface with two operations: at(index) to access an element and size() to get the length.

The input represents a 0-indexed array where all equal numbers are adjacent. The expected output is a single integer indicating how many contiguous blocks of equal numbers exist in the array.

Key constraints to note are the array's size (up to $10^{15}$) and the guarantee that all equal numbers are adjacent. This means we can leverage binary search to efficiently find block boundaries instead of iterating element by element.

Important edge cases include arrays where all numbers are the same, arrays with all distinct numbers, and very small arrays (length 1 or 2). The guarantee of adjacency simplifies the problem because we never have to handle "scattered duplicates."

Approaches

Brute Force

The naive approach is to iterate through the array from start to end, counting the number of times a value changes. Each time the value at the current index differs from the previous, we increment the block count. This works correctly for small arrays but requires $O(n)$ calls to at(index), which is impossible for $n \leq 10^{15}$.

Optimal Approach

The key observation is that all occurrences of a value are contiguous, so each block can be found using binary search. Instead of checking every element, we can jump ahead to the last occurrence of the current value in logarithmic steps. For each block starting at index i, we perform a binary search to find the first index where the value changes. We then move i to that new index and repeat until we reach the end of the array. This reduces the number of at() calls from linear to roughly $O(b \log n)$, where b is the number of blocks.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Iterates over all elements; impractical for very large arrays
Optimal O(b * log n) O(1) Uses binary search to jump to block boundaries efficiently

Algorithm Walkthrough

  1. Initialize index = 0 and count = 0. index will track the start of the current block.

  2. Retrieve the length of the array via nums.size().

  3. While index < n, do the following:

  4. Increment count since we have found a new block starting at index.

  5. Store the value of the current block in current_val = nums.at(index).

  6. Use binary search to find the first index right where nums.at(right) != current_val. Start left = index + 1 and right = n. While left < right, check the middle element. If it is equal to current_val, move left to mid + 1, otherwise move right to mid.

  7. Set index = right to move to the start of the next block.

  8. Return count when index >= n.

Why it works: The algorithm relies on the invariant that all occurrences of a number are contiguous. Binary search guarantees that we efficiently find the boundary of each block without inspecting every element. Incrementing count each time a new block is encountered ensures we count all blocks exactly once.

Python Solution

# Definition for BigArray.
# class BigArray:
#     def at(self, index: long) -> int:
#         pass
#     def size(self) -> long:
#         pass

class Solution(object):
    def countBlocks(self, nums: 'BigArray') -> int:
        n = nums.size()
        count = 0
        index = 0
        
        while index < n:
            count += 1
            current_val = nums.at(index)
            
            left, right = index + 1, n
            while left < right:
                mid = left + (right - left) // 2
                if nums.at(mid) == current_val:
                    left = mid + 1
                else:
                    right = mid
            index = right
        
        return count

Implementation Walkthrough: We start at index 0 and initialize count to 0. Each iteration of the outer loop represents finding a new block. We retrieve the current value and use binary search to locate the end of the block. After the binary search, index points to the start of the next block. This continues until we reach the end of the array.

Go Solution

/**
 * Definition for BigArray.
 * type BigArray interface {
 *     At(int64) int
 *     Size() int64
 * }
 */
func countBlocks(nums BigArray) int {
    n := nums.Size()
    count := 0
    var index int64 = 0
    
    for index < n {
        count++
        currentVal := nums.At(index)
        left, right := index+1, n
        for left < right {
            mid := left + (right-left)/2
            if nums.At(mid) == currentVal {
                left = mid + 1
            } else {
                right = mid
            }
        }
        index = right
    }
    
    return count
}

Go Notes: Go uses int64 for indices because the array can be extremely large. The binary search and main loop logic is identical to the Python version. The handling of integers and array access is straightforward due to the provided BigArray interface.

Worked Examples

Example 1: nums = [3,3,3,3,3]

Step index current_val left right count
1 0 3 1 5 1
2 5 - - - 1

Result: 1 block

Example 2: nums = [1,1,1,3,9,9,9,2,10,10]

Step index current_val left right count
1 0 1 1 10 1
2 3 3 4 10 2
3 4 9 5 10 3
4 7 2 8 10 4
5 8 10 9 10 5
6 10 - - - 5

Result: 5 blocks

Example 3: nums = [1,2,3,4,5,6,7]

Each element is a single block, count increments from 1 to 7. Result: 7 blocks.

Complexity Analysis

Measure Complexity Explanation
Time O(b * log n) Each block requires a binary search to find its end; total time proportional to number of blocks times log of array size
Space O(1) Only counters and temporary variables are used; no extra memory scales with input size

Since n can be extremely large, iterating directly is infeasible. This algorithm efficiently jumps to block boundaries using binary search.

Test Cases

# test cases
# single block
assert Solution().countBlocks(BigArrayMock([3,3,3,3,3])) == 1  # all equal
# multiple blocks
assert Solution().countBlocks(BigArrayMock([1,1,1,3,9,9,9,2,10,10])) == 5
# all distinct
assert Solution().countBlocks(BigArrayMock([1,2,3,4,5,6,7])) == 7
# single element
assert Solution().countBlocks(BigArrayMock([42])) == 1
# two identical elements
assert Solution().countBlocks(BigArrayMock([5,5])) == 1
# two distinct elements
assert Solution().countBlocks(BigArrayMock([5,6])) == 2
# large uniform block (simulate smaller)
assert Solution().countBlocks(BigArrayMock([7]*100)) == 1
Test Why
single block Validates the simplest case of all identical values
multiple blocks Ensures multiple transitions are counted correctly
all distinct Each element is a block
single element Edge case of smallest array
two identical Minimal size with repeated elements
two distinct Minimal size with distinct elements
large uniform Checks efficiency of binary search in a