Problem

You are given a 0-indexed array of integers, nums. The following property holds for nums:

  • All occurrences of a value are adjacent. In other words, if there are two indices 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.

Examples

Example 1:

1
2
3

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:

1
2
3
4
5
6
7
8
9

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:

1
2
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 <= 1015
  • 1 <= nums[i] <= 10^9
  • The input is generated such that all equal values are adjacent.
  • The sum of the elements of nums is at most 1015.

Solution

Method 1 – Binary Search for Block Boundaries

Intuition

Since all equal values are adjacent, each block is a contiguous segment of equal values. We can find the start of each block by moving to the next index where the value changes, using binary search to jump to the end of the current block efficiently.

Approach

  1. Start at index 0. For each block, use binary search to find the last index of the current value.
  2. Move to the next index and repeat until the end of the array.
  3. Count the number of blocks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int numberOfBlocks(BigArray arr) {
        int n = arr.size();
        int blocks = 0;
        long i = 0;
        while (i < n) {
            int val = arr.at(i);
            long l = i, r = n-1, last = i;
            while (l <= r) {
                long m = l + (r-l)/2;
                if (arr.at(m) == val) {
                    last = m; l = m+1;
                } else {
                    r = m-1;
                }
            }
            blocks++;
            i = last+1;
        }
        return blocks;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def numberOfBlocks(self, arr: 'BigArray') -> int:
        n = arr.size()
        blocks = 0
        i = 0
        while i < n:
            val = arr.at(i)
            l, r, last = i, n-1, i
            while l <= r:
                m = (l+r)//2
                if arr.at(m) == val:
                    last = m; l = m+1
                else:
                    r = m-1
            blocks += 1
            i = last+1
        return blocks

Complexity

  • ⏰ Time complexity: O(B*log N), where B is the number of blocks and N is the array size.
  • 🧺 Space complexity: O(1).