Find All Duplicates In An Array Problem


Description

LeetCode Problem 442.

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 inO(n)time and uses only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i ++) {
            int x = abs(nums[i]);
            if (nums[x-1] > 0) {
                nums[x-1] = -nums[x-1];
            } else {
                ans.push_back(x);
            }
        }
        return ans;
    }
};




Related Posts

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...