Number of Equal Numbers Blocks

Number of Equal Numbers Blocks

What is this problem about?

The Number of Equal Numbers Blocks problem presents an interactive problem where you have a hidden array and an API call query(l, r) that returns whether all elements in arr[l..r] are equal. Find all maximal blocks of equal consecutive elements with the minimum number of API calls. This coding problem uses binary search to find block boundaries efficiently.

Why is this asked in interviews?

Google asks this interactive binary search problem to test the ability to design efficient API-usage strategies. The naive O(n) sequential scan uses n-1 calls; binary search reduces calls per block boundary to O(log n). The array, interactive, and binary search interview pattern is directly demonstrated.

Algorithmic pattern used

Binary search for block boundaries. Start at index 0. For each current block starting at left: binary search for the rightmost index where query(left, mid) is true. This gives the right boundary of the current block. Record the block, then move left to right + 1. Continue until the end of the array. Each block boundary discovery takes O(log n) API calls.

Example explanation

Array: [3, 3, 3, 7, 7, 1, 1, 1, 1]. Blocks: [3,3,3], [7,7], [1,1,1,1].

• Start at 0. Binary search: query(0,4)=false (3≠7), query(0,2)=true, query(0,3)=false → block [0..2]=3.
• Start at 3. Binary search: query(3,4)=true, query(3,5)=false → block [3..4]=7.
• Start at 5. Binary search: query(5,8)=true → block [5..8]=1. Total API calls: ~3 * log(9) ≈ 9 calls (vs 8 for brute force but amortized better for larger arrays).

Common mistakes candidates make

• Using sequential scan (O(n) calls — misses the binary search insight).
• Binary searching on the wrong condition (should find rightmost position where prefix is uniform).
• Not advancing left correctly after finding each block boundary.
• Off-by-one in the binary search bounds.

Interview preparation tip

Interactive binary search problems require designing the binary search condition around the API. Here: "find the rightmost index r such that all elements from left to r are equal" is a monotonic condition (if (left,r) is uniform, so is (left,r-1)). Standard binary search applies. Practice interactive problems by mentally simulating API calls — always aim to minimize total calls by finding block boundaries in O(log n) per block.