Quick Overview

Find the earliest repeated value in scan order, then analyze sorted-input and no-built-in-set variants without losing the original ordering rule.

Find the First Value Repeated During a Left-to-Right Scan

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Scan an integer array from left to right and return the first value encountered for a second time. If no value repeats, return `-1`. Implement `first_duplicate(values: int[]) -> int`. The answer is determined by the earliest second occurrence, not the smallest repeated value or the repeated value with the earliest first occurrence. ### Constraints & Assumptions - The array has at most 200,000 elements, each a signed 32-bit integer. - `-1` is also a valid element; the required return convention may therefore use the same value for a repeated `-1` and for no duplicate. - Do not reorder the input for the primary task, because scanning order determines the answer. ### Examples - `[2, 1, 3, 1, 2]` returns `1`; its second occurrence appears before the second `2`. - `[4, 7, 9]` returns `-1`. After explaining the primary algorithm and its time/space costs, discuss both reported variants: how the method changes when the input is already sorted, and how to solve the task if built-in set-like containers are unavailable. State the data-range or custom-structure assumptions of the latter approach. ```hint Record what the scan has already seen At each position, determine whether this exact value appeared in the prefix. Once that condition is true, later positions cannot produce an earlier second occurrence. ```

Overview: Find the earliest repeated value in scan order, then analyze sorted-input and no-built-in-set variants without losing the original ordering rule.

Read the full Microsoft Software Engineer interview experience this question came from

Scan an integer array from left to right and return the first value encountered for a second time. If no value repeats, return `-1`. Implement `first_duplicate(values: int[]) -> int`. The answer is determined by the earliest second occurrence, not the smallest repeated value or the repeated value with the earliest first occurrence. ### Constraints & Assumptions - The array has at most 200,000 elements, each a signed 32-bit integer. - `-1` is also a valid element; the required return convention may therefore use the same value for a repeated `-1` and for no duplicate. - Do not reorder the input for the primary task, because scanning order determines the answer. ### Examples - `[2, 1, 3, 1, 2]` returns `1`; its second occurrence appears before the second `2`. - `[4, 7, 9]` returns `-1`. After explaining the primary algorithm and its time/space costs, discuss both reported variants: how the method changes when the input is already sorted, and how to solve the task if built-in set-like containers are unavailable. State the data-range or custom-structure assumptions of the latter approach. ```hint Record what the scan has already seen At each position, determine whether this exact value appeared in the prefix. Once that condition is true, later positions cannot produce an earlier second occurrence. ```

Constraints

  • 0 <= len(values) <= 200000.
  • Each value is a signed 32-bit integer in [-2147483648, 2147483647].
  • Return the value whose second occurrence is earliest in the original left-to-right order.
  • Return -1 if no duplicate exists; -1 is also a legal input and duplicate value.
  • Do not reorder the primary-task input. Already-sorted and no-built-in-set variants are explanatory follow-ups.

Examples

Input: ([2, 1, 3, 1, 2],)

Expected Output: 1

Explanation: The second 1 is encountered before the second 2, as in the source example.

Input: ([4, 7, 9],)

Expected Output: -1

Explanation: Every element in the second source example is distinct.

Hints

  1. The relevant ordering is the position of the second occurrence in the unchanged input.

Loading coding console...

Show the approach

Approach

Keep a set of values already encountered. For each input value, check membership before inserting it. Return immediately on a membership hit. If the scan ends without a hit, return -1.

Before each iteration, the set contains exactly the values in the preceding prefix. This is true initially for the empty prefix. Adding an unseen current value preserves the invariant. A membership hit means the current value appeared earlier; every previous position was checked without a hit, so this is precisely the earliest second occurrence. The answer therefore depends on original scan order, not numeric order or the earliest first occurrence. A legal input value of -1 participates in the set normally; the specified return convention deliberately does not distinguish its repetition from an all-distinct input.

With ordinary hash-table assumptions, membership and insertion take expected O(1) time, giving expected O(n) time overall. Pathological hashing can cause O(n^2) worst-case time. The set needs O(u) space for the distinct values processed, where u <= n. The C++ by-value parameter additionally copies O(n) input space. The other references leave the input in place. All legal signed 32-bit values are represented exactly in each language, including JavaScript.

If the input is already sorted, duplicates are consecutive. Scan from the second element and return the first value equal to its predecessor. This takes O(n) time and O(1) auxiliary space. Sorting an originally unsorted array before applying this method would change the primary task's answer.

If built-in set-like containers are unavailable, the same scan can use a custom hash table backed by arrays. Use separate occupancy information because every signed 32-bit value is a valid key. Expected O(n) time needs suitable hashing and a controlled load factor with resizing; storage is O(n). A custom balanced search tree instead gives O(n log n) worst-case time with O(n) storage. A direct-address bitmap requires a known range small enough for the available memory; the full 32-bit domain alone requires 2^32 bits, or 512 MiB, so a smaller-range assumption matters. With no additional data structure, compare each value with every earlier value and stop on the first match: O(n^2) time and O(1) auxiliary space.

Time complexity:
Expected O(n); O(n^2) worst case under pathological hashing.
Space complexity:
O(u) set storage for u distinct scanned values; C++ also copies O(n) input space.