2936. Number of Equal Numbers Blocks

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