Description#
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.
Example 1:
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:
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:
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 <= 10151 <= nums[i] <= 109- The input is generated such that all equal values are adjacent.
- The sum of the elements of
nums is at most 1015.
Solutions#
Solution 1: Binary Search#
We can use binary search to find the right boundary of each block. Specifically, we traverse the array from left to right. For each index $i$, we use binary search to find the smallest index $j$ such that all elements between $[i,j)$ are equal to $nums[i]$. Then we update $i$ to $j$ and continue to traverse the array until $i$ is greater than or equal to the length of the array.
The time complexity is $O(m \times \log n)$, where $m$ is the number of different elements in the array $num$, and $n$ is the length of the array $num$. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| # Definition for BigArray.
# class BigArray:
# def at(self, index: long) -> int:
# pass
# def size(self) -> long:
# pass
class Solution(object):
def countBlocks(self, nums: Optional["BigArray"]) -> int:
i, n = 0, nums.size()
ans = 0
while i < n:
ans += 1
x = nums.at(i)
if i + 1 < n and nums.at(i + 1) != x:
i += 1
else:
i += bisect_left(range(i, n), True, key=lambda j: nums.at(j) != x)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| /**
* Definition for BigArray.
* class BigArray {
* public BigArray(int[] elements);
* public int at(long index);
* public long size();
* }
*/
class Solution {
public int countBlocks(BigArray nums) {
int ans = 0;
for (long i = 0, n = nums.size(); i < n; ++ans) {
i = search(nums, i, n);
}
return ans;
}
private long search(BigArray nums, long l, long n) {
long r = n;
int x = nums.at(l);
while (l < r) {
long mid = (l + r) >> 1;
if (nums.at(mid) != x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /**
* Definition for BigArray.
* class BigArray {
* public:
* BigArray(vector<int> elements);
* int at(long long index);
* long long size();
* };
*/
class Solution {
public:
int countBlocks(BigArray* nums) {
int ans = 0;
using ll = long long;
ll n = nums->size();
auto search = [&](ll l) {
ll r = n;
int x = nums->at(l);
while (l < r) {
ll mid = (l + r) >> 1;
if (nums->at(mid) != x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (long long i = 0; i < n; ++ans) {
i = search(i);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* Definition for BigArray.
* class BigArray {
* constructor(elements: number[]);
* public at(index: number): number;
* public size(): number;
* }
*/
function countBlocks(nums: BigArray | null): number {
const n = nums.size();
const search = (l: number): number => {
let r = n;
const x = nums.at(l);
while (l < r) {
const mid = l + Math.floor((r - l) / 2);
if (nums.at(mid) !== x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
let ans = 0;
for (let i = 0; i < n; ++ans) {
i = search(i);
}
return ans;
}
|
Solution 2: Divide and Conquer#
We can use the divide and conquer method to calculate the answer. Specifically, we divide the array into two subarrays, recursively calculate the answer for each subarray, and then merge the answers. If the last element of the first subarray is equal to the first element of the second subarray, then we need to subtract one from the answer.
The time complexity is $O(\log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array $num$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* Definition for BigArray.
* class BigArray {
* public BigArray(int[] elements);
* public int at(long index);
* public long size();
* }
*/
class Solution {
public int countBlocks(BigArray nums) {
return f(nums, 0, nums.size() - 1);
}
private int f(BigArray nums, long l, long r) {
if (nums.at(l) == nums.at(r)) {
return 1;
}
long mid = (l + r) >> 1;
int a = f(nums, l, mid);
int b = f(nums, mid + 1, r);
return a + b - (nums.at(mid) == nums.at(mid + 1) ? 1 : 0);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /**
* Definition for BigArray.
* class BigArray {
* public:
* BigArray(vector<int> elements);
* int at(long long index);
* long long size();
* };
*/
class Solution {
public:
int countBlocks(BigArray* nums) {
using ll = long long;
function<int(ll, ll)> f = [&](ll l, ll r) {
if (nums->at(l) == nums->at(r)) {
return 1;
}
ll mid = (l + r) >> 1;
int a = f(l, mid);
int b = f(mid + 1, r);
return a + b - (nums->at(mid) == nums->at(mid + 1));
};
return f(0, nums->size() - 1);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* Definition for BigArray.
* class BigArray {
* constructor(elements: number[]);
* public at(index: number): number;
* public size(): number;
* }
*/
function countBlocks(nums: BigArray | null): number {
const f = (l: number, r: number): number => {
if (nums.at(l) === nums.at(r)) {
return 1;
}
const mid = l + Math.floor((r - l) / 2);
const a = f(l, mid);
const b = f(mid + 1, r);
return a + b - (nums.at(mid) === nums.at(mid + 1) ? 1 : 0);
};
return f(0, nums.size() - 1);
}
|
