Problem

Given an array of n elements where each element is in the range 1 to n (or 0 to n-1), check if the array contains any duplicates.

Examples

Example 1

1
2
3

Input: [1, 1, 2, 3, 2]
Output: true
Explanation: 1 and 2 are repeated.

Example 2

1
2
3

Input: [1, 2, 3, 4, 5]
Output: false
Explanation: No duplicates present.

Solution

Method 1 – Negation Trick (Modify Array)

Intuition

If all elements are in the range 1 to n (or 0 to n-1), we can use the array itself to track seen elements by negating the value at the index corresponding to each element.

Approach

  1. Traverse the array.
  2. For each element A[i], check the sign of A[abs(A[i])]:
    • If positive, negate it.
    • If negative, a duplicate is found.
  3. If no duplicate is found, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
	bool hasDuplicates(vector<int>& arr) {
		for (int i = 0; i < arr.size(); ++i) {
			int idx = abs(arr[i]);
			if (arr[idx] < 0) return true;
			arr[idx] = -arr[idx];
		}
		return false;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	public boolean hasDuplicates(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int idx = Math.abs(arr[i]);
			if (arr[idx] < 0) return true;
			arr[idx] = -arr[idx];
		}
		return false;
	}
}
1
2
3
4
5
6
7
8

class Solution:
	def has_duplicates(self, arr: list[int]) -> bool:
		for i in range(len(arr)):
			idx = abs(arr[i])
			if arr[idx] < 0:
				return True
			arr[idx] = -arr[idx]
		return False

Complexity

  • ⏰ Time complexity: O(n) — Each element is checked once.
  • 🧺 Space complexity: O(1) — No extra space is used.

Note: This method modifies the original array and only works for positive numbers in the specified range.