2936. Number of Equal Numbers Blocks


Problem Description

In this problem, you are presented with an array of integers, nums, where all occurrences of any given value are situated next to each other. It means that the array is segmented into blocks of equal values. The objective is to count how many such blocks exist in the array. Since nums can be very large, you are provided with a BigArray class with two functions to interact with the array: at(index) to get the value at a certain index, and size() to get the total size of the array.

You are required to determine the number of maximal blocks of equal values within this array. A maximal block is a continuous subarray where all elements are the same and cannot be extended further while maintaining the same value.

Intuition

To solve this problem, we need to find a way to count contiguous blocks of equal values within a potentially very large array, without scanning every single element. The key observation is that, due to the property of the array (all occurrences of a value being adjacent), once we find a new value different from the current one, we know a new block has started.

Starting from the first element, we can search for the boundary of each block. Since performing a linear search may not be efficient for a large dataset, we can take advantage of the block property and use binary search. Binary search will efficiently find the next index where a different value occurs, which also marks the end of the current block.

Here's how we can arrive at the solution: We iterate through the array elements using a loop. At each step, we look for the first index on the right side of the current position that has a different value than the value at the current position. This marks the end of a block. We can speed up this search using binary search as follows:

  1. From the current index, we check the next value. If it's different, this is already the end of a block.
  2. If it's not different, we perform a binary search between the current index and the end of the array to find the first position where the value differs from the current block's value. This is done with the help of a key function provided to bisect_left, which uses the at method of the BigArray.
  3. We update the current index to the boundary found (the index with a different value) to continue searching for the next block.

We repeat this process until we reach the end of the array and in the process, maintain a count of blocks found.

Learn more about Binary Search and Divide and Conquer patterns.

Solution Approach

The solution employs a binary search strategy to efficiently find the right boundary of each block in the array. Let's break down the implementation steps of the solution using algorithms and data structures:

  1. Initialize an index i at 0 and a counter ans to 0 to keep the tally of blocks encountered.
  2. Loop until i is less than the size n of the BigArray.
  3. For each iteration of the loop:
    • Increment the block counter ans since the element at index i starts a new block.
    • Check the value at the current index x = nums.at(i).
    • Then there are two possible scenarios: a. If the element immediately next to the current one (i + 1) is different from x, it implies the current block is of size 1. So, increment i by 1. b. If the next element is not different, then perform a binary search to find the left boundary of the next block where the value differs from x. Use the bisect_left method combined with a key function that leverages nums.at(j) to perform the binary search efficiently. c. Update the index i to the boundary index found using the binary search. This skips the entire block of identical elements in one step.
  4. Return the counter ans as the final result, which represents the total number of blocks in the array.

The use of binary search significantly optimizes the performance of the solution, especially when dealing with large data sets where linear search would be too slow. It reduces the potential searches from linear time complexity (O(n)) to logarithmic time complexity (O(log n)), for each block search.

When using the bisect_left function, the key function provided is essential. It acts as a predicate to tell bisect_left when to stop and find an index j where the value at j no longer equals x (nums.at(j) != x). This binary search is within the range from the current index i to the end of the array n.

Thus, the algorithm's efficiency stems from its ability to jump over contiguous segments of repeated values and count blocks without individually checking each element within a block.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's consider a BigArray represented by nums which contains the following array of integers:

1nums: [2, 2, 3, 3, 3, 6, 6, 6, 6, 7, 7, 10]

We want to count the number of maximal blocks of equal values. Here's a step-by-step walkthrough of the solution:

  1. Initialize i to index 0 and ans (the block counter) to 0. The array size n is 12.
  2. Since i < n, we enter the loop for the first time.
  3. We increment ans to 1 because nums.at(i) (which is 2 now) starts a new block.
  4. The next element nums.at(i+1) is also 2, so we perform a binary search to find the left boundary of the next block. In this case, binary search finds that the value changes at index 2. We update i to 2.
  5. We're now looking at the second block starting with a value of 3. Increment ans to 2.
  6. The next element nums.at(i+1) is 3, so once again, we perform a binary search to find the next value change. This time it happens at index 5, and i is updated to 5.
  7. Repeat these steps for the values of 6, 7, and finally 10.
    • For the block of 6's, ans becomes 3, and i jumps to 9.
    • Then for 7's, ans increases to 4, and i goes to 11.
    • Finally, for the solo value of 10, ans becomes 5, and since there are no more elements, the loop ends.

