Find Duplicate by Index Marking

EasyArrays & Hashingindex marking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array nums of length n where every value is in the range 1 to n (inclusive). Exactly one value appears **twice** in the array, while every other value in the range 1 to n appears **at most once**. Return the value that appears twice. The intended approach uses the **index marking** technique: because each value is a valid index into the array (after offsetting by one), you can use the sign or magnitude of the element at the position a value points to as a "visited" flag. This lets you find the duplicate in O(n) time using only O(1) extra space, without sorting or a separate hash set. For example, when you read value v, you look at the slot it maps to (typically index v - 1). If that slot has already been marked, then v is the duplicate; otherwise you mark it and move on.

Examples

Input: nums = [1, 3, 4, 2, 2]
Output: 2
The value `2` is the only one that appears more than once.
Input: nums = [3, 1, 3, 4, 2]
Output: 3
`3` appears at index 0 and index 2, so it is the repeated value.
Input: nums = [2, 2]
Output: 2
With `n = 2`, values must be in 1..2; `2` is repeated and `1` is missing.

Constraints

  • `2 <= n <= 10^5` where `n` is the length of `nums`
  • `1 <= nums[i] <= n` for every index `i`
  • Exactly one value appears exactly twice; all other values appear at most once
  • Aim for `O(n)` time and `O(1)` extra space (the index marking pattern)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More index marking problems