Distinct Intensity Counts — Problem Statement & Solution Guide
Problem Description
You are provided with an array of integers named intensities, which represents a sequence of measured signal amplitudes recorded over time. Your task is to compute the total number of distinct amplitude values present in the sequence. Two measurements are considered identical if and only if their integer values are exactly equal.
The input will be a single array of integers. The output must be a single integer representing the count of unique values found within the array. If the array is empty, the count is zero. If all elements are identical, the count is one. If all elements are different, the count equals the length of the array.
This problem requires an efficient approach to handle large input sizes. A brute-force comparison of every pair of elements would be computationally expensive. Instead, leverage data structures that allow for O(1) average-time complexity lookups to track seen values.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Distinct Intensity Counts"
WHY DOES IT MATTER?
Counting distinct elements is a fundamental pattern for deduplication, frequency analysis, and data compression. Mastery of this pattern enables engineers to efficiently handle large streams of telemetry, logs, or user events where uniqueness matters.
OPTIMIZATION CHALLENGE
The key insight is recognizing that uniqueness can be enforced during a single pass by leveraging a data structure that offers O(1) average insertion and lookup, thereby eliminating the need for nested comparisons or multiple scans.
REAL-WORLD CONNECTION
In distributed monitoring systems, each sensor emits readings that must be aggregated without double‑counting. Using a hash set at the aggregator mirrors how a central service de‑duplicates IDs before persisting metrics.
During an interview, first state the naive O(n^2) idea, then immediately pivot to the hash‑set solution, emphasizing expected O(n) time and clarifying assumptions about hash collisions and memory limits.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem of counting distinct values in an array is a classic application of set theory in algorithm design. A naive solution would iterate over each element and compare it with every other element, leading to O(n^2) time, which quickly becomes infeasible for large n (e.g., n > 10^5). The optimal paradigm leverages hash‑based data structures (such as HashSet) or sorting to achieve linear or near‑linear performance. By inserting each element into a hash set, duplicates are automatically discarded because the set maintains only unique keys, resulting in O(n) expected time and O(n) additional space. Alternatively, sorting the array first (O(n log n)) and then scanning once to count value changes also yields O(1) extra space if the sort is in‑place, but the hash‑set approach is generally preferred for its simplicity and true linearity on average.
Interview Questions on This Problem
Q1How would you modify your solution if the input array is read-only and you cannot use extra space beyond O(1)?
You would sort the array in‑place using an O(n log n) algorithm (e.g., quicksort or heapsort) and then iterate once, counting a new distinct value each time the current element differs from the previous one. This respects the O(1) auxiliary space constraint.
Q2What are the trade‑offs between using a hash set versus sorting when counting distinct elements?
A hash set gives expected O(n) time with O(n) extra space and works well for unsorted data, but it relies on good hash functions and may have higher constant factors. Sorting costs O(n log n) time but can be done in‑place, reducing auxiliary space to O(1); however, it destroys the original order and may be slower for very large datasets.
Q3If the integer range is bounded (e.g., 0 ≤ intensity ≤ 10^6), how can you achieve O(n) time with O(1) additional space?
You can use a bitmap (bitset) of size equal to the range, setting the bit corresponding to each intensity. After processing, count the set bits. This uses O(range) bits, which is O(1) relative to the input size when the range is a fixed constant.
Examples
Input
intensities = [4, 2, 4, 7, 2, 9]
Output
4
Explanation: The unique values in the array are {2, 4, 7, 9}. The value 4 appears twice, and 2 appears twice, but they are counted only once each. The distinct values are 2, 4, 7, and 9, totaling 4 distinct intensities.
Input
intensities = [10, 10, 10, 10]
Output
1
Explanation: All elements in the array are identical (10). Therefore, there is only one unique signal strength present in the sequence.
Input
intensities = [-5, 0, 5, -5, 12, 0]
Output
4
Explanation: The array contains negative, zero, and positive integers. The unique values are {-5, 0, 5, 12}. The duplicates -5 and 0 do not increase the count. The total number of distinct values is 4.
Input
intensities = [1, 2, 3, 4, 5]
Output
5
Explanation: Every element in the array is unique. There are no duplicates. Therefore, the number of distinct intensities is equal to the length of the array, which is 5.
Constraints
- 1 <= intensities.length <= 10^5
- -10^9 <= intensities[i] <= 10^9
- The array may contain duplicate values.
- The array may contain negative integers, zero, and positive integers.
Optimal Approach & Strategy
Insert each element into a hash set (or sort the array first) and then return the size of the set, achieving linear or near‑linear time.
Brute Force Approach
Iterate over each element and compare it with every other element to check for duplicates, counting only those that never match another element.
Verified Code Solutions
function solution(intensities) { return new Set(intensities).size; }class Solution { public: int solution(vector<int>& intensities) { unordered_set<int> uniqueIntensities; for (int intensity : intensities) { uniqueIntensities.insert(intensity); } return uniqueIntensities.size(); } };import java.util.HashSet; import java.util.Set; class Solution { public int solution(int[] intensities) { Set<Integer> uniqueIntensities = new HashSet<>(); for (int intensity : intensities) { uniqueIntensities.add(intensity); } return uniqueIntensities.size(); } }def solution(intensities): return len(set(intensities))function solution(intensities) { return new Set(intensities).size; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.