Null and duplicate detection in Apache Spark - Time & Space Complexity

Time Complexity: Null and duplicate detection

O(n log n)

Understanding Time Complexity

We want to know how the time needed to find nulls and duplicates changes as the data grows.

How does checking for missing or repeated data scale with bigger datasets?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.sql import SparkSession

spark = SparkSession.builder.getOrCreate()
df = spark.read.csv('data.csv', header=True, inferSchema=True)

# Count nulls in column 'age'
null_count = df.filter(df['age'].isNull()).count()

# Count number of duplicated row groups
duplicate_count = df.groupBy(df.columns).count().filter('count > 1').count()

This code counts how many rows have null values in the 'age' column and how many unique row combinations appear more than once (i.e., number of duplicated groups).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows to check for nulls and grouping all rows to find duplicates.
• How many times: Each row is examined once for null check; grouping requires sorting or hashing all rows once.

How Execution Grows With Input

As the number of rows grows, the time to check nulls grows linearly, and grouping for duplicates grows a bit more due to sorting or hashing.

Input Size (n)	Approx. Operations
10	About 10 checks for nulls, small grouping effort
100	About 100 checks, grouping takes more time but still manageable
1000	About 1000 checks, grouping cost grows but still roughly proportional to n log n

Pattern observation: Null checks grow directly with data size; duplicate detection grows a bit faster due to grouping.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because grouping duplicates involves sorting or hashing all data.

Common Mistake

[X] Wrong: "Checking for duplicates is just as fast as checking for nulls because both scan the data once."

[OK] Correct: Duplicate detection requires grouping or sorting, which adds extra steps beyond a simple scan, making it slower as data grows.

Interview Connect

Understanding how data checks scale helps you explain your approach clearly and shows you know what happens behind the scenes when working with big data.

Self-Check

"What if we used approximate methods like sampling to detect duplicates? How would the time complexity change?"

Practice

1. What does null detection in Apache Spark help you find in a dataset?

easy

A. Columns with only numeric data

B. Rows with duplicate values

C. Missing or empty values in columns

D. The total number of rows

Solution

1. Step 1: Understand null detection purpose

   Null detection identifies missing or empty values in dataset columns.

2. Step 2: Differentiate from duplicates

   Duplicate detection finds repeated rows, not missing values.

3. Final Answer:

   Missing or empty values in columns -> Option C

4. Quick Check:

   Null detection = Missing values [OK]

Hint: Null detection finds missing data, not duplicates [OK]

Common Mistakes:

• Confusing null detection with duplicate detection
• Thinking null means zero or empty string
• Assuming null detection counts rows

2. Which Apache Spark DataFrame method is used to find duplicate rows?

easy

A. count()

B. isNull()

C. fillna()

D. dropDuplicates()

Solution

1. Step 1: Identify method for duplicates

   The method dropDuplicates() removes duplicate rows from a DataFrame.

2. Step 2: Confirm other methods' purposes

   isNull() checks for nulls, fillna() fills nulls, count() counts rows.

3. Final Answer:

   dropDuplicates() -> Option D

4. Quick Check:

   Duplicates removed by dropDuplicates() [OK]

Hint: Use dropDuplicates() to find/remove duplicates [OK]

Common Mistakes:

• Using isNull() to find duplicates
• Confusing fillna() with duplicate removal
• Trying count() to detect duplicates

3. Given this Spark code snippet, what is the output?

from pyspark.sql import SparkSession
spark = SparkSession.builder.getOrCreate()
data = [(1, 'A'), (2, None), (1, 'A'), (3, 'C'), (None, 'D')]
df = spark.createDataFrame(data, ['id', 'value'])
null_count = df.filter(df['id'].isNull()).count()
duplicate_count = df.count() - df.dropDuplicates().count()
print(null_count, duplicate_count)

medium

A. 1 2

B. 1 1

C. 0 2

D. 2 1

Solution

1. Step 1: Count nulls in 'id'

   There is one row with id = None, so null_count = 1.

2. Step 2: Calculate duplicates

   Total rows = 5, dropDuplicates() removes one duplicate row (1, 'A'), so duplicate_count = 5 - 4 = 1.

3. Final Answer:

   1 1 -> Option B

4. Quick Check:

   Nulls = 1, Duplicates = 1 [OK]

Hint: Count nulls with filter, duplicates by count difference [OK]

Common Mistakes:

• Counting duplicates before removing nulls
• Miscounting duplicates as 2
• Ignoring None as null

4. What is wrong with this Spark code to detect duplicates?

df = spark.createDataFrame([(1, 'x'), (1, 'x'), (2, 'y')], ['id', 'val'])
duplicates = df.dropDuplicates().count()
print(duplicates)

medium

A. dropDuplicates() removes duplicates, so count shows unique rows, not duplicates

B. The code will raise a syntax error

C. dropDuplicates() counts duplicates instead of removing them

D. The DataFrame is empty, so count is zero

Solution

1. Step 1: Understand dropDuplicates() behavior

   dropDuplicates() removes duplicate rows, so count() returns unique row count.

2. Step 2: Identify mistake in duplicate detection

   Counting duplicates requires comparing total count with unique count, not just unique count alone.

3. Final Answer:

   dropDuplicates() removes duplicates, so count shows unique rows, not duplicates -> Option A

4. Quick Check:

   dropDuplicates() = unique rows, not duplicates count [OK]

Hint: Compare total count and dropDuplicates count to find duplicates [OK]

Common Mistakes:

• Assuming dropDuplicates() counts duplicates
• Expecting syntax error from correct code
• Ignoring difference between total and unique counts

5. You have a Spark DataFrame with columns 'user_id' and 'email'. You want to remove rows where 'email' is null and also remove duplicate rows based on 'user_id'. Which code snippet correctly does this?

hard

A. df.filter(df['email'].isNotNull()).dropDuplicates(['user_id'])

B. df.dropDuplicates(['user_id']).filter(df['email'].isNull())

C. df.filter(df['email'].isNull()).dropDuplicates(['email'])

D. df.dropDuplicates().filter(df['email'].isNotNull())

Solution

1. Step 1: Filter out rows with null emails

   Use filter(df['email'].isNotNull()) to keep only rows with email values.

2. Step 2: Remove duplicates by 'user_id'

   Use dropDuplicates(['user_id']) to remove rows with repeated user_id values.

3. Final Answer:

   df.filter(df['email'].isNotNull()).dropDuplicates(['user_id']) -> Option A

4. Quick Check:

   Filter null emails then drop duplicates by user_id [OK]

Hint: Filter nulls first, then drop duplicates by key column [OK]

Common Mistakes:

• Filtering null emails after dropping duplicates
• Dropping duplicates on wrong column
• Filtering for null emails instead of non-null