Finding duplicates efficiently in SQL - Time & Space Complexity

Time Complexity: Finding duplicates efficiently

O(n)

Understanding Time Complexity

When we look for duplicates in a database table, we want to know how the work grows as the table gets bigger.

We ask: How much longer does it take to find duplicates if we add more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column_name, COUNT(*)
FROM table_name
GROUP BY column_name
HAVING COUNT(*) > 1;
    

This query finds all values in column_name that appear more than once in table_name.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows to group by the column.
• How many times: Each row is processed once to count duplicates.

How Execution Grows With Input

As the number of rows grows, the database must check each row once to group and count.

Input Size (n)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find duplicates grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Finding duplicates takes much longer than just reading the table once."

[OK] Correct: The database groups rows in one pass, so it doesn't repeatedly scan the table.

Interview Connect

Understanding how grouping works helps you explain efficient data checks clearly and confidently.

Self-Check

"What if we added an index on column_name? How would the time complexity change?"

Practice

1. What is the main purpose of using GROUP BY with HAVING COUNT(*) > 1 in SQL?

easy

A. To sort the table alphabetically

B. To find duplicate values in a column

C. To delete rows from a table

D. To create a new table

Solution

1. Step 1: Understand GROUP BY usage

   GROUP BY groups rows that have the same value in specified columns.

2. Step 2: Use HAVING COUNT(*) > 1 to filter groups

   HAVING COUNT(*) > 1 keeps only groups with more than one row, meaning duplicates.

3. Final Answer:

   To find duplicate values in a column -> Option B

4. Quick Check:

   GROUP BY + HAVING COUNT(*) > 1 = Find duplicates [OK]

Hint: Use GROUP BY with HAVING COUNT(*) > 1 to spot duplicates fast [OK]

Common Mistakes:

• Confusing HAVING with WHERE clause
• Using COUNT(column) instead of COUNT(*)
• Not grouping by the correct column

2. Which of the following SQL queries correctly finds duplicate email values in a table named users?

easy

A. SELECT email FROM users GROUP BY email HAVING COUNT(*) > 1;

B. SELECT email FROM users WHERE COUNT(email) > 1;

C. SELECT email FROM users GROUP BY email WHERE COUNT(*) > 1;

D. SELECT email FROM users HAVING COUNT(email) > 1;

Solution

1. Step 1: Check correct syntax for grouping and filtering

   GROUP BY groups rows; HAVING filters groups. WHERE cannot filter aggregates.

2. Step 2: Identify correct query

   SELECT email FROM users GROUP BY email HAVING COUNT(*) > 1; uses GROUP BY email and HAVING COUNT(*) > 1 correctly.

3. Final Answer:

   SELECT email FROM users GROUP BY email HAVING COUNT(*) > 1; -> Option A

4. Quick Check:

   GROUP BY + HAVING filters duplicates correctly [OK]

Hint: Use HAVING, not WHERE, to filter grouped results [OK]

Common Mistakes:

• Using WHERE with aggregate functions
• Placing WHERE after GROUP BY
• Using COUNT(column) incorrectly in WHERE

3. Given the table orders with column customer_id, what will this query return?

SELECT customer_id FROM orders GROUP BY customer_id HAVING COUNT(*) > 2;

medium

A. All customer IDs with exactly 2 orders

B. All customer IDs regardless of order count

C. All customer IDs with less than 2 orders

D. All customer IDs with more than 2 orders

Solution

1. Step 1: Understand HAVING COUNT(*) > 2 condition

   This filters groups where the count of rows is greater than 2.

2. Step 2: Apply to customer_id groups

   Only customer IDs with more than 2 orders appear in the result.

3. Final Answer:

   All customer IDs with more than 2 orders -> Option D

4. Quick Check:

   HAVING COUNT(*) > 2 means count > 2 [OK]

Hint: HAVING COUNT(*) > N finds groups with more than N rows [OK]

Common Mistakes:

• Thinking it finds exactly 2 instead of more than 2
• Confusing WHERE and HAVING clauses
• Ignoring GROUP BY effect

4. Identify the error in this query to find duplicate username values:

SELECT username FROM users WHERE COUNT(username) > 1 GROUP BY username;

medium

A. Missing ORDER BY clause

B. GROUP BY should come before WHERE

C. COUNT() cannot be used in WHERE clause

D. COUNT() should be COUNT(DISTINCT username)

Solution

1. Step 1: Check WHERE clause usage

   WHERE cannot filter on aggregate functions like COUNT().

2. Step 2: Correct clause to use HAVING

   HAVING is used to filter groups after GROUP BY with aggregates.

3. Final Answer:

   COUNT() cannot be used in WHERE clause -> Option C

4. Quick Check:

   Aggregates need HAVING, not WHERE [OK]

Hint: Use HAVING, not WHERE, to filter aggregates [OK]

Common Mistakes:

• Using WHERE with aggregate functions
• Placing GROUP BY after WHERE
• Confusing COUNT() usage

5. You want to find duplicate product_code values in a large inventory table but also want to see how many times each duplicate appears. Which query is the most efficient and correct?

hard

A. SELECT product_code, COUNT(*) AS count FROM inventory GROUP BY product_code HAVING count > 1;

B. SELECT product_code, COUNT(*) AS count FROM inventory WHERE COUNT(*) > 1 GROUP BY product_code;

C. SELECT product_code FROM inventory GROUP BY product_code HAVING COUNT(*) > 1 ORDER BY product_code;

D. SELECT product_code, COUNT(product_code) FROM inventory GROUP BY product_code WHERE COUNT(product_code) > 1;

Solution

1. Step 1: Check correct use of GROUP BY and HAVING

   SELECT product_code, COUNT(*) AS count FROM inventory GROUP BY product_code HAVING count > 1; groups by product_code and filters groups with count > 1 using HAVING, which is correct.

2. Step 2: Verify alias usage and efficiency

   Using COUNT(*) AS count allows filtering with HAVING count > 1 efficiently and shows counts.

3. Final Answer:

   SELECT product_code, COUNT(*) AS count FROM inventory GROUP BY product_code HAVING count > 1; -> Option A

4. Quick Check:

   GROUP BY + HAVING with alias count shows duplicates and counts [OK]

Hint: Use HAVING with COUNT(*) alias to filter and show duplicates count [OK]

Common Mistakes:

• Using WHERE with COUNT()
• Placing WHERE after GROUP BY
• Not selecting count to see duplicate frequency