How to find duplicate element in array and return duplicate index

Algorithm Type

• Category: Array Manipulation, In-Place Modification

• Time Complexity: O(n) (linear time)

• Space Complexity: O(1) (constant extra space, ignoring output list)

• Technique Used: Index Mapping & Negation

Explanation

It is commonly used in in-place duplicate detection problems, especially when the input array contains numbers from 1 to n. The algorithm tracks duplicates by marking indices as negative instead of using extra space like a hash set. It leverages the fact that all numbers are between 1 and n to use indices as a way to mark seen numbers.

1. Iterate through the array and compute an index (n = abs(nums[i]) - 1).

2. Check if nums[n] is already negative:

   • If yes, this means the number has appeared before → it's a duplicate.

   • If no, mark it by negating (nums[n] = -nums[n]).

3. Continue until all elements are processed.

4. Return the list of duplicates.

Example With Processing Steps:

Input:

nums = {4, 3, 2, 7, 8, 2, 3, 1}

Output:

Duplicate numbers: 2 3

public class Solution {
    public IList<int> FindDuplicates(int[] nums) {
        
        var res = new List<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            //Iterate through the array and compute an index.
            var n = Math.Abs(nums[i]) - 1;
            //Check if nums[n] is already negative
            if(nums[n] < 0)
            {                
               //If yes, this means the number has appeared before
               res.Add(n + 1);
            }
            //If no, mark it by negating.
            nums[n] = -nums[n];

        }
        //Return the list of duplicates.
        return res;
    }
}

Comparison with Other Duplicate-Finding Algorithms

When to Use This Algorithm?

✔️ When extra space is not allowed
✔️ When numbers are within 1 to n
✔️ When O(n) time complexity is needed

❌ Not suitable if numbers can be negative or out of range
❌ Modifies the input array (restoration might be needed)

This approach is commonly used in LeetCode problems like:

• "Find All Duplicates in an Array" (LeetCode 442)

• "Find the Duplicate Number" (LeetCode 287, with slight modifications)