Problem

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Solution

Method 1 – Cyclic Sort for Detecting Duplicate and Missing Number

Intuition

Since the numbers are in the range [1, n], we can use the array indices to place each number at its correct position (i.e., value v at index v-1). If a number is already at its correct position or a duplicate is found, we skip it. After sorting, the index where the value does not match the index + 1 gives us the duplicate and missing numbers.

Approach

  1. Iterate through the array and for each index i, while nums[i] != nums[nums[i] - 1], swap nums[i] with nums[nums[i] - 1].
  2. After the swaps, iterate through the array again. If nums[i] != i + 1, then nums[i] is the duplicate and i + 1 is the missing number.
  3. Return [duplicate, missing].

Complexity

  • ⏰ Time complexity: O(n), as each element is swapped at most once.
  • 🧺 Space complexity: O(1), since the algorithm works in-place and uses only a result array for output.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return {nums[i], i + 1};
        }
        return {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findErrorNums(nums []int) []int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return []int{nums[i], i+1}
        }
    }
    return []int{}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[i];
                nums[i] = nums[tmp - 1];
                nums[tmp - 1] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return new int[]{nums[i], i + 1};
        }
        return new int[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        n = len(nums)
        for i in range(n):
            while nums[i] != nums[nums[i] - 1]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i, v in enumerate(nums):
            if v != i + 1:
                return [v, i + 1]
        return []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findErrorNums(nums: IntArray): IntArray {
        val n = nums.size
        for (i in 0 until n) {
            while (nums[i] != nums[nums[i] - 1]) {
                val tmp = nums[i]
                nums[i] = nums[tmp - 1]
                nums[tmp - 1] = tmp
            }
        }
        for (i in 0 until n) {
            if (nums[i] != i + 1) return intArrayOf(nums[i], i + 1)
        }
        return intArrayOf()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function findErrorNums(nums: number[]): number[] {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] !== nums[nums[i] - 1]) {
            const tmp = nums[i];
            nums[i] = nums[tmp - 1];
            nums[tmp - 1] = tmp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return [nums[i], i + 1];
    }
    return [];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_error_nums(nums: &mut Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            while nums[i] != nums[(nums[i] - 1) as usize] {
                let j = (nums[i] - 1) as usize;
                nums.swap(i, j);
            }
        }
        for (i, &v) in nums.iter().enumerate() {
            if v != (i as i32) + 1 {
                return vec![v, (i as i32) + 1];
            }
        }
        vec![]
    }
}