Skip to content

2936. Number of Equal Numbers Blocks

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 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
/**
 * 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) {
    return countBlocks(nums, 0, nums->size() - 1, nums->at(0),
                       nums->at(nums->size() - 1));
  }

 private:
  // Returns the number of maximal blocks in nums[l..r].
  int countBlocks(BigArray* nums, long l, long r, int leftValue,
                  int rightValue) {
    if (leftValue == rightValue)  // nums[l..r] are identical.
      return 1;
    if (l + 1 == r)  // nums[l] != nums[r].
      return 2;
    const long m = (l + r) / 2;
    const int midValue = nums->at(m);
    // Substract nums[m], which will be counted twice.
    return countBlocks(nums, l, m, leftValue, midValue) +
           countBlocks(nums, m, r, midValue, rightValue) - 1;
  }
};

 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
/**
 * 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 countBlocks(nums, 0, nums.size() - 1, nums.at(0), nums.at(nums.size() - 1));
  }

  // Returns the number of maximal blocks in nums[l..r].
  private int countBlocks(BigArray nums, long l, long r, int leftValue, int rightValue) {
    if (leftValue == rightValue) // nums[l..r] are identical.
      return 1;
    if (l + 1 == r) // nums[l] != nums[r].
      return 2;
    final long m = (l + r) / 2;
    final int midValue = nums.at(m);
    // Substract nums[m], which will be counted twice.
    return countBlocks(nums, l, m, leftValue, midValue) +
        countBlocks(nums, m, r, midValue, rightValue) - 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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:
    def countBlocks(l: int, r: int, leftValue: int, rightValue: int) -> int:
      """Returns the number of maximal blocks in nums[l..r]."""
      if leftValue == rightValue:
        return 1
      if l + 1 == r:
        return 2
      m = (l + r) // 2
      midValue = nums.at(m)
      return (countBlocks(l, m, leftValue, midValue) +
              countBlocks(m, r, midValue, rightValue) - 1)
    # Substract nums[m], which will be counted twice.
    return countBlocks(0, nums.size() - 1,
                       nums.at(0), nums.at(nums.size() - 1))