Skip to main content
Talentd

Count Integers Appearing in a Single Block - Solution & Explanation

EasyArrayHash TableCounting6 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

Approach Overview

Problem Overview: You are given an array of integers, and you need to count how many distinct integers appear in exactly one contiguous block (i.e., all occurrences of that integer are consecutive). For example, in [1,1,2,2,1], the integer 1 appears in two blocks, so it doesn't count; 2 appears in one block, so it counts.

Approach 1: Brute Force (O(n^2) time, O(n) space)

For each unique integer, scan the entire array to find the first and last occurrence. Then check if all occurrences between those indices are the same integer. This requires nested loops and a set to track visited numbers. It's straightforward but inefficient for large inputs. Use this only if you're unfamiliar with hash maps or when the array is very small.

Approach 2: Count Blocks per Integer (O(n) time, O(n) space)

Iterate through the array once, tracking the previous element. Whenever the current element differs from the previous one, you've started a new block for that integer. Use a hash map to store the number of blocks seen for each integer. After the loop, count how many integers have exactly one block. This is optimal because it processes each element once and uses constant-time hash lookups. This is the approach you should implement in interviews.

Recommended for interviews: Interviewers expect the hash map approach because it demonstrates your ability to use arrays and counting techniques efficiently. The brute force shows you understand the problem but lacks optimization. The O(n) solution is clean, easy to explain, and handles large inputs well.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(n)When array is very small or for simplicity
Count Blocks (Optimal)O(n)O(n)General case and interviews

Video Solutions (6)

Count Integers Appearing in a Single Block | Leetcode 4038 | Weekly Contest 517 | DRY RUN

VIJAY KUMAR [IIT-BHU]6:44199 views
Video 1 of 6

Frequently Asked Questions

Count Integers Appearing in a Single Block Python solution
In Python, use a dictionary to track block counts. Iterate with a for loop comparing each element to the previous one. Increment counts on changes. After the loop, sum values equal to 1.
Is Count Integers Appearing in a Single Block easy or hard?
It's rated Easy on FleetCode with a 45% acceptance rate. The problem is straightforward once you realize you only need to count transitions between different elements.
How to solve Count Integers Appearing in a Single Block in O(n)?
Initialize an empty hash map and a variable for the previous element. Iterate through the array; whenever the current element differs from the previous, increment the block count for that element in the map. Finally, count how many keys have a value of exactly 1.
What is the best approach for Count Integers Appearing in a Single Block?
The best approach is to iterate through the array once while tracking the previous element. Use a hash map to count how many blocks each integer appears in. After the loop, count integers with exactly one block. This runs in O(n) time and O(n) space.
Is Count Integers Appearing in a Single Block asked at Google/Amazon/Meta?
This problem is tagged as 'General' on FleetCode, so it may appear as an easy warm-up at companies like Amazon or Microsoft. It tests basic hash map usage and array traversal skills.
What data structure is used in Count Integers Appearing in a Single Block?
A hash map (or dictionary) is used to store the number of blocks for each integer. This allows O(1) average-time updates and lookups while scanning the array.
What is the time complexity of Count Integers Appearing in a Single Block?
The optimal solution runs in O(n) time because you traverse the array a single time. The space complexity is O(n) due to the hash map storing block counts for each distinct integer.

Ready to solve this problem?

Practice Count Integers Appearing in a Single Block with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays