Lists, maps and the first repeated ID

What you will learn

• State an input/output contract before choosing a data structure.
• Find the first repeated positive integer ID with a seen map.
• Explain expected time, worst-case caveats and extra memory.

Theory: list, map and contract

A list is an ordered sequence of values. A map associates a key with a value. PHP uses an ordered-map array for both common roles; it is not the same memory representation as a compact C array. Numeric strings can become integer keys, so key identity must be chosen deliberately.

Our contract accepts a PHP list of integers from 1 to 1000000. It returns the ID whose second occurrence is encountered first while scanning left to right, or null if there is no repeat. It rejects any invalid element anywhere, even after an early duplicate. It does not sort, edit the input or query a database.

This helps with batch import checks and interview explanations. An in-memory duplicate check is not a replacement for a database unique constraint: another request can write between a check and an insert.

Worked example: first repeated ID

Required: PHP 8.4+ CLI. Save as duplicate_ids.php in a personal practice folder. No framework or database. Laragon/XAMPP are optional.

<?php

declare(strict_types=1);

function firstDuplicateId(array $ids): ?int
{
    if (! array_is_list($ids)) {
        throw new InvalidArgumentException('Provide a list of IDs.');
    }
    foreach ($ids as $id) {
        if (! is_int($id) || $id < 1 || $id > 1000000) {
            throw new InvalidArgumentException('Each ID must be an integer from 1 to 1000000.');
        }
    }

    $seen = [];
    foreach ($ids as $id) {
        if (array_key_exists($id, $seen)) {
            return $id;
        }
        $seen[$id] = true;
    }

    return null;
}

if (realpath($_SERVER['SCRIPT_FILENAME'] ?? '') === __FILE__) {
    foreach ([[41, 12, 41, 12], [8, 9, 10], []] as $ids) {
        $duplicate = firstDuplicateId($ids);
        echo 'Duplicate: '.($duplicate === null ? 'none' : $duplicate).PHP_EOL;
    }
}

Run and trace the map

Windows PowerShell:

php --version
php ./duplicate_ids.php

Ubuntu Bash:

php --version
php ./duplicate_ids.php

Duplicate: 41
Duplicate: none
Duplicate: none

The commands are the same except for the labelled shell; they require PHP on PATH. Windows PHP 8.4.26 was run. Ubuntu was not run.

For 41,12,41,12 the seen map starts empty, then contains 41, then 41 and 12. The next 41 is already a key, so the answer is 41. There is no need to look for the smallest repeated value. Requiring the file defines the function without running the printed demo.

Reason about time and space

Let n be the number of input IDs. A nested comparison with every earlier value can use n(n-1)/2 comparisons when no duplicate exists: quadratic growth, O(n²). Doubling n makes this term roughly four times as large.

This algorithm validates all n items, then scans at most n more. Under the ordinary expected constant-time hash-map lookup/insertion model, expected time is O(n), not O(2n) as a different growth class. It uses up to n keys, so extra memory is O(n). Empty input uses constant work and returns null. The input itself is not counted as extra memory.

This is an algorithmic model, not a promise that every PHP lookup is worst-case constant time or that measured seconds always double. Hash collisions, key lengths, allocation and runtime behavior matter. We restrict key types/ranges and do not claim a benchmark or a security-resistant hash design. For huge imports, consider bounded batches, external storage and database constraints.

Guided lab

1. Trace seen keys on paper for 5,2,2,5. Predict which ID is returned.
2. Run empty, one-item, no-repeat, adjacent-repeat and late-repeat cases.
3. Try a string ID, zero, a negative ID, an array element and an associative outer array. Each must throw.
4. Try 2,2 followed by an invalid string. The first validation pass must reject the whole input; do not return 2 early.
5. Run the same list twice. Compare the return values and original list; there must be no retained map or input mutation.

Independent exercise

Write firstDuplicatePosition() returning the zero-based index of the first repeated encounter, or null. Keep exactly the same input contract and full-validation rule. For 5,2,2,5 return 2; for 5,5 return 1; for empty input return null.

Then implement a separate simple nested-loop baseline with the same output rule. Compare results over small generated fixtures. Do not claim a performance measurement just from Big O. Hint: scan the current index in the outer loop and only earlier indices in the inner loop; the first match is the first repeated encounter.

Common mistakes

• Returning the smallest duplicate instead of the first repeated encounter.
• Returning before validating invalid later input.
• Treating string IDs and integer IDs as interchangeable without a contract.
• Sorting the caller’s list and losing encounter order.
• Saying the map uses no extra memory.
• Using an in-memory check to promise concurrency-safe database uniqueness.

Self-check and interview

Why are two linear passes still O(n)? What does first mean in the contract? What extra memory does the map use?

Interview: explain your input rules, invariant “seen contains exactly the earlier IDs”, expected lookup model, early return only after complete validation, and the time/memory tradeoff. Name the database unique constraint needed when this becomes a real concurrent write.

English practice and glossary

• List: an ordered sequence.
• Map: a key/value lookup structure.
• Invariant: a statement kept true during the loop.
• Big O: an upper-bound growth description under a stated model.
• Extra space: working memory beyond the input.
• Encounter order: the order values are visited.

Explain aloud: “I first validate __. The map stores __. Expected time is __ because __. The tradeoff is __.” Save your own approach, edge cases and later reattempt in the practice journal.

Recap and next step

Define the contract, validate it, then pick a structure. This map trades O(n) extra space for expected O(n) time. Next practise stacks/queues, binary search and two-pointer problems with explicit invariants. Source links accompany this draft; only Windows execution is recorded.