Contains Duplicate 4 - Check if array contains duplicates given ranged array

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

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

Example 2

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

C++

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;
	}
};

Java

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;
	}
}

Python

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.