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.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).
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.
C++
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search | — |
| Divide and Conquer | — |
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