CS3334 Project: Find the Most Frequent Duplicate

1. Problem Description

1.1 Problem Statement

Given a list of integers, find the most frequent duplicate element. A "duplicate" is an element that appears more than once. Among all duplicates, return the one with the highest frequency. If two or more duplicates share the same highest frequency, return the one that appears first in the original list.

1.2 Input / Output Specification

Item	Description
Input	Multiple test cases. Each test case is a single line of space-separated integers. The number of integers is less than 10^5, and each integer is in the range (-10^5, 10^5).
Output	For each test case, output a single line containing the most frequent duplicated element.

1.3 Examples

Input	Output	Explanation
-1 1 -1 8	-1	-1 appears 2 times (duplicate), others appear once.
1 2 3 3 3 4 4 5	3	3 appears 3 times, 4 appears 2 times. 3 wins.
2 3 1 5 4 3 2 1	2	2, 3, 1 all appear 2 times. 2 appears first at index 0.

1.4 Key Observations

1. Only elements with frequency ≥ 2 (duplicates) are candidates.
2. The tie-breaking rule uses first-occurrence position in the original input, not the smaller value.
3. The integer range (-10^5, 10^5) is bounded, which opens the door for array-based counting.

---

2. Method 1 — Brute Force (Nested Loops)

2.1 Algorithm

For each element in the list, count its occurrences by scanning the entire list. Track the element with the highest count (≥ 2), preferring the one that appears earliest.

for i = 0 to n-1:
    if element[i] is already counted, skip
    count = 0
    for j = 0 to n-1:
        if element[j] == element[i]:
            count++
    if count >= 2 and count > bestCount:
        bestCount = count
        bestElement = element[i]

2.2 Data Structures

• Array / vector to store the input.
• A simple boolean array or set to record which values have already been counted (to avoid redundant inner scans).

2.3 Complete C++ Implementation

// Method 1: Brute Force — O(n^2)
// Compile: g++ -std=c++11 -O2 -o method1 method1.cpp
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    string line;

    while (getline(cin, line)) {
        if (line == "") continue;

        stringstream ss(line);
        vector<int> nums;
        int num;

        // Read numbers into vector
        while (ss >> num) {
            nums.push_back(num);
        }

        int n = nums.size();
        int bestCount = 0;
        int bestValue = nums[0];

        // Count frequency of each number
        for (int i = 0; i < n; i++) {
            int count = 0;

            for (int j = 0; j < n; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }

            // Only consider numbers that appear at least twice
            if (count >= 2) {
                if (count > bestCount) {
                    bestCount = count;
                    bestValue = nums[i];
                }
            }
        }

        cout << bestValue << endl;
    }

    return 0;
}

2.4 Time Complexity

Case	Complexity
Worst-case	O(n^2) — every element is distinct until the last pair, so the outer loop runs n times and the inner loop scans n elements each time.
Best-case	O(n) — all elements are identical; the first outer iteration counts n, and the visited set skips all subsequent iterations.
Space	O(n) — for the visited set.

2.5 Pros & Cons

Pros	Cons
Extremely simple to understand and implement.	Very slow for large inputs (n \approx 10^5).
No advanced data structures needed.	O(n^2) is likely to TLE on the OJ.

---

3. Method 2 — Sorting-Based

3.1 Algorithm

1. Create an auxiliary array of (value, first_occurrence_index) pairs.
2. Sort the array by value.
3. Scan the sorted array linearly: consecutive equal values form a group. Count each group's size.
4. Among groups with size ≥ 2, pick the one with the largest count; break ties by the smallest first_occurrence_index.

pairs[] = { (nums[i], i) for each i }
sort pairs by value

scan pairs to find groups of equal values
    for each group: record (value, count, first_index)

return the value with max count (tie-break: smallest first_index)

3.2 Data Structures

• Vector of pairs (value, original_index) for sorting.
• Sorting uses the quick sort, which is O(n \log n).

3.3 Complete C++ Implementation

// Method 2: Sorting-Based — O(n log n)
// Compile: g++ -std=c++11 -O2 -o method2 method2.cpp
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

