NEW OR EXISTING ID — Problem Statement & Solution Guide

ArraysMedium

TimeO(n)

SpaceO(n)

Problem Description

You are managing a registry of unique integer identifiers. Given an array ids representing the currently registered identifiers and a target integer newId, determine the final state of the registry after attempting to register newId.

If newId is already present in the ids array, the registry remains unchanged. If newId is not present, it must be appended to the end of the array. Return the resulting array of identifiers.

The operation must be performed in-place or by constructing a new array that reflects the final state of the registry.

DSA Pattern Breakdown

"NEW OR EXISTING ID"

medium

WHY DOES IT MATTER?

The hash-table membership pattern is essential because it transforms a linear-time operation into constant-time, which is critical for scalability and low latency in real-world systems.

OPTIMIZATION CHALLENGE

The key insight is to precompute a hash set from the array, turning an O(n) scan into an O(1) lookup, and then perform a single append if needed.

REAL-WORLD CONNECTION

Think of a library catalog: instead of scanning every book to find a title, you use an index (hash table) that points directly to the book's location, dramatically speeding up searches.

When explaining this to an interviewer, emphasize the trade-off between time and space, and mention that the hash set construction is a one-time cost that pays off for many subsequent queries.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to a membership test followed by an optional append. A naive solution scans the array linearly for the target, yielding O(n) time and O(1) space. While this is acceptable for small inputs, it becomes costly when the registry grows to millions of IDs, as each registration attempt requires a full scan. The optimal paradigm leverages a hash-based set to achieve average-case O(1) lookup time. By constructing a hash set from the array once (O(n) time, O(n) space), we can test membership instantly and append only when necessary, keeping the overall complexity linear in the size of the input but with a constant factor that is far smaller than repeated scans.

This approach is a classic example of the "hash table for membership queries" pattern. It trades a modest amount of additional memory for a dramatic reduction in time, which is essential in systems where registration latency must remain low under heavy load. Moreover, the pattern scales gracefully: as the registry grows, the cost of a single lookup stays constant, whereas a linear scan would grow proportionally.

In distributed or concurrent environments, the same principle applies: a distributed hash map or a Bloom filter can provide probabilistic or deterministic membership checks with sub-linear time, enabling high-throughput registration services without bottlenecking on array scans.

Interview Questions on This Problem

Q1How would you handle duplicate ID checks in a high-traffic registration service where IDs are stored in a relational database?

I would use a unique constraint on the ID column to enforce uniqueness at the database level, and perform a single SELECT to check existence before INSERT. If the SELECT returns a row, I skip insertion; otherwise, I insert. This ensures atomicity and leverages the database's indexing for O(log n) lookup.

Q2In a fintech platform, you need to validate transaction IDs in real-time. What data structure would you choose for fast membership checks, and why?

I would use a concurrent hash set (e.g., ConcurrentHashMap in Java) or a lock-free hash table to allow multiple threads to check and insert IDs concurrently. This provides average-case O(1) lookup and insertion while avoiding contention in a high-throughput environment.

Q3A startup is building a microservice that registers user session tokens. They want to avoid storing all tokens in memory. What trade-offs can you propose?

Use a Bloom filter to probabilistically test membership with low memory overhead, accepting a small false-positive rate. For false positives, fall back to a persistent store or a secondary check. This balances memory usage against occasional extra lookups.

Examples

Example 1

Input

ids = [10, 20, 30], newId = 20

Output

[10, 20, 30]

Explanation: The target identifier 20 is already present at index 1 in the array. Since the ID exists, no modification is made. The original array is returned as is.

Example 2

Input

ids = [10, 20, 30], newId = 40

Output

[10, 20, 30, 40]

Explanation: The target identifier 40 is not found in the array. Therefore, it is appended to the end of the list. The resulting array contains the original elements followed by 40.

Example 3

Input

ids = [5], newId = 5

Output

[5]

Explanation: The array contains a single element, 5. The newId is also 5. Since the ID already exists, the array remains unchanged.

Example 4

Input

ids = [], newId = 100

Output

[100]

Explanation: The input array is empty. The newId 100 is not present (trivially). It is appended to the empty array, resulting in an array containing only 100.

Constraints

0 <= ids.length <= 10^5
-10^9 <= ids[i] <= 10^9
-10^9 <= newId <= 10^9

Optimal Approach & Strategy

Build a hash set from the array for O(1) membership checks, then append newId only if it’s absent. This keeps time linear overall and uses O(n) additional space.

Brute Force Approach

Scan the array from start to finish to see if newId exists; if not, append it. This takes O(n) time for each check and uses no extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} ids
 * @param {number} newId
 * @return {number[]}
 */
var registerId = function(ids, newId) {
    if (ids.includes(newId)) {
        return ids;
    }
    ids.push(newId);
    return ids;
};

class Solution {
public:
    vector<int> registerId(vector<int>& ids, int newId) {
        for (int id : ids) {
            if (id == newId) {
                return ids;
            }
        }
        ids.push_back(newId);
        return ids;
    }
};

class Solution {
    public List<Integer> registerId(int[] ids, int newId) {
        List<Integer> list = new ArrayList<>();
        for (int id : ids) {
            list.add(id);
            if (id == newId) {
                return list;
            }
        }
        list.add(newId);
        return list;
    }
}

class Solution:
    def registerId(self, ids: List[int], newId: int) -> List[int]:
        if newId in ids:
            return ids
        ids.append(newId)
        return ids

/**
 * @param {number[]} ids
 * @param {number} newId
 * @return {number[]}
 */
var registerId = function(ids, newId) {
    if (ids.includes(newId)) {
        return ids;
    }
    ids.push(newId);
    return ids;
};

Asked in Top Tech Interviews

PhonePe

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.

NEW OR EXISTING ID Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

NEW OR EXISTING ID — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor