Find Array Distinct Elements — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums. Construct and return a new array that contains each value from nums exactly once, preserving the order of their first appearance. While scanning nums from left to right, the first time a value is encountered it should be copied to the result; any later occurrences of the same value are ignored. The returned array therefore consists of the distinct elements of the original array in the same relative order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Find Array Distinct Elements"
WHY DOES IT MATTER?
Deduplication with order preservation is a foundational pattern for data cleaning, log processing, and any pipeline where idempotent streams must be collapsed without losing temporal semantics.
OPTIMIZATION CHALLENGE
The key insight is to replace the O(n) scan for each element with a constant‑time membership test by storing previously seen values in a hash set, turning a quadratic process into a linear one.
REAL-WORLD CONNECTION
Think of a distributed event bus where each event carries a unique ID; a consumer must process each ID only once, but must respect the order events were first seen to maintain causal consistency.
During an interview, write the hash‑set solution first, then discuss edge cases (empty array, negative numbers, large inputs) and optionally mention the sorted‑array O(1)‑space shortcut to show depth.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
The problem is a classic example of deduplication while preserving order, which can be modeled as a streaming filter: as each element arrives, we decide whether to emit it based on whether we have seen it before. A naive solution would compare each element with all previously emitted ones, leading to O(n²) time on large inputs because each new element incurs a linear scan of the result list. The optimal paradigm leverages a hash‑based set (or a boolean map for bounded integer ranges) to achieve constant‑time membership checks, allowing a single left‑to‑right pass that records the first occurrence of each value and discards subsequent duplicates, yielding O(n) time and O(k) auxiliary space where k is the number of distinct elements.
Interview Questions on This Problem
Q1How would you modify the solution if the input array is sorted in non‑decreasing order?
When the array is sorted, duplicates appear consecutively, so we can solve the problem in O(1) extra space by scanning once and copying each element that differs from the previous one; no hash set is needed.
Q2What changes are required if the array can contain up to 10⁹ distinct 32‑bit integers and memory is limited to O(√n) extra space?
We would need to use a streaming algorithm such as a Bloom filter to approximate membership or process the array in chunks, writing distinct elements of each chunk to disk and then merging while eliminating cross‑chunk duplicates, trading exactness for space.
Q3Explain how you would extend the algorithm to return the index of the first occurrence for each distinct value.
Maintain a hash map from value to its first index; when encountering a value not yet in the map, store the current index. After the pass, iterate over the map’s insertion order (or store keys in a list) to produce the required index list.
Examples
Input
[4,5,4,2,5,1]
Output
[4,5,2,1]
Explanation: Traverse the list: 4 → added, 5 → added, 4 again → already seen, 2 → added, 5 again → already seen, 1 → added. The collected distinct values are [4,5,2,1].
Input
[10,-3,10,10,-3,7]
Output
[10,-3,7]
Explanation: Scanning left to right: 10 (new) → keep, -3 (new) → keep, next 10 → duplicate, next 10 → duplicate, -3 → duplicate, 7 (new) → keep. Resulting array is [10,-3,7].
Input
[0]
Output
[0]
Explanation: The array contains a single element, which is automatically distinct, so the output is the same single‑element array.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The algorithm should run in O(n) time and use O(n) additional memory in the worst case.
Optimal Approach & Strategy
Use a hash set to store values that have already been added to the result. As you traverse the array once, add an element to the result only if the set does not contain it, achieving O(n) time.
Brute Force Approach
Iterate through the array and for each element, scan the result list to check if it already exists; if not, append it. This double loop leads to O(n²) time on large inputs.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number[]}
*/
var distinctElements = function(nums) {
const seen = new Set();
const result = [];
for (const num of nums) {
if (!seen.has(num)) {
seen.add(num);
result.push(num);
}
}
return result;
};class Solution {
public:
vector<int> distinctElements(vector<int>& nums) {
unordered_set<int> seen;
vector<int> result;
for (int num : nums) {
if (seen.find(num) == seen.end()) {
seen.insert(num);
result.push_back(num);
}
}
return result;
}
};class Solution {
public int[] distinctElements(int[] nums) {
Set<Integer> seen = new HashSet<>();
List<Integer> result = new ArrayList<>();
for (int num : nums) {
if (seen.add(num)) {
result.add(num);
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution:
def distinctElements(self, nums: List[int]) -> List[int]:
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
return result/**
* @param {number[]} nums
* @return {number[]}
*/
var distinctElements = function(nums) {
const seen = new Set();
const result = [];
for (const num of nums) {
if (!seen.has(num)) {
seen.add(num);
result.push(num);
}
}
return result;
};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.