First Duplicate Node — Problem Statement & Solution Guide
Problem Description
Given an array of integers nodeIds of size n, containing unique identifiers for surveillance nodes, find the first duplicate node ID found, which represents the breached node. If no duplicates are found, return null.
Examples
Input
[2, 1, 2, 5, 3, 2]
Output
2
Explanation: Step-by-step: with input [2, 1, 2, 5, 3, 2], we iterate through the array and keep track of the node IDs we've seen. The first duplicate node ID we encounter is 2, so we return 2.
Input
[1, 3, 4, 5, 6]
Output
null
Explanation: Step-by-step: with input [1, 3, 4, 5, 6], we iterate through the array and keep track of the node IDs we've seen. Since there are no duplicates, we return null.
Constraints
- 1 <= n <= 10^5
- array elements are 0 or 1.
Optimal Approach & Strategy
The optimized approach involves using a linear scan with a time complexity of O(n) to find the breached node.
Brute Force Approach
The brute force approach involves checking each node in the grid one by one to find the breached node.
Verified Code Solutions
function solution(nodeIds) {
const seen = new Set();
for (const id of nodeIds) {
if (seen.has(id)) {
return id;
}
seen.add(id);
}
return null;
}class Solution {
public:
int solution(vector<int>& nodeIds) {
unordered_set<int> seen;
for (int id : nodeIds) {
if (seen.find(id) != seen.end()) {
return id;
}
seen.insert(id);
}
return -1; // equivalent to null in other languages
}
};import java.util.HashSet;
import java.util.Set;
class Solution {
public Integer solution(int[] nodeIds) {
Set<Integer> seen = new HashSet<>();
for (int id : nodeIds) {
if (seen.contains(id)) {
return id;
}
seen.add(id);
}
return null;
}
}def solution(nodeIds):
seen = set()
for id in nodeIds:
if id in seen:
return id
seen.add(id)
return Nonefunction solution(nodeIds) {
const seen = new Set();
for (const id of nodeIds) {
if (seen.has(id)) {
return id;
}
seen.add(id);
}
return null;
}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.