The final count ans is 5, which means there are 5 blocks of equal values in the provided array nums.

Solution Implementation

1# Definition for BigArray remains unchanged.
2# class BigArray:
3#     def at(self, index: int) -> int:
4#         pass
5#     def size(self) -> int:
6#         pass
7
8from bisect import bisect_left
9from typing import Optional
10
11class Solution:
12    def count_blocks(self, nums: Optional["BigArray"]) -> int:
13        """Counts the number of contiguous blocks of identical elements in the nums BigArray."""
14        index, size = 0, nums.size()  # Initialize the index and get the size of BigArray.
15        block_count = 0  # Initialize the count of contiguous blocks.
16      
17        # Iterate through the array.
18        while index < size:
19            block_count += 1  # Increment block count for each new block found.
20            element = nums.at(index)  # Get the element at the current index.
21          
22            # Condition to check if we are within bounds and if the next element is different.
23            if index + 1 < size and nums.at(index + 1) != element:
24                index += 1
25            else:
26                # Use binary search to find the index of the next different element.
27                # bisect_left will find the leftmost value exactly matching the key.
28                # The range object is used here as a sequence input for the bisect_left function.
29                index += bisect_left(range(index, size), True, key=lambda j: nums.at(j) != element)
30      
31        return block_count  # Return the total number of blocks.
32
33# Additional notes:
34# The `bisect_left` function is used to find the first index where `nums.at(j) != element` is True.
35# The `range(index, size)` is given to the `bisect_left` as a sequence over which it performs binary search.
36# The lambda function is used as a key to the bisect_left function to decide if the condition is met.
37
1class Solution {
2
3    /**
4     * This method counts the number of blocks with the same value in a BigArray.
5     *
6     * @param nums A BigArray object which contains the elements in which we need to find blocks.
7     * @return The number of blocks with the same value.
8     */
9    public int countBlocks(BigArray nums) {
10        int count = 0; // Initialize block count to zero
11
12        // Iterate over the elements of the BigArray starting from the first index
13        for (long i = 0, totalSize = nums.size(); i < totalSize; ++count) {
14            // Find the next starting index of a 'new' value block, increasing block count
15            i = findNextBlockStart(nums, i, totalSize);
16        }
17
18        // Return the total number of blocks found
19        return count;
20    }
21
22    /**
23     * Finds the starting index of the next distinct value block.
24     *
25     * @param nums A BigArray object to search within.
26     * @param start The index to start searching from.
27     * @param totalSize The total size of the BigArray.
28     * @return The starting index of the next block.
29     */
30    private long findNextBlockStart(BigArray nums, long start, long totalSize) {
31        long end = totalSize;  // Set the end index to the total size of the BigArray
32        int currentValue = nums.at(start);  // Get the value of the start index
33      
34        // Perform binary search to find the end index of the current value block
35        while (start < end) {
36            long mid = (start + end) >> 1; // Find the mid index by right shifting the sum of start and end
37          
38            // If the mid index has a different value, that's a potential new block, so move end to mid
39            if (nums.at(mid) != currentValue) {
40                end = mid;
41            } else {
42                // Otherwise, the current block continues, so move start one index past mid
43                start = mid + 1;
44            }
45        }
46
47        // Return the starting index of the next block (after the end of the current block)
48        return start;
49    }
50}
51
1/**
2 * Definition for BigArray.
3 * The class provides an interface for arrays with a potentially very large number of elements.
4 * It includes methods to construct a BigArray, retrieve a value at a given index, and get the size of the array. 
5 */
6class BigArray {
7public:
8    // Constructor that initializes the BigArray with the provided elements.
9    BigArray(vector<int> elements);
10  
11    // Returns the element at the specified index.
12    int at(long long index);
13  
14    // Returns the total size (number of elements) of the BigArray.
15    long long size();
16};
17
18
19class Solution {
20public:
21    // Counts the number of contiguous blocks of identical elements within the BigArray.
22    int countBlocks(BigArray* nums) {
23        int blockCount = 0; // Initialize the count of blocks
24        using ll = long long; // Alias for long long to simplify typing
25        ll n = nums->size(); // Get the total size of the BigArray
26
27        // Lambda function to find the next boundary where the value changes in the BigArray.
28        auto findNextBoundary = [&](ll leftIndex) {
29            ll rightIndex = n; // Set the search's right boundary to the end of the array
30            int currentValue = nums->at(leftIndex); // Get the value at the current leftIndex
31            while (leftIndex < rightIndex) {
32                ll midpoint = (leftIndex + rightIndex) >> 1; // Compute the midpoint for binary search
33                if (nums->at(midpoint) != currentValue) {
34                    // If the value at the midpoint is different, search to the left
35                    rightIndex = midpoint;
36                } else {
37                    // If the value is the same, search to the right
38                    leftIndex = midpoint + 1;
39                }
40            }
41            return leftIndex; // Return the boundary where the value changes
42        };
43
44        // Iterate through the BigArray and count the contiguous blocks
45        for (ll i = 0; i < n; ++blockCount) {
46            // Each search returns the start of the next block, which becomes the new i
47            i = findNextBoundary(i);
48        }
49        return blockCount; // Return the total number of contiguous blocks found
50    }
51};
52
1// Define the type for a BigArray for better understanding. This type should align with
2// the provided information about the BigArray class in the initial code comments.
3interface BigArray {
4    at(index: number): number;
5    size(): number;
6}
7
8/**
9 * Counts the number of distinct continuous subarrays where the value is constant,
10 * within a given BigArray.
11 * 
12 * @param {BigArray} bigArray An instance of BigArray that contains the numbers
13 *                            we want to analyze.
14 * 
15 * @return {number} Returns the number of constant-value subarrays (blocks).
16 */
17function countBlocks(bigArray: BigArray | null): number {
18    if (bigArray === null) {
19        return 0; // If the input is null, there are no blocks to count.
20    }
21
22    const totalSize = bigArray.size();
23
24    /**
25     * Searches for the right boundary of a block with the same values that starts at index `left`.
26     * 
27     * @param {number} left Left boundary index where the same value block starts.
28     * 
29     * @return {number} Returns the non-inclusive right boundary index of the block.
30     */
31    const searchRightBoundary = (left: number): number => {
32        let right = totalSize;
33        const valueAtLeft = bigArray.at(left);
34
35        // Binary search to find the non-inclusive right boundary index where the value changes.
36        while (left < right) {
37            const mid = left + Math.floor((right - left) / 2);
38            if (bigArray.at(mid) !== valueAtLeft) {
39                right = mid;
40            } else {
41                left = mid + 1;
42            }
43        }
44        return left;
45    };
46
47    let count = 0; // Initialize the count of blocks to 0.
48    let currentIndex = 0; // Start from the first index of the BigArray.
49
50    // Iterate until the currentIndex reaches the end of the BigArray.
51    while (currentIndex < totalSize) {
52        // Find the next block's right boundary and assign it as the new currentIndex.
53        currentIndex = searchRightBoundary(currentIndex);
54        count++; // Increment the count for each block found.
55    }
56
57    return count; // Return the total count of distinct blocks.
58}
59

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(m * log n), where m is the number of distinct elements in the nums BigArray, and n is the size of nums. This is because for every unique value x in the array, the code performs a binary search using bisect_left to find the next index where the value of nums.at(j) is different from x. Given that binary search has a time complexity of O(log n), and this is done for m distinct elements, the total time complexity is O(m * log n).

Space Complexity

The space complexity of the code is O(1) because the algorithm uses a fixed number of variables i, n, ans, and x, and does not create any auxiliary data structures that grow with the input size. This means that the space used remains constant regardless of the size of the input array nums.

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


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