Problem

There is a size-N array of integers whose values range from 1 to N. Some integers are duplicated. Find the first duplicate and its index without using any extra memory (not even O(1)).

Examples

Example 1:

Input: nums = [2, 3, 3, 1, 4, 2]
Output: [3, 1]
Explanation: The first duplicate is 3, which appears first at index 1.

Example 2:

Input: nums = [1, 2, 3, 4, 2, 6, 7, 5]
Output: [2, 1]

Solution

Consider the following key points for this problem:

  1. The array has a fixed size N, which is the upper limit for the integers in the array. So, if the array size is 10, it contains 10 elements, each between 1 and 10.
  2. Some numbers are duplicates, meaning the array may not include every number from 1 to N.
  3. We are required to find only the first duplicate. Once we find it, we can stop.
  4. No extra memory is allowed. This means we cannot use any additional storage or declare any new variables in our algorithm, as the space complexity must be O(1).

To solve the problem, we need to track the elements to identify duplicates, but without using extra memory. We must rely on the constraints given in the problem.

Method 1 - Using modulo operator

Given that each element’s value is between 1 and N, adding (N + 1) to any element in the array doesn’t change its modulus with (N + 1). For instance, the modulus of 2 and (N + 1) remains 2, and so does the modulus of 2 + (N + 1). Therefore, we can mark a visited element by adding (N + 1) to its value without altering its modulus.

Each element’s value falls between 1 and N, allowing us to use the value as a key and the element at array[key] as the marker. For example, if the current element is 4, we can check for duplication by inspecting the value at index 4 in the array. Similarly, if the element is 2, we check the value at index 2, and so forth.

Lastly, we need to traverse the array and check each element until we find a duplicate or reach the array’s end. This typically requires an additional counter for loop termination, which would need extra memory. However, since the first element cannot be a duplicate (nothing precedes it), we can use the first element in the array as our counter.

Code

Java
public class Solution {
    public int[] findFirstDuplicate(int[] arr) {
        int n = arr.length;
        boolean found = false;
        // Initialize the loop
        for (int i = 0; i < n; i++) {
            int index = arr[i] % n;  // Use the value as an index
            arr[index] += n;         // Mark the element by adding n to the value at index
            if (arr[index] / n >= 2) {
                return new int[] { index, i };
            }
        }
        return new int[] { -1, -1 };  // indicating no duplicate found
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = { 2, 3, 3, 1, 4, 2 };
        int[] result1 = solution.findFirstDuplicate(arr1);
        System.out.println("The first duplicate is: " + result1[0] + ", Index: " + result1[1]);  // Output: The first duplicate is: 3, Index: 2

        int[] arr2 = { 1, 2, 3, 4, 2, 6, 7, 5 };
        int[] result2 = solution.findFirstDuplicate(arr2);
        System.out.println("The first duplicate is: " + result2[0] + ", Index: " + result2[1]);  // Output: The first duplicate is: 2, Index: 4
    }
}
Python
class Solution:
    def findFirstDuplicate(self, arr):
        n = len(arr)
        for i in range(n):
            index = arr[i] % n  # Use the value as an index
            arr[index] += n     # Mark the element by adding n to the value at index
            if arr[index] // n >= 2:
                return index, i
        return -1, -1  # indicating no duplicate found

# Example usage
solution = Solution()
arr1 = [2, 3, 3, 1, 4, 2]
print(f"The first duplicate is: {solution.findFirstDuplicate(arr1)}")  # Output: (3, 2)

arr2 = [1, 2, 3, 4, 2, 6, 7, 5]
print(f"The first duplicate is: {solution.findFirstDuplicate(arr2)}")  # Output: (2, 4)

Method 2 - Using sign

To solve this problem without using any extra memory, we can use the input array itself to keep track of visited numbers by making the values at visited indices negative. This way:

  1. Traverse the array.
  2. For each number, treat the absolute value of the number as an index and make the value at that index negative to mark it as visited.
  3. If the value at the index is already negative, it indicates the first occurrence of the duplicate value.

Code

Java
public class Solution {
    public int[] findFirstDuplicate(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int index = Math.abs(arr[i]);
            if (arr[index] >= 0) {
                arr[index] = -arr[index];
            } else {
                return new int[] { index, i };
            }
        }
        return new int[] { -1, -1 };  // indicating no duplicate found
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = { 2, 3, 3, 1, 4, 2 };
        int[] result1 = solution.findFirstDuplicate(arr1);
        System.out.println("The first duplicate is: " + result1[0] + ", Index: " + result1[1]);  // Output: The first duplicate is: 3, Index: 2

        int[] arr2 = { 1, 2, 3, 4, 2, 6, 7, 5 };
        int[] result2 = solution.findFirstDuplicate(arr2);
        System.out.println("The first duplicate is: " + result2[0] + ", Index: " + result2[1]);  // Output: The first duplicate is: 2, Index: 4
    }
}
Python
class Solution:
    def findFirstDuplicate(self, arr):
        n = len(arr)
        for i in range(n):
            index = abs(arr[i])
            if arr[index] >= 0:
                arr[index] = -arr[index]
            else:
                return index, i
        return -1, -1  # indicating no duplicate found

# Example usage
solution = Solution()
arr1 = [2, 3, 3, 1, 4, 2]
print(f"The first duplicate is: {solution.findFirstDuplicate(arr1)}")  # Output: (3, 2)

arr2 = [1, 2, 3, 4, 2, 6, 7, 5]
print(f"The first duplicate is: {solution.findFirstDuplicate(arr2)}")  # Output: (2, 4)

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)