Watch 10 video solutions for Number of Equal Numbers Blocks, a medium level problem involving Array, Binary Search, Interactive. This walkthrough by NeetCode has 427,751 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array of integers, nums. The following property holds for nums:
i < j such that nums[i] == nums[j], then for every index k that i < k < j, nums[k] == nums[i].Since nums is a very large array, you are given an instance of the class BigArray which has the following functions:
int at(long long index): Returns the value of nums[i].void size(): Returns nums.length.Let's partition the array into maximal blocks such that each block contains equal values. Return the number of these blocks.
Note that if you want to test your solution using a custom test, behavior for tests with nums.length > 10 is undefined.
Example 1:
Input: nums = [3,3,3,3,3] Output: 1 Explanation: There is only one block here which is the whole array (because all numbers are equal) and that is: [3,3,3,3,3]. So the answer would be 1.
Example 2:
Input: nums = [1,1,1,3,9,9,9,2,10,10] Output: 5 Explanation: There are 5 blocks here: Block number 1: [1,1,1,3,9,9,9,2,10,10] Block number 2: [1,1,1,3,9,9,9,2,10,10] Block number 3: [1,1,1,3,9,9,9,2,10,10] Block number 4: [1,1,1,3,9,9,9,2,10,10] Block number 5: [1,1,1,3,9,9,9,2,10,10] So the answer would be 5.
Example 3:
Input: nums = [1,2,3,4,5,6,7] Output: 7 Explanation: Since all numbers are distinct, there are 7 blocks here and each element representing one block. So the answer would be 7.
Constraints:
1 <= nums.length <= 10151 <= nums[i] <= 109nums is at most 1015.Problem Overview: You are given an interactive array where values can only be accessed through a query API. The goal is to count how many contiguous blocks of equal numbers exist. A block is a maximal segment where every element has the same value. Since direct array access is restricted, the challenge is minimizing queries while identifying block boundaries.
Approach 1: Binary Search on Block Boundaries (O(b log n) time, O(1) space)
Start at the leftmost index and query its value. That value defines the current block. Instead of scanning linearly, use binary search to locate the farthest index where the value remains the same. Each search finds the right boundary of the current block in O(log n) queries. Move to the next index after that boundary and repeat until the array ends. If the array has b distinct blocks, the total cost becomes O(b log n) queries with constant auxiliary memory. This approach minimizes expensive API calls and works well when large blocks exist.
Approach 2: Divide and Conquer (O(b log n) time, O(log n) space)
Treat the array as a segment and recursively determine how many blocks it contains. Query the values at the left and right ends of the segment. If both values are equal, the entire segment might belong to one block, so no further splitting is needed. If they differ, split the segment at the midpoint and recursively evaluate both halves. This is a classic divide and conquer pattern combined with value queries. Each recursive split narrows down the boundaries of equal segments while avoiding unnecessary exploration.
The divide‑and‑conquer strategy performs well when blocks are unevenly distributed because large uniform ranges terminate early. The recursion depth is O(log n), and the total number of value checks stays proportional to the number of distinct blocks.
Recommended for interviews: The binary search boundary approach is usually the expected answer. It shows you recognize that each block can be located with logarithmic queries rather than scanning sequentially. Discussing a naive linear scan first demonstrates understanding, but implementing the optimized array boundary search shows stronger algorithmic thinking and awareness of query‑limited environments.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Queries | O(n) | O(1) | Conceptual baseline when query cost is not restricted |
| Binary Search for Block End | O(b log n) | O(1) | Best when the array has large equal segments and queries are expensive |
| Divide and Conquer | O(b log n) | O(log n) | Useful when segments can terminate early based on boundary values |