Problem Description

You are given a very large array nums with a special property: all occurrences of the same value appear consecutively. This means if a value appears multiple times in the array, all those occurrences must be adjacent to each other with no other values in between.

Since the array is extremely large, you cannot access it directly. Instead, you're provided with a BigArray class that has two methods:

• at(index): Returns the value at the given index
• size(): Returns the total length of the array

Your task is to count how many distinct blocks of equal values exist in the array. A block is a maximal contiguous segment where all elements have the same value.

For example:

• If the array is [1, 1, 1, 2, 2, 3, 3, 3, 3], there are 3 blocks: [1,1,1], [2,2], and [3,3,3,3]
• If the array is [5, 5, 4, 4, 4, 7], there are 3 blocks: [5,5], [4,4,4], and [7]

The solution uses binary search to efficiently find the boundaries of each block. Starting from index 0, for each new block encountered, it uses binary search to find where that block ends (the first index where the value changes), then moves to the next block. This approach is efficient for very large arrays since it doesn't need to check every single element when dealing with large blocks of the same value.

The time complexity is O(b * log(n)) where b is the number of blocks and n is the array size, which is much better than O(n) when there are long sequences of repeated values.

Intuition

The key insight comes from recognizing that we're dealing with a potentially massive array where consecutive equal values form blocks. If we naively check every single element, we'd need O(n) operations, which could be inefficient for very large arrays.

Think about it this way: if we encounter a block of one million consecutive 5s, do we really need to check all million elements? No! We just need to find where this block ends.

This leads us to the binary search approach. When we're at the start of a block with value x, we know that:

• Elements equal to x will continue for some distance
• At some point, we'll hit an element that's not equal to x (marking the end of the block)

We can use binary search to find this boundary efficiently. The search space is from our current position to the end of the array. We're looking for the first index where the value changes from x.

The binary search works because of the problem's guarantee: all occurrences of a value are adjacent. This means once we find a value different from x, we know we've passed the entire block of xs, and there won't be any more xs later in the array.

For each block, instead of checking potentially millions of elements one by one (O(block_size)), we can find the block's end in just O(log(n)) operations using binary search. This is especially powerful when blocks are large.

The bisect_left function with a custom key lambda j: nums.at(j) != x cleverly searches for the first position where the condition "value is not equal to x" becomes True, which is exactly where our current block ends.

Learn more about Binary Search patterns.

Solution Approach

The solution uses the binary search template to efficiently find the boundaries of each block of equal values.

Binary Search Template Applied:

For each block starting at index startIndex, we find the first index where the value differs from targetValue. The feasible function is:

• feasible(mid) = nums.at(mid) != targetValue
• Pattern: false, false, ..., false, true, true, true
• We find the first True index (first different element)

left, right = start_index, array_size - 1
first_true_index = array_size  # Default if all remaining elements are same

while left <= right:
    mid = left + (right - left) // 2
    if nums.at(mid) != target_value:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index  # Index of first different element

Main Algorithm Flow:

1. Start at index 0
2. For each block:
   • Use binary search to find where the block ends (first different value)
   • Increment block counter
   • Jump to the end of the current block
3. Repeat until we've processed the entire array

Why This Works:

The algorithm leverages the problem's guarantee that all occurrences of a value are consecutive. The binary search finds the exact boundary where values change, allowing us to skip entire blocks efficiently.

Time Complexity:

• For each block, binary search takes O(log n) time
• Total complexity: O(b × log n) where b is the number of blocks
• This is much better than O(n) when blocks are large

Example Walkthrough

Let's walk through the algorithm with the array [2, 2, 2, 7, 7, 3, 3, 3, 3, 3] which has length 10.

Initial State:

• i = 0, n = 10, ans = 0

First Block (value = 2):

• Increment counter: ans = 1
• Current value: x = nums.at(0) = 2
• Check next element: nums.at(1) = 2 (same as x)
• Since the block continues, use binary search to find where it ends
• Binary search in range [0, 10) looking for first index where value ≠ 2:
  • Mid = 5: nums.at(5) = 3 (≠ 2) → search left half
  • Mid = 2: nums.at(2) = 2 (= 2) → search right half
  • Mid = 3: nums.at(3) = 7 (≠ 2) → search left half
  • Found: index 3 is the first position where value ≠ 2
• Jump to index 3: i = 0 + 3 = 3

Second Block (value = 7):

• Increment counter: ans = 2
• Current value: x = nums.at(3) = 7
• Check next element: nums.at(4) = 7 (same as x)
• Use binary search in range [3, 10) looking for first index where value ≠ 7:
  • Mid = 6: nums.at(6) = 3 (≠ 7) → search left half
  • Mid = 4: nums.at(4) = 7 (= 7) → search right half
  • Mid = 5: nums.at(5) = 3 (≠ 7) → found
• Jump to index 5: i = 3 + (5-3) = 5

Third Block (value = 3):

• Increment counter: ans = 3
• Current value: x = nums.at(5) = 3
• Check next element: nums.at(6) = 3 (same as x)
• Use binary search in range [5, 10) looking for first index where value ≠ 3:
  • Mid = 7: nums.at(7) = 3 (= 3) → search right half
  • Mid = 9: nums.at(9) = 3 (= 3) → search right half
  • Search reaches end of array at index 10
• Jump to index 10: i = 5 + (10-5) = 10

Termination:

• i = 10 which equals n, so we exit the loop
• Return ans = 3

The algorithm correctly identified 3 blocks: [2,2,2], [7,7], and [3,3,3,3,3], making only 11 array accesses instead of checking all 10 elements sequentially.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log n), where m is the number of distinct blocks (consecutive elements with the same value) in the array, and n is the length of the array.

The algorithm iterates through the array and for each distinct block:

• When encountering a new value that differs from the next element (the if branch), it moves forward by 1 position in O(1) time
• When encountering a value that continues in a block (the else branch), it uses binary search via bisect_left to find the end of the current block, which takes O(log n) time

Since we process each of the m blocks exactly once, and in the worst case each block requires a binary search operation, the total time complexity is O(m × log n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables i, n, ans, and x, regardless of the input size. The bisect_left operation with the range object and lambda function doesn't create additional space proportional to the input size, as the range object is a lazy iterator and the lambda function is evaluated on-the-fly.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

Pitfall: Using while left < right with right = mid instead of the standard template.

Common incorrect pattern:

# WRONG: Non-standard template
while left < right:
    mid = (left + right) >> 1
    if nums.at(mid) != target:
        right = mid
    else:
        left = mid + 1
return left

Solution: Use the standard template with first_true_index:

# CORRECT: Standard template
left, right = start_index, array_size - 1
first_true_index = array_size

while left <= right:
    mid = left + (right - left) // 2
    if nums.at(mid) != target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index

2. Incorrect Binary Search Range

Pitfall: When using Python's bisect_left with range(), the returned index is relative to the range, not absolute.

Solution: For clearer code, use explicit binary search with first_true_index tracking.

3. Edge Case: Last Block Extends to End

Pitfall: Not handling the case where no different value is found.

Solution: Initialize first_true_index = array_size so that when no different element exists, we correctly return the array size as the block end.

4. Optimization Check Boundary Issue

Pitfall: Accessing nums.at(current_index + 1) without bounds checking.

Solution:

if current_index + 1 < total_size and nums.at(current_index + 1) != current_value:
    current_index += 1