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:
- From the current index, we check the next value. If it's different, this is already the end of a block.
- 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 theat
method of theBigArray
. - 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:
- Initialize an index
i
at 0 and a counterans
to 0 to keep the tally of blocks encountered. - Loop until
i
is less than the sizen
of theBigArray
. - For each iteration of the loop:
- Increment the block counter
ans
since the element at indexi
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 fromx
, it implies the current block is of size 1. So, incrementi
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 fromx
. Use thebisect_left
method combined with a key function that leveragesnums.at(j)
to perform the binary search efficiently. c. Update the indexi
to the boundary index found using the binary search. This skips the entire block of identical elements in one step.
- Increment the block counter
- 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a BigArray
represented by nums
which contains the following array of integers:
nums: [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:
- Initialize
i
to index 0 andans
(the block counter) to 0. The array sizen
is 12. - Since
i < n
, we enter the loop for the first time. - We increment
ans
to 1 becausenums.at(i)
(which is 2 now) starts a new block. - 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 updatei
to 2. - We're now looking at the second block starting with a value of 3. Increment
ans
to 2. - 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, andi
is updated to 5. - Repeat these steps for the values of 6, 7, and finally 10.
- For the block of 6's,
ans
becomes 3, andi
jumps to 9. - Then for 7's,
ans
increases to 4, andi
goes to 11. - Finally, for the solo value of 10,
ans
becomes 5, and since there are no more elements, the loop ends.
- For the block of 6's,
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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!