// Partition function
int partition(vector<pair<int,int>> &arr, int low, int high) {
    int pivot = arr[high].first; // choose last element as pivot
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j].first <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Quick Sort function
void quickSort(vector<pair<int,int>> &arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    string line;

    while (getline(cin, line)) {
        if (line == "") continue;

        stringstream ss(line);
        vector<pair<int,int>> arr;
        int x, idx = 0;

        // Read input
        while (ss >> x) {
            arr.push_back(make_pair(x, idx));
            idx++;
        }

        int n = arr.size();

        // Use Quick Sort instead of sort()
        quickSort(arr, 0, n - 1);

        int bestCount = 1;
        int bestFirstIdx = n;
        int bestVal = arr[0].first;

        int i = 0;
        while (i < n) {
            int j = i;
            int firstIdx = n;

            while (j < n && arr[j].first == arr[i].first) {
                if (arr[j].second < firstIdx) {
                    firstIdx = arr[j].second;
                }
                j++;
            }

            int count = j - i;

            if (count >= 2) {
                if (count > bestCount ||
                   (count == bestCount && firstIdx < bestFirstIdx)) {
                    bestCount = count;
                    bestFirstIdx = firstIdx;
                    bestVal = arr[i].first;
                }
            }

            i = j;
        }

        cout << bestVal << endl;
    }

    return 0;
}

3.4 Time Complexity

Case	Complexity
Worst-case	O(n \log n) — dominated by the sort step. The subsequent linear scan is O(n).
Best-case	O(n \log n) — sorting always takes O(n \log n) regardless of input distribution.
Space	O(n) — for the auxiliary pairs array.

3.5 Pros & Cons

Pros	Cons
Significantly faster than brute force.	Sorting is destructive to original order (hence we store indices).
Uses only standard library sort.	Slightly more complex bookkeeping for tie-breaking.
Deterministic O(n \log n) with no hash collision risk.	Not as fast as hash-based O(n) on average.

---

4. Method 3 — Hash Map (unordered_map)

4.1 Algorithm

1. Traverse the list once. For each element, increment its count in a hash map.
2. Also record the first occurrence index of each element (only on the first encounter).
3. After counting, iterate over the hash map to find the duplicate (count ≥ 2) with the highest frequency, breaking ties by the smallest first occurrence index.

for i = 0 to n-1:
    freq[nums[i]]++
    if first_seen[nums[i]] not set:
        first_seen[nums[i]] = i

scan freq map:
    find element with max freq (>= 2), tie-break by first_seen

4.2 Data Structures

• **unordered_map<int, int>** for frequency counting — average O(1) per insertion/lookup.
• **unordered_map<int, int>** (or combined struct) for first-occurrence index.

4.3 Complete C++ Implementation

// Method 3: Hash Map — O(n) average
// Compile: g++ -std=c++11 -O2 -o method3 method3.cpp
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    string line;

    while (getline(cin, line)) {
        if (line == "") continue;

        stringstream ss(line);
        vector<int> nums;
        int x;

        // Read input numbers
        while (ss >> x) {
            nums.push_back(x);
        }

        unordered_map<int, int> freq;        // number -> frequency
        unordered_map<int, int> firstIndex;  // number -> first position

        int n = nums.size();

        // Build frequency and first index maps
        for (int i = 0; i < n; i++) {
            freq[nums[i]]++;

            // store first time we see this number
            if (firstIndex.find(nums[i]) == firstIndex.end()) {
                firstIndex[nums[i]] = i;
            }
        }

        int bestCount = 0;
        int bestValue = nums[0];
        int bestFirstIndex = n;

        // Find best answer
        for (auto &p : freq) {
            int value = p.first;
            int count = p.second;

            if (count >= 2) {
                int fi = firstIndex[value];

                if (count > bestCount ||
                   (count == bestCount && fi < bestFirstIndex)) {
                    bestCount = count;
                    bestFirstIndex = fi;
                    bestValue = value;
                }
            }
        }

        cout << bestValue << endl;
    }

    return 0;
}

4.4 Time Complexity

Case	Complexity
Average-case	O(n) — hash map operations are amortized O(1).
Worst-case	O(n^2) — if all keys hash to the same bucket (extremely unlikely with a good hash function).
Space	O(n) — for the hash maps (at most n distinct keys).

4.5 Pros & Cons

Pros	Cons
Fastest in practice — single pass O(n).	Hash collisions could degrade to O(n^2) (theoretical worst-case).
Clean and straightforward implementation.	Higher constant factor than array-based counting due to hashing overhead.
Handles arbitrary integer ranges naturally.	Uses more memory than a plain array when the value range is small.

---

