Count Integers Appearing in a Single Block - Solution & Explanation

Easy5 min read

Practice this problem

Problem Statement

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

Solution

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 nums[i] neq nums[i - 1], position i starts a new block, and we increment cnt[nums[i]]. After the traversal, the answer is the number of integers whose count in 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 nums, and M = 100 is the maximum value in the array.