Welcome to Subscribe On Youtube

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

Thinking

A special integer is one that forms exactly one contiguous equal block. Collecting every index of each value just to test contiguity would store extra lists.

A scan increments a counter at the start of each block; afterwards we count how many values have counter $1$.

The universe has size $100$, so a frequency table suffices.

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.

  • 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;
    }
}


  • 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);
    }
};


  • 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())


  • 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
}


  • 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;
}

All Problems

All Solutions