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.
We can use binary search to find the right boundary of each block. Specifically, we traverse the array from left to right. For each index i, we use binary search to find the smallest index j such that all elements between [i,j) are equal to nums[i]. Then we update i to j and continue to traverse the array until i is greater than or equal to the length of the array.
The time complexity is O(m times log n), where m is the number of different elements in the array num, and n is the length of the array num. The space complexity is O(1).
Python
Java
C++
TypeScript
We can use the divide and conquer method to calculate the answer. Specifically, we divide the array into two subarrays, recursively calculate the answer for each subarray, and then merge the answers. If the last element of the first subarray is equal to the first element of the second subarray, then we need to subtract one from the answer.
The time complexity is O(log n), and the space complexity is O(log n). Here, n is the length of the array num.
Java
C++
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search | — |
| Divide and Conquer | — |
| 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 |
How to EASILY solve LeetCode problems • NeetCode • 427,751 views views
Watch 9 more video solutions →Practice Number of Equal Numbers Blocks with our built-in code editor and test cases.
Practice on FleetCode