[leetcode #442] Find All Duplicates in an Array

Problem

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: []

Constraints:

・ n == nums.length
・ 1 <= n <= 10⁵
・ 1 <= nums[i] <= n
・ Each element in nums appears once or twice.

Idea

주어진 array에서 중복된 숫자를 구하라는 문제다. Time complexity는 O(n), space complexity는 상수로 풀어야 한다는 제약 사항이 있다. 이런 문제는 제약 사항을 잘 봐야 하는데, array에 들어가는 수가 1~n까지이며 각 수는 최대 2번까지 포함될 수 있다고 말한다.

set을 이용해 풀면 간단하지만 space complexity가 O(n)이 되어버린다는 문제가 있다. 각 수가 최대 2번까지 포함될 수 있다는 사항에 유의하면, 주어진 array의 부호를 이용하여 각 값이 몇 번 등장했는지 알 수 있다.

알고리즘은 다음과 같다.

1. array를 순차적으로 탐색한다.
2. array의 절대값에 1을 뺀 값을 index로 정한다.
3. index에 해당하는 값이 음수이면 이미 2번 포함된 수이므로 result에 (index+1)을 더한다.
4. index에 해당하는 값에 -1을 곱한다.
5. 구한 값을 return한다.

위와 같은 알고리즘을 활용할 수 있는 이유는 array에 들어가는 수가 1~n까지로 제한되기 때문에 각 index의 부호를 활용하여 2번 포함되었는지 여부를 확인할 수 있기 때문이다.

Solution

class Solution {
    public List<Integer> findDuplicates(int[] nums) {

    	List<Integer> resultSet = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            // Get the index, the element corresponds to
            int index = Math.abs(nums[i]) - 1;

            // If the number is already negative, it means we are 
            // encountering it twice
            if (nums[index] < 0)
                resultSet.add(index + 1);

            // Flip the number at the index to negative
            nums[index] = nums[index] * -1;
        }

        return resultSet;
    }
}

Reference

https://leetcode.com/problems/find-all-duplicates-in-an-array/
https://studyalgorithms.com/array/leetcode-find-duplicates-array/