Skip to content

4038. Count Integers Appearing in a Single Block

Description

You are given an integer array nums.

An integer x is special if all occurrences of x in nums appear in a single contiguous block.

Return the number of distinct special integers in nums.

Β 

Example 1:

Input: nums = [1,2,2,1]

Output: 1

Explanation:

  • 1 appears at indices 0 and 3, forming two separate blocks, so it is not special.
  • 2 appears in a single contiguous block at indices [1, 2], so it is special.

Therefore, there is one special integer.

Example 2:

Input: nums = [3,3,1,2,2,1]

Output: 2

Explanation:

  • 3 appears in a single contiguous block at indices [0, 1], so it is special.
  • 1 appears at indices 2 and 5, forming two separate blocks, so it is not special.
  • 2 appears in a single contiguous block at indices [3, 4], so it is special.

Therefore, there are two special integers.

Β 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Solutions

Solution 1: Count the Blocks of Each Integer

Call each maximal run of consecutive equal elements a block. An integer \(x\) is special if and only if it forms exactly one block.

So we traverse the array, and whenever \(i = 0\) or \(\textit{nums}[i] \neq \textit{nums}[i - 1]\), position \(i\) starts a new block, and we increment \(\textit{cnt}[\textit{nums}[i]]\). After the traversal, the answer is the number of integers whose count in \(\textit{cnt}\) is exactly \(1\).

The time complexity is \(O(n + M)\), and the space complexity is \(O(M)\). Here, \(n\) is the length of the array \(\textit{nums}\), and \(M = 100\) is the maximum value in the array.

1
2
3
4
class Solution:
    def countSpecialIntegers(self, nums: List[int]) -> int:
        cnt = Counter(x for i, x in enumerate(nums) if i == 0 or x != nums[i - 1])
        return sum(v == 1 for v in cnt.values())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int countSpecialIntegers(int[] nums) {
        int[] cnt = new int[101];
        for (int i = 0; i < nums.length; ++i) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                ++cnt[nums[i]];
            }
        }
        int ans = 0;
        for (int c : cnt) {
            if (c == 1) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int countSpecialIntegers(vector<int>& nums) {
        int cnt[101]{};
        for (int i = 0; i < nums.size(); ++i) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                ++cnt[nums[i]];
            }
        }
        return count(begin(cnt), end(cnt), 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func countSpecialIntegers(nums []int) int {
    cnt := [101]int{}
    for i, x := range nums {
        if i == 0 || x != nums[i-1] {
            cnt[x]++
        }
    }
    ans := 0
    for _, c := range cnt {
        if c == 1 {
            ans++
        }
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function countSpecialIntegers(nums: number[]): number {
    const cnt: number[] = Array(101).fill(0);
    for (let i = 0; i < nums.length; ++i) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            ++cnt[nums[i]];
        }
    }
    return cnt.filter(c => c === 1).length;
}

Comments