Introduction

Duplicate values in arrays can pose a challenge when working with data in programming. Duplicate elements do not only consume unnecessary memory but can also lead to incorrect results if not handled properly. In C++, there are various techniques to remove duplicate values from an array efficiently, ensuring optimal performance.

Problem Statement

Consider an array containing elements where some values may be duplicated. The objective is to create a modified array that retains only unique elements, eliminating any duplicates. This process is crucial in scenarios where distinct values are required for accurate data analysis, processing, or presentation.

Algorithm

The algorithm for removing duplicate values from an array involves iterating through each element and keeping track of unique values encountered so far. Here's a step-by-step breakdown of the algorithm:

1. Initialize an empty set or hash table to store unique values.
2. Iterate through the array.
3. For each element, check if it is already present in the set.
   a. If not present, add it to the set and include it in the modified array.
   b. If already present, skip the element.
4. The modified array now contains only unique values.

Code Implementation

#include <iostream>
#include <unordered_set>
#include <vector>

// Function to remove duplicate values from an array
std::vector<int> removeDuplicates(const std::vector<int>& inputArray) {
    // Create an unordered_set to store unique values
    std::unordered_set<int> uniqueSet;

    // Create a vector to store the modified array without duplicates
    std::vector<int> result;

    // Iterate through each element in the input array
    for (const auto& element : inputArray) {
        // Check if the element is not present in the set
        if (uniqueSet.find(element) == uniqueSet.end()) {
            // If not present, add it to the set
            uniqueSet.insert(element);

            // Also include it in the modified array
            result.push_back(element);
        }
    }

    // Return the modified array without duplicate values
    return result;
}

// Main function
int main() {
    // Example usage: an array with duplicate values
    std::vector<int> inputArray = {1, 2, 3, 2, 4, 5, 6, 1};

    // Call the removeDuplicates function to get the modified array
    std::vector<int> modifiedArray = removeDuplicates(inputArray);

    // Output the modified array
    std::cout << "Modified Array: ";
    for (const auto& element : modifiedArray) {
        std::cout << element << " ";
    }

    // Return 0 to indicate successful execution
    return 0;
}

// Output
Modified Array: 1 2 3 4 5 6 

Explanation

Function removeDuplicates:

• The removeDuplicates function take a constant reference to an input array (inputArray).
• It initializes an unordered set (uniqueSet) to store unique values encountered during the iteration.
• Another vector (result) is created to store the modified array without duplicate values.
• The function iterates through each element in the input array using a range-based for loop.
• For each element, it checks whether the element is present in the set (uniqueSet) using find.
• If the element is not present, it means it's unique.
• It adds the element to the set and also includes it in the modified array (result).
• In the main function, an example array with duplicate values (inputArray) is created and the removeDuplicates  function is called to obtain the modified array without duplicates (modifiedArray).

Complexity Analysis

Time Complexity: The time complexity of this algorithm is O(N), where N is the number of elements in the input array. This is because each element is visited only once.

Space Complexity: The space complexity is also O(N) as the unordered set may store all unique elements from the array. In the worst case, where all elements are unique, the set's size would be equal to the array size.