5. Comprehensive Comparison

5.1 Theoretical Complexity Summary

Method	Best-Case Time	Average-Case Time	Worst-Case Time	Space
1. Brute Force	O(n)	O(n^2)	O(n^2)	O(n)
2. Sorting	O(n \log n)	O(n \log n)	O(n \log n)	O(n)
3. Hash Map	O(n)	O(n)	O(n^2)	O(n)

5.2 Practical Performance Comparison

The table below shows expected running times for different input sizes (n), assuming a modern machine with O(1) hash operations:

Input Size n	Brute Force	Sorting	Hash Map
100	< 1 ms	< 1 ms	< 1 ms
1,000	~1 ms	< 1 ms	< 1 ms
10,000	~100 ms	~1 ms	< 1 ms
100,000	~10 s (TLE)	~5 ms	~2 ms

5.3 Impact of Input Distribution

Input Pattern	Brute Force	Sorting	Hash Map
All elements identical	Fast (early termination)	O(n \log n) regardless	O(n)
All elements distinct	Slowest (n full scans)	O(n \log n)	O(n) but no valid answer
Many distinct values, few duplicates	Slow	Stable	Fast
Few distinct values, many duplicates	Moderate (visited set helps)	Stable	Fastest
Already sorted input	No benefit	O(n \log n), some sort optimizations	O(n)
Adversarial hash input	N/A	N/A	Could degrade to O(n^2)

5.4 Algorithm & Data Structure Comparison

Aspect	Brute Force	Sorting	Hash Map
Core Data Structure	Array + Set	Array of pairs	Hash table
Preserves original order?	Yes (inherently)	No (needs extra index storage)	Yes (via firstSeen map)
Deterministic worst-case	Yes, O(n^2)	Yes, O(n \log n)	No, depends on hash function
In-place?	Essentially yes	No (auxiliary pairs array)	No (hash map allocation)
Cache friendliness	Good (sequential access)	Good (after sort)	Poor (pointer chasing in hash buckets)
Implementation difficulty	Very easy	Moderate	Easy

5.5 When to Use Which Method

Scenario	Recommended Method	Reason
n \leq 1{,}000	Any method works	All run in under 1 ms.
n \approx 10^5 (OJ constraint)	Hash Map or Sorting	Brute force will TLE. Hash map is fastest on average.
Need guaranteed worst-case	Sorting	O(n \log n) is deterministic; hash map has theoretical O(n^2) worst-case.
Memory is very constrained	Sorting (in-place variant)	Can sort the original array to save memory.
Simplicity is the priority	Brute Force	Easiest to understand and debug.

5.6 OJ Acceptance Expectations

Given the constraint n < 10^5:

• Method 1 (Brute Force): Likely TLE on large test cases. O(n^2) = 10^{10} operations in the worst case.
• Method 2 (Sorting): Should pass comfortably. O(n \log n) \approx 1.7 \times 10^6 operations.
• Method 3 (Hash Map): Should pass with the fastest time. O(n) = 10^5 operations on average.

---

6. Testing Strategy

6.1 Edge Cases

Test Case	Expected Output	Tests
1 1	1	Minimum duplicate
5	(undefined — no duplicate exists)	Single element
-100000 100000 -100000	-100000	Boundary values
1 2 1 2	1	Tie-break by first occurrence
3 3 3 3 3	3	All identical

6.2 Stress Test Generation

// Generate random test data
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    int n = 100000;
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << (rand() % 200001 - 100000);
    }
    cout << endl;
    return 0;
}

---

7. Compilation Commands

# Method 1: Brute Force
g++ -std=c++11 -O2 -o method1 method1.cpp

# Method 2: Sorting
g++ -std=c++11 -O2 -o method2 method2.cpp

# Method 3: Hash Map
g++ -std=c++11 -O2 -o method3 method3.cpp

---

8. Conclusion

Among the three methods:

1. Brute Force is the simplest but impractical for large inputs due to its O(n^2) time complexity.
2. Sorting-Based provides a reliable O(n \log n) solution with deterministic worst-case guarantees.
3. Hash Map is the most efficient in practice with O(n) average time, making it the best choice for the OJ system.

For this project's constraints (n < 10^5), Method 3 (Hash Map) is the recommended primary solution, with Method 2 (Sorting) as a robust alternative. Method 1 (Brute Force) serves as a baseline for understanding and correctness verification.