First Duplicate Value

Tags

First Duplicate Value

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of integers between 1 and n (inclusive), where n is the length of the array, find the first integer that appears more than once when reading the array from left to right. If no duplicate exists, return -1. The solution must use O(1) extra space.

Intuition

Since every value is in the range [1, n], we can use the array itself as a hash map by treating each value as an index. When we encounter a value, we negate the element at that index. If the element at that index is already negative, we have found our first duplicate.

Approach

  1. Iterate through the array from left to right.
  2. For each element, compute absVal = abs(array[i]).
  3. Check array[absVal - 1]:
    • If it is negative, absVal has been seen before — return absVal.
    • Otherwise, negate array[absVal - 1] to mark absVal as seen.
  4. If no duplicate is found after the full scan, return -1.

Pseudocode

function firstDuplicateValue(array):
    for i from 0 to length(array) - 1:
        absVal = abs(array[i])
        if array[absVal - 1] < 0:
            return absVal
        array[absVal - 1] *= -1

    return -1

Time & Space Complexity

  • Time: O(n) — single pass through the array.
  • Space: O(1) — the array is modified in place; no additional data structures are used.

Key Insights

  • The constraint that values are in [1, n] is what makes the index-as-hash-map trick possible.
  • Using absolute values ensures that a previously negated index does not cause an out-of-bounds access.
  • This finds the first duplicate by order of second occurrence, which is the correct interpretation of "first duplicate value."
  • An alternative O(n) time, O(n) space approach uses a hash set, but the negation trick achieves O(1) space.

Edge Cases

  • No duplicates in the array: return -1.
  • The duplicate is the first element: handled naturally since its index will be negated on first visit.
  • Array of length 1: no duplicate possible, return -1.
  • Multiple duplicates: the one whose second occurrence appears earliest is returned.

Linked mentions