Drop Duplicate Rows

Difficulty: Easy | Acceptance: 85.10% | Paid: No Topics: N/A

You are given a DataFrame customers containing columns customer_id, name, and email. Remove all rows that are duplicates of another row, keeping only the first occurrence.

The result should contain only unique rows based on all columns.

• Examples
• Constraints
• Approach 1: Built-in Methods
• Approach 2: Hash Set Tracking
• Approach 3: Sorting and Grouping

Examples

Example 1

Input:

+-------------+--------+----------+
| customer_id | name   | email    |
+-------------+--------+----------+
| 1           | John   | john@example.com |
| 2           | Alice  | alice@example.com |
| 3           | John   | john@example.com |
| 4           | Bob    | bob@example.com   |
| 5           | Alice  | alice@example.com |
+-------------+--------+----------+

Output:

+-------------+--------+----------+
| customer_id | name   | email    |
+-------------+--------+----------+
| 1           | John   | john@example.com |
| 2           | Alice  | alice@example.com |
| 4           | Bob    | bob@example.com   |
+-------------+--------+----------+

Explanation: There are two duplicate rows: one where customer_id is 3 (same as 1) and one where customer_id is 5 (same as 2). We keep the first occurrence of each unique row.

Example 2

Input:

+-------------+--------+----------+
| customer_id | name   | email    |
+-------------+--------+----------+
| 1           | John   | john@example.com |
| 2           | Jane   | jane@example.com |
| 3           | John   | john@example.com |
+-------------+--------+----------+

Output:

+-------------+--------+----------+
| customer_id | name   | email    |
+-------------+--------+----------+
| 1           | John   | john@example.com |
| 2           | Jane   | jane@example.com |
+-------------+--------+----------+

Constraints

0 <= customers.length <= 1000

Approach 1: Built-in Methods

Intuition Most data processing libraries provide optimized functions to handle duplicate removal natively. Utilizing these built-in methods is the most efficient and readable approach.

Steps

• Use the library’s specific function to drop duplicates.
• Ensure the operation considers all columns to identify duplicates.
• Return the resulting data structure.

import pandas as pd

def dropDuplicateRows(customers: pd.DataFrame) -> pd.DataFrame:
    return customers.drop_duplicates()

Complexity

• Time: O(n) on average for hash-based operations, though serialization in some languages adds overhead.
• Space: O(n) to store the unique rows.
• Notes: Python’s Pandas is highly optimized. In other languages, serialization (like JSON.stringify) creates overhead.

Approach 2: Hash Set Tracking

Intuition We can iterate through the dataset once, maintaining a record of rows we have already encountered. If a row has been seen before, we skip it; otherwise, we add it to our result.

Steps

• Initialize an empty Set to store unique identifiers of rows.
• Initialize an empty list/array for the result.
• Iterate through each row in the input.
• Convert the row into a hashable string key.
• If the key is not in the Set, add the row to the result and add the key to the Set.
• Return the result.

import pandas as pd

def dropDuplicateRows(customers: pd.DataFrame) -> pd.DataFrame:
    seen = set()
    result = []
    for index, row in customers.iterrows():
        # Create a tuple of the row values to use as a hashable key
        key = tuple(row)
        if key not in seen:
            seen.add(key)
            result.append(row)
    return pd.DataFrame(result)

Complexity

• Time: O(n * m) where n is the number of rows and m is the number of columns (due to string concatenation/joining).
• Space: O(n) to store the keys and result.
• Notes: This approach is generic and works in any language, though slightly slower than built-in optimized methods.

Approach 3: Sorting and Grouping

Intuition If we sort the rows, duplicate rows will be adjacent to each other. We can then iterate through the sorted list and keep a row only if it is different from the previous one.

Steps

• Sort the dataset based on all columns.
• Initialize a result list.
• Iterate through the sorted rows.
• If the current row is different from the last row added to the result, add it.
• Return the result.

import pandas as pd

def dropDuplicateRows(customers: pd.DataFrame) -> pd.DataFrame:
    # Sort by all columns to bring duplicates together
    customers_sorted = customers.sort_values(by=customers.columns.tolist())
    # Drop duplicates while keeping the first occurrence (which is now the first in sorted order)
    # Note: This changes the original order of rows.
    return customers_sorted.drop_duplicates()

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting implementation.
• Notes: This approach is generally slower than hash-based methods (O(n)) due to the sorting step, and it does not preserve the original order of rows.