Find All Duplicates In Array Solution for TCS NQT
Company: TCS NQT · Difficulty: Medium · Topics: Array, Hash Table
Problem Statement
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 a solution that runs in O(n) time and uses only constant extra space.
Examples
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation:
- 2 appears twice (at indices 2 and 5)
- 3 appears twice (at indices 1 and 6)
- All other numbers appear only once
Example 2:
Input: nums = [1,1,2]
Output: [1]
Explanation:
- 1 appears twice (at indices 0 and 1)
- 2 appears only once
Example 3:
Input: nums = [1]
Output: []
Explanation:
- 1 appears only once, so there are no duplicates
Example 4:
Input: nums = [3,3,3,3]
Output: [3]
Explanation:
- 3 appears four times, but we only count it once in the result
Intuition
The key insight is to use the array itself as a hash table. Since all numbers are in the range [1, n], we can use the array indices to mark which numbers we've seen.
When we encounter a number, we can mark its corresponding index (number-1) as negative to indicate we've seen it. If we encounter a negative number at that index, it means we've seen this number before.
Approach
Approach 1: Mark as Negative (Optimal)
1. Iterate through the array
2. For each number nums[i], calculate its corresponding index: abs(nums[i]) - 1
3. If the number at that index is negative, it means we've seen this number before
4. Mark the number at that index as negative
5. Collect all numbers that appear twice
Approach 2: Using Extra Array
1. Create a boolean array of size n+1
2. Iterate through the input array
3. Mark each number as seen in the boolean array
4. If a number is already marked, add it to the result
Approach 3: Sorting and Linear Scan
1. Sort the array
2. Scan through the sorted array
3. If consecutive elements are equal, add to result
Dry Run
Let's trace through Example 1: nums = [4,3,2,7,8,2,3,1]
Mark as Negative Approach:
Initial array: [4,3,2,7,8,2,3,1]
Step 1: i=0, nums[0]=4
- Index = abs(4)-1 = 3
- nums[3] = 7 (positive), mark as negative: nums[3] = -7
- Array: [4,3,2,-7,8,2,3,1]
Step 2: i=1, nums[1]=3
- Index = abs(3)-1 = 2
- nums[2] = 2 (positive), mark as negative: nums[2] = -2
- Array: [4,3,-2,-7,8,2,3,1]
Step 3: i=2, nums[2]=-2
- Index = abs(-2)-1 = 1
- nums[1] = 3 (positive), mark as negative: nums[1] = -3
- Array: [4,-3,-2,-7,8,2,3,1]
Step 4: i=3, nums[3]=-7
- Index = abs(-7)-1 = 6
- nums[6] = 3 (positive), mark as negative: nums[6] = -3
- Array: [4,-3,-2,-7,8,2,-3,1]
Step 5: i=4, nums[4]=8
- Index = abs(8)-1 = 7
- nums[7] = 1 (positive), mark as negative: nums[7] = -1
- Array: [4,-3,-2,-7,8,2,-3,-1]
Step 6: i=5, nums[5]=2
- Index = abs(2)-1 = 1
- nums[1] = -3 (negative), so 2 is a duplicate
- Mark as negative: nums[1] = 3 (already negative, stays negative)
- Array: [4,-3,-2,-7,8,2,-3,-1]
Step 7: i=6, nums[6]=-3
- Index = abs(-3)-1 = 2
- nums[2] = -2 (negative), so 3 is a duplicate
- Mark as negative: nums[2] = 2 (already negative, stays negative)
- Array: [4,-3,-2,-7,8,2,-3,-1]
Step 8: i=7, nums[7]=-1
- Index = abs(-1)-1 = 0
- nums[0] = 4 (positive), mark as negative: nums[0] = -4
- Array: [-4,-3,-2,-7,8,2,-3,-1]
Result: [2,3] (numbers that appeared twice)
Key Insights
1. Array as Hash Table: Use the array indices to mark seen numbers
2. Negative Marking: Mark seen numbers by making them negative
3. Absolute Value: Use abs() to handle already marked numbers
4. Range Constraint: Numbers are in [1, n], so indices are valid
Edge Cases
1. Single element: Return empty array
2. All duplicates: Return array with one element
3. No duplicates: Return empty array
4. Multiple occurrences: Only count each duplicate once
Time and Space Complexity
- Time Complexity: O(n) - Single pass through the array
- Space Complexity: O(1) - Only using the input array