BackmediumArraysTCS

Find All Duplicates Solution

Problem Statement

You are provided with an array of integers where each element represents a unique identifier for a data record. The system requires identifying all identifiers that have been logged more than twice. Specifically, an identifier is considered a duplicate if its frequency of occurrence in the array is strictly greater than 2. Return a list of all such identifiers. The order of the returned list does not matter, but each identifier must appear exactly once in the result, even if it appears multiple times beyond the threshold in the input array.

Example 1
Input
nums = [1, 2, 3, 1, 2, 3, 4, 1, 2]
Output
[1, 2]

Explanation: Count the occurrences of each number: 1 appears 3 times, 2 appears 3 times, 3 appears 2 times, 4 appears 1 time. The numbers with frequency > 2 are 1 and 2. Thus, the output is [1, 2].

Example 2
Input
nums = [5, 5, 5, 5, 6, 6, 7]
Output
[5]

Explanation: Count the occurrences: 5 appears 4 times, 6 appears 2 times, 7 appears 1 time. Only 5 has a frequency greater than 2. Thus, the output is [5].

Example 3
Input
nums = [10, 20, 30, 40, 50]
Output
[]

Explanation: Each number appears exactly once. No number has a frequency greater than 2. Thus, the output is an empty list [].

Example 4
Input
nums = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Output
[1, 2, 3, 4]

Explanation: Count the occurrences: 1 appears 3 times, 2 appears 3 times, 3 appears 3 times, 4 appears 4 times. All numbers have a frequency > 2. Thus, the output is [1, 2, 3, 4].

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • The input array may contain duplicates.
  • The output list must not contain duplicate values.
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Find All Duplicates — Problem Statement & Solution Guide

ArraysMediumCyclic Sort / Index Hashing
TimeO(n)
|
SpaceO(n)

Problem Description

You are provided with an array of integers where each element represents a unique identifier for a data record. The system requires identifying all identifiers that have been logged more than twice. Specifically, an identifier is considered a duplicate if its frequency of occurrence in the array is strictly greater than 2. Return a list of all such identifiers. The order of the returned list does not matter, but each identifier must appear exactly once in the result, even if it appears multiple times beyond the threshold in the input array.

DSA Pattern Breakdown

DSA Pattern Breakdown

"Find All Duplicates"

medium

WHY DOES IT MATTER?

Frequency counting is a foundational pattern in data analysis, caching, and database indexing. Mastering this pattern allows engineers to efficiently solve problems related to anomaly detection, load balancing, and resource allocation, which are ubiquitous in backend engineering.

OPTIMIZATION CHALLENGE

The key insight is shifting from O(n^2) repeated scanning to O(n) single-pass processing by using a Hash Map to store cumulative counts. This trades O(n) space for a significant reduction in time complexity, which is the standard trade-off in algorithm design for large-scale systems.

REAL-WORLD CONNECTION

This pattern is directly analogous to identifying 'hot keys' in a Redis cache or detecting spam in email servers. In both cases, the system must quickly identify items that appear with a frequency significantly higher than the baseline to trigger specific actions like rate limiting or filtering.

During the interview, explicitly state the trade-off between time and space. If the interviewer mentions memory constraints, pivot to the sorting-based O(1) space solution. This demonstrates flexibility and a deep understanding of the constraints.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)
💾 Space:O(n)

Core Theory — Why This Approach?

The problem of identifying elements with a frequency strictly greater than two is a classic instance of the frequency counting problem. The naive approach involves iterating through the array for each element to count its occurrences, resulting in a time complexity of O(n^2). This quadratic behavior becomes prohibitive for large datasets, such as those encountered in high-throughput logging systems or real-time analytics pipelines, where latency is critical. The fundamental limitation of the naive approach is the redundant computation of counts, which can be eliminated by leveraging auxiliary data structures that allow for constant-time lookups and updates.

Interview Questions on This Problem

Q1In a distributed logging system, how would you adapt this algorithm to handle data shards across multiple nodes before aggregating the final duplicate list?

You would perform local frequency counting on each shard using a HashMap. Then, you would aggregate these local maps by summing the counts for each key across all nodes. Finally, you filter the aggregated map for keys with a total count > 2. This MapReduce-style approach ensures scalability and handles the distributed nature of the data.

Q2If the input array is extremely large and does not fit in memory, what streaming algorithm could you use to approximate the duplicates, and what are the trade-offs?

You could use the Misra-Gries algorithm or Count-Min Sketch. These probabilistic data structures allow you to track heavy hitters (frequent elements) with sub-linear space. The trade-off is that you may get false positives (identifying non-duplicates as duplicates) but no false negatives, which is often acceptable for anomaly detection but not for strict data integrity checks.

Q3How would you modify this solution if the array was sorted in non-decreasing order? What is the new time and space complexity?

If the array is sorted, you can use a sliding window or a single pass with a pointer to count consecutive identical elements. You iterate through the array, counting how many times the current element appears. If the count exceeds 2, you add it to the result. This reduces the space complexity to O(1) (excluding the output list) while maintaining O(n) time complexity.

Examples

Example 1

Input

nums = [1, 2, 3, 1, 2, 3, 4, 1, 2]

Output

[1, 2]

Explanation: Count the occurrences of each number: 1 appears 3 times, 2 appears 3 times, 3 appears 2 times, 4 appears 1 time. The numbers with frequency > 2 are 1 and 2. Thus, the output is [1, 2].

Example 2

Input

nums = [5, 5, 5, 5, 6, 6, 7]

Output

[5]

Explanation: Count the occurrences: 5 appears 4 times, 6 appears 2 times, 7 appears 1 time. Only 5 has a frequency greater than 2. Thus, the output is [5].

Example 3

Input

nums = [10, 20, 30, 40, 50]

Output

[]

Explanation: Each number appears exactly once. No number has a frequency greater than 2. Thus, the output is an empty list [].

Example 4

Input

nums = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4]

Output

[1, 2, 3, 4]

Explanation: Count the occurrences: 1 appears 3 times, 2 appears 3 times, 3 appears 3 times, 4 appears 4 times. All numbers have a frequency > 2. Thus, the output is [1, 2, 3, 4].

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • The input array may contain duplicates.
  • The output list must not contain duplicate values.

Optimal Approach & Strategy

Use a Hash Map to store the frequency of each element in a single O(n) pass. Iterate through the map's entries and collect keys with a frequency strictly greater than 2 into the result list.

Brute Force Approach

Iterate through the array with two nested loops, where the outer loop selects an element and the inner loop counts its occurrences in the entire array. If the count is greater than 2, add the element to the result list, ensuring no duplicates are added to the result.

Verified Code Solutions

JavaScript Solution
Time: O(n)
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = data[idx++]||0;
const nums = data.slice(idx, idx+n);
function findDuplicates(nums){
    const map = new Map();
    for(const x of nums){
        map.set(x, (map.get(x)||0)+1);
    }
    const res = [];
    for(const [k,v] of map){
        if(v>2) res.push(k);
    }
    return res;
}
const res = findDuplicates(nums);
console.log(res.join(' '));

Asked in Top Tech Interviews

TCS

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.