How do you solve Set Mismatch?

Create a boolean array of size n+1 initialized to False. Iterate over nums, marking seen[num] as True; if already True, record num as duplicate. Then iterate from 1 to n to find the number not seen, which is the missing number. Return [duplicate, missing].

What pattern does Set Mismatch use?

The Pattern: Hash Maps (Boolean Array for Presence Tracking) The Heuristic: When needing to detect duplicates and missing elements within a known range, use a presence-tracking data structure to achieve O(n) time by trading space for constant-time membership checks.

Set Mismatch | Hash Maps

Q: What is the time complexity of Set Mismatch?

O(n). The algorithm makes two passes over arrays of length n: one over the input nums and one over the range 1 to n, each O(n).

Problem

Given an array nums containing n integers where each integer is in the range [1, n] inclusive, exactly one number is duplicated and one number is missing; return the duplicate number and the missing number as an array [duplicate, missing].

2 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ nums.length

Example

Input: nums = [1,2,2,4]

Output: [2,3]

The array should contain numbers 1 through 4. The number 2 appears twice, and the number 3 is missing. The algorithm detects the duplicate by tracking seen numbers and then finds the missing number by checking which number in the range 1 to n was never seen.

Approach

Straightforward Solution

A brute-force approach would check counts of each number using nested loops, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

The problem reduces to identifying one number that appears twice and one number missing from the range 1 to n. Tracking occurrences efficiently allows detection of the duplicate and missing numbers.

Path to Optimal

Preview

By using a boolean array to track which numbers have been seen, the algorithm can detect the duplicate in a single pass. Then, a second pass over the range 1 to n identifies the missing number by finding which number was never marked as seen…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Create a boolean array of size n+1 initialized to False. Iterate over nums, marking seen[num] as True; if already True, record num as duplicate…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes two passes over arrays of length n: one over the input nums and one over the range 1 to n, each O(n).

Space

O(n)

The boolean array of size n+1 stores presence information for each number, which scales linearly with input size. This auxiliary space is necessary for constant-time membership checks.

Solution

Python

1class Solution:
  def findErrorNums(self, nums: List[int]) -> List[int]:
      n = len(nums)
      seen = [False] * (n + 1)
5
      duplicate = -1
7
      for num in nums:
          if seen[num]:
              duplicate = num
          else:
              seen[num] = True
13
      missing = -1
15
      for num in range(1, n + 1):
          if not seen[num]:
              missing = num
              break
20
      return [duplicate, missing]

Step-by-Step Solution

1

Track Seen Numbers to Identify the Duplicate

3n = len(nums)
4seen = [False] * (n + 1)
6duplicate = -1
8for num in nums:
9    if seen[num]:
10        duplicate = num
11    else:
12        seen[num] = True

Objective

To iterate through nums and mark each number as seen, detecting the duplicate when a number is encountered twice.

Key Insight

Using a boolean array indexed by number allows constant-time checks for whether a number has been seen before. When a number is found already marked as seen, it must be the duplicate. This approach avoids nested loops and reduces time complexity from O(n^2) to O(n).

Interview Quick-Check

Core Logic

Mark each number as seen in a boolean array; if already marked, record it as the duplicate.

State & Boundaries

The boolean array size is n+1 to align indices with numbers 1 through n, simplifying indexing.

Common Pitfalls & Bugs

Forgetting to check if a number is already seen before marking it leads to missing the duplicate.

2

Identify the Missing Number by Checking Unseen Indices

To find the missing number by scanning the boolean array for the first number not marked as seen.

3

Return the Result Array Containing Duplicate and Missing Numbers

To return the final answer as an array containing the duplicate and missing numbers.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

if seen[num]:

Check if the current number has already been seen.

Detecting a previously seen number here is the definitive check that identifies the duplicate, enabling immediate recording without further search.

Line 17 Critical

if not seen[num]:

Check if the current number in the range was not seen.

Identifying the missing number here is the critical step that completes the problem's requirement, leveraging the presence tracking.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why is a boolean array used instead of a hash set, and why is it sufficient for this problem?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Set Mismatch from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Set Mismatch drill

or drill a free problem

1	`class Solution:`
2	`def findErrorNums(self, nums: List[int]) -> List[int]:`
3	`n = len(nums)`
4	`seen = [False] * (n + 1)`
5
6	`duplicate = -1`
7
8	`for num in nums:`
9	`if seen[num]:`
10	`duplicate = num`
11	`else:`
12	`seen[num] = True`
13
14	`missing = -1`
15
16	`for num in range(1, n + 1):`
17	`if not seen[num]:`
18	`missing = num`
19	`break`
20
21	`return [duplicate, missing]`

3	`n = len(nums)`
4	`seen = [False] * (n + 1)`
6	`duplicate = -1`
8	`for num in nums:`
9	`if seen[num]:`
10	`duplicate = num`
11	`else:`
12	`seen[num] = True`