Given an array of integers, 1 ≤ a[i] ≤ *n* (*n* = size of array), some elements appear **twice** and others appear **once**.

Find all the elements that appear **twice** in this array.

Could you do it without extra space and in O(*n*) runtime?

**Example:**

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

## Approach

- When find a number i, flip the number at position i-1 to negative.
- If the number at position i-1 is already negative, i is the number that occurs twice.

## Solution

C# Program

public class Solution { public IList<int> FindDuplicates(int[] nums) { var list = new List<int>(); for(int i=0;i<nums.Length;i++) { //Take the index of the element //We need the index i - 1 for the element at i int index = Math.Abs(nums[i]) - 1; if(nums[index] < 0) list.Add(index+1); /*When find a number i, flip the number at position i-1 to negative. */ else nums[index] = -nums[index]; } return list; } }

**Time Complexity : O(n)**

**Space Complexity : O(1)**

Pingback: 100 Days Leetcode Challenge – Passion of Programming

Pingback: Find All Numbers Disappeared in an Array – Passion of Programming