Find All Duplicates in an Array

class Solution {
 public:
    vector<int> getDuplicates(vector<int>& elements) {
        vector<int> duplicates;

        for (int element : elements) {
            int index = abs(element) - 1;
            if (elements[index] < 0) {
                duplicates.push_back(abs(element));
            }
            elements[index] = -elements[index];
        }

        return duplicates;
    }
};

The solution provided in C++ efficiently identifies all duplicate elements within an array. Here's a brief overview of how this approach works:

• The function getDuplicates accepts a reference to a vector of integers, which contains the elements of the array you are analyzing for duplicates.
• A new vector duplicates is declared to store the results, i.e., the duplicate elements found in the input array.
• Iterating through each element of the input array exploits a key observation: the array elements are used as indices to mark visited locations in the same array. This is accomplished by negating the value at the indexed position. If the value is already negative, this indicates a revisit, and hence, the element is a duplicate.
• For each element in the array, calculate its corresponding index by subtracting one from its absolute value (to account for 0-based indexing).
• Check if the value at the computed index is negative:
  • If yes, the abs value of the current element is added to the duplicates vector since this implies the index has been visited before, marking the element as a duplicate.
  • If no, negate the value at the index to mark it as visited.
• Return the duplicates vector, which now contains all duplicate elements from the input array.

This method proves to be efficient because it operates in linear time, O(n), where n is the number of elements in the array, and requires no additional space for its operation, O(1), beyond the space needed for the result. This efficiency makes the solution well-suited for large datasets. Make sure to use this function when the input guarantees that all elements are within the range from 1 to n, where n is the size of the array.

class Solution {
    public List<Integer> identifyDuplicates(int[] array) {
        List<Integer> duplicates = new ArrayList<>();

        for (int value : array) {
            int index = Math.abs(value) - 1;
            if (array[index] < 0) { // already marked
                duplicates.add(Math.abs(value));
            }
            array[index] = -array[index];
        }

        return duplicates;
    }
}

This Java solution addresses the problem of finding all duplicates in an array using a space-efficient algorithm. The solution leverages the input array itself to detect duplicates by marking visited numbers. Here's how you execute this approach:

1. Initialize an empty list to store the duplicates found in the array.
2. Iterate through each number in the provided array.
3. Calculate the index associated with the current number's absolute value (considering that indices are zero-based).
4. Check if the number at the computed index is negative, which indicates the original number has been seen before, hence is a duplicate.
5. If a duplicate is detected, add the absolute value of the current number to the list of duplicates.
6. Mark the number at the computed index as visited by making it negative.

By the end of the loop, the list contains all the numbers that appear twice in the array. This method does not use additional space for another data structure, as it directly modifies the original array for marking purposes, exploiting the properties of indices and values for tracking seen numbers. Please note that the array elements should strictly be positive numbers for this method to work correctly. The solution ensures modifications are only sign-based, preserving the ability to extract the original values using absolute operations.