Review the fundamentals: Arrays guide and time complexities.

First Duplicate Node — Problem Statement & Solution Guide

ArraysEasyLinear Scan

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the First Duplicate Node problem optimally.

TopicArrays

PatternLinear Scan

TimeO(n)

SpaceO(n)

Problem Description

Given an integer array nodeIds, scan it from left to right and return the value of the first element that appears for the second time. If the scan finishes without encountering any repeated value, return null. The algorithm must run in linear time and may use O(n) extra memory for bookkeeping.

DSA Pattern Breakdown

"First Duplicate Node"

easy

WHY DOES IT MATTER?

Detecting the first duplicate in a stream is a fundamental pattern for de‑duplication, early error detection, and ensuring data integrity. Mastering this pattern equips engineers to handle real‑time validation tasks where the cost of a missed duplicate can be high (e.g., double‑charging a customer).

OPTIMIZATION CHALLENGE

The breakthrough is realizing that you don't need to compare every pair; you only need constant‑time membership checks. By storing each seen value in a hash set, you reduce the problem from quadratic to linear time while only paying a linear space cost.

REAL-WORLD CONNECTION

Think of a network router that must drop the first retransmitted packet it sees to avoid congestion. The router keeps a short‑lived hash of packet identifiers; when a packet arrives that already exists in the hash, it is flagged as a duplicate and discarded—mirroring the first‑duplicate‑node algorithm.

During an interview, explicitly state the trade‑off: O(n) time with O(n) extra space versus O(n²) time with O(1) space. Then walk through a quick dry‑run on a small example to demonstrate that you understand the “first‑seen‑again” semantics.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem of finding the first duplicate element while scanning an array from left to right is a classic example of a linear‑time detection task that can be solved with constant‑time membership checks. A naive double‑loop solution would compare each element with every later element, leading to O(n²) time, which quickly becomes prohibitive for large data sets such as log streams, user‑ID feeds, or telemetry buffers. The inefficiency stems from repeatedly scanning portions of the array that have already been examined, causing redundant work.

The optimal paradigm leverages a hash‑based auxiliary structure—typically a Set or a hash map—to record every value as it is encountered. Because hash look‑ups and insertions run in amortized O(1) time, each array element is processed exactly once: we check if the value already exists in the set, and if it does, we have found the first duplicate; otherwise we add it to the set and continue. This yields an overall O(n) time complexity while using O(n) extra space in the worst case (when no duplicates exist). The approach scales gracefully to millions of entries and aligns with the “single‑pass, constant‑time lookup” design pattern that underpins many real‑world streaming algorithms.

From an algorithmic theory perspective, this technique exemplifies the trade‑off between time and auxiliary space: by allocating linear extra memory we avoid the quadratic blow‑up of the brute‑force method. It also demonstrates the power of hash‑based data structures for membership queries, a cornerstone concept in computer science that appears in bloom filters, caching layers, and duplicate‑detection pipelines.

Interview Questions on This Problem

Q1How would you modify the solution if the array could contain negative numbers and you were restricted to O(1) extra space?

If the values are bounded (e.g., within the range of array indices) you can reuse the input array as a visitation map by marking visited positions with a sentinel (like negating the value at the indexed position). For arbitrary negatives without extra space, you would need to sort the array first (O(n log n)) or use a two‑pointer technique after sorting, which sacrifices the O(n) time guarantee.

Q2A fintech platform processes transaction IDs in real time and must flag the first repeated ID within a sliding window of 10,000 entries. Which data structure would you choose and why?

A hash set combined with a queue (or deque) works well: the queue maintains the order of the last 10,000 IDs, while the set provides O(1) duplicate checks. When the window slides, you dequeue the oldest ID and remove it from the set, ensuring memory stays bounded while still detecting the first repeat in the current window.

Q3Why is the first‑duplicate‑node problem often asked in high‑growth startups, and what does it reveal about a candidate’s problem‑solving style?

Startups value engineers who can write clean, linear‑time code that scales with data volume. This problem forces candidates to recognize when a brute‑force solution is unacceptable, choose the right hash‑based abstraction, and articulate trade‑offs between time and space—key skills for building performant services under tight resource constraints.

Examples

Example 1

Input

[3,1,4,2,5,1,6]

Output

Explanation: Traverse: 3 (first), 1 (first), 4, 2, 5, then 1 appears again – this is the earliest second occurrence, so return 1.

Example 2

Input

[7,8,9,10]

Output

null

Explanation: All numbers are seen only once; after the full scan no duplicate is found, thus return null.

Example 3

Input

[5,5,5,5]

Output

Explanation: The second element repeats 5, making it the first duplicate encountered, so the answer is 5.

Constraints

1 <= nodeIds.length <= 200000
-1000000000 <= nodeIds[i] <= 1000000000
Expected time complexity: O(n)
Expected auxiliary space: O(n)

Optimal Approach & Strategy

Maintain a hash set while iterating once through the array; if the current value is already in the set, return it immediately, otherwise insert it. This yields O(n) time with O(n) extra space.

Brute Force Approach

Use two nested loops: for each element, scan the rest of the array to see if it appears again. This checks every pair and runs in O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
function firstDuplicate(nodeIds) {
    const seen = new Set();
    for (const v of nodeIds) {
        if (seen.has(v)) return v;
        seen.add(v);
    }
    return null;
}
function main() {
    const data = fs.readFileSync(0, 'utf8').trim();
    if (data.length === 0) {
        console.log('null');
        return;
    }
    const arr = data.split(/\s+/).map(Number);
    const result = firstDuplicate(arr);
    console.log(result === null ? 'null' : result);
}
main();

#include <bits/stdc++.h>
using namespace std;

int firstDuplicate(const vector<int>& nodeIds) {
    unordered_set<int> seen;
    for (int v : nodeIds) {
        if (seen.count(v)) return v;
        seen.insert(v);
    }
    return INT_MIN; // sentinel indicating no duplicate
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> nodeIds;
    int x;
    while (cin >> x) {
        nodeIds.push_back(x);
    }
    int res = firstDuplicate(nodeIds);
    if (res == INT_MIN) cout << "null";
    else cout << res;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static Integer firstDuplicate(int[] nodeIds) {
        Set<Integer> seen = new HashSet<>();
        for (int v : nodeIds) {
            if (seen.contains(v)) return v;
            seen.add(v);
        }
        return null;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        List<Integer> list = new ArrayList<>();
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            for (String part : line.split("\\s+")) {
                list.add(Integer.parseInt(part));
            }
        }
        int[] arr = list.stream().mapToInt(i -> i).toArray();
        Integer ans = firstDuplicate(arr);
        System.out.println(ans == null ? "null" : ans);
    }
}

import sys

def first_duplicate(node_ids):
    """Return the first element that appears for the second time.
    If no such element exists, return None.
    """
    seen = set()
    for v in node_ids:
        if v in seen:
            return v
        seen.add(v)
    return None

if __name__ == "__main__":
    data = sys.stdin.read().strip().split()
    node_ids = list(map(int, data)) if data else []
    res = first_duplicate(node_ids)
    print('null' if res is None else res)

const fs = require('fs');
function firstDuplicate(nodeIds) {
    const seen = new Set();
    for (const v of nodeIds) {
        if (seen.has(v)) return v;
        seen.add(v);
    }
    return null;
}
function main() {
    const data = fs.readFileSync(0, 'utf8').trim();
    if (data.length === 0) {
        console.log('null');
        return;
    }
    const arr = data.split(/\s+/).map(Number);
    const result = firstDuplicate(arr);
    console.log(result === null ? 'null' : result);
}
main();

Asked in Top Tech Interviews

Infosys

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.