Identify Unique Identifier — Problem Statement & Solution Guide

ArraysMedium

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array ids and an integer target_id, determine whether target_id appears in ids at least once. Return true if it is present; otherwise, return false. The solution must run in linear time relative to the size of ids and use only O(1) additional memory beyond the input storage.

DSA Pattern Breakdown

"Identify Unique Identifier"

medium

WHY DOES IT MATTER?

Linear scans are the canonical solution for membership queries when no ordering or hashing guarantees are available, teaching candidates to respect problem constraints and avoid over‑engineering.

OPTIMIZATION CHALLENGE

Recognizing that early termination is possible—stopping the scan the moment the target is encountered—reduces average‑case work and satisfies the O(1) space bound.

REAL-WORLD CONNECTION

Think of a security guard checking a guest list at a venue entrance: they scan each name until they find a match, without needing to sort the list or build a separate database.

During an interview, write the loop with a clear break condition and avoid auxiliary containers; a one‑liner return (e.g., for‑each with early return) signals confidence and brevity.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to a membership test in an unsorted integer array. The most straightforward algorithm scans each element sequentially, comparing it to the target; this is a linear‑time algorithm that uses constant extra space because it only needs a loop index and a boolean flag. Naïve alternatives, such as sorting the array first or building auxiliary data structures like hash sets, either increase the time complexity to O(n log n) or consume O(n) extra memory, which violates the strict O(1) auxiliary‑space requirement for large‑scale inputs where memory bandwidth is a bottleneck. The optimal paradigm is the single‑pass linear scan, which leverages the fact that membership does not require ordering or pre‑processing—each element can be examined independently, and the scan can terminate early as soon as the target is found, yielding the best‑possible worst‑case runtime of Θ(n) while staying within constant auxiliary space.

Interview Questions on This Problem

Q1How would you modify the solution if the array were sorted and you needed to preserve O(1) extra space?

You could apply a binary search, which runs in O(log n) time and O(1) space, by repeatedly halving the search interval until the target is found or the interval is empty.

Q2What edge cases must you consider when implementing the linear scan for this problem?

Empty array, arrays containing only the target, and arrays with duplicate values; also ensure integer overflow does not affect comparison logic.

Q3In a distributed system where the array is sharded across multiple nodes, how can you efficiently determine if the target exists without moving data?

Each node performs a local O(m) scan on its shard (m = shard size) and returns a boolean; a coordinator aggregates the results with a logical OR, achieving overall O(N) time across the cluster while keeping network traffic O(number of nodes).

Examples

Example 1

Input

ids = [5, 3, 9, 5, 2], target_id = 9

Output

true

Explanation: The array contains the values 5,3,9,5,2. Scanning from left to right, the third element equals 9, which matches target_id, so the function returns true.

Example 2

Input

ids = [10, -1, 0, 4], target_id = 7

Output

false

Explanation: None of the elements 10, -1, 0, 4 equal 7. After examining all entries the target is not found, so the function returns false.

Example 3

Input

ids = [1000000000, -1000000000, 123456789], target_id = -1000000000

Output

true

Explanation: The second element of the array is -1000000000, which matches target_id, therefore the result is true.

Constraints

1 <= ids.length <= 100000
-1000000000 <= ids[i] <= 1000000000
-1000000000 <= target_id <= 1000000000

Optimal Approach & Strategy

Perform a single pass through the array, comparing each element to the target and exiting early on a match, achieving O(n) time and O(1) extra space.

Brute Force Approach

Check every pair of elements or use nested loops to compare each element with the target, leading to O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function identifyUniqueIdentifier(ids, target_id) {
    for (let i = 0; i < ids.length; i++) {
        if (ids[i] === target_id) {
            return true;
        }
    }
    return false;
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const ids = lines[1].split(' ').map(Number);
    const target_id = parseInt(lines[2]);
    
    const result = identifyUniqueIdentifier(ids, target_id);
    console.log(result ? "true" : "false");
});

#include <iostream>
#include <vector>

using namespace std;

bool identifyUniqueIdentifier(vector<int>& ids, int target_id) {
    for (int id : ids) {
        if (id == target_id) {
            return true;
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> ids(n);
    for (int i = 0; i < n; i++) {
        cin >> ids[i];
    }
    int target_id;
    cin >> target_id;
    
    bool result = identifyUniqueIdentifier(ids, target_id);
    cout << (result ? "true" : "false") << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static boolean identifyUniqueIdentifier(int[] ids, int target_id) {
        for (int id : ids) {
            if (id == target_id) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] ids = new int[n];
        for (int i = 0; i < n; i++) {
            ids[i] = scanner.nextInt();
        }
        int target_id = scanner.nextInt();
        
        boolean result = identifyUniqueIdentifier(ids, target_id);
        System.out.println(result ? "true" : "false");
        scanner.close();
    }
}

def identify_unique_identifier(ids, target_id):
    for id in ids:
        if id == target_id:
            return True
    return False

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    ids = list(map(int, data[1:n+1]))
    target_id = int(data[n+1])
    
    result = identify_unique_identifier(ids, target_id)
    print("true" if result else "false")

function identifyUniqueIdentifier(ids, target_id) {
    for (let i = 0; i < ids.length; i++) {
        if (ids[i] === target_id) {
            return true;
        }
    }
    return false;
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const ids = lines[1].split(' ').map(Number);
    const target_id = parseInt(lines[2]);
    
    const result = identifyUniqueIdentifier(ids, target_id);
    console.log(result ? "true" : "false");
});

Asked in Top Tech Interviews

Swiggy

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.

Identify Unique Identifier Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Identify Unique Identifier — 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