SUNION, SINTER, SDIFF set operations in Redis - Time & Space Complexity

Time Complexity: SUNION, SINTER, SDIFF set operations

O(N)

Understanding Time Complexity

When working with Redis sets, it's important to know how the time to perform operations grows as the sets get bigger.

We want to understand how the cost changes when combining or comparing sets using SUNION, SINTER, and SDIFF.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

# Get union of sets
SUNION set1 set2 set3

# Get intersection of sets
SINTER set1 set2 set3

# Get difference of sets
SDIFF set1 set2 set3
    

These commands combine or compare multiple sets to produce a new set based on union, intersection, or difference.

Identify Repeating Operations

Look at what repeats when Redis processes these commands.

• Primary operation: Scanning elements of each input set to compare or combine them.
• How many times: Each element in each set is checked once during the operation.

How Execution Grows With Input

As the sets get bigger, Redis must look at more elements.

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

Pattern observation: The work grows roughly in direct proportion to the total number of elements across all sets.

Final Time Complexity

Time Complexity: O(N)

This means the time to complete the operation grows linearly with the total number of elements in all input sets.

Common Mistake

[X] Wrong: "These set operations always take the same time no matter how big the sets are."

[OK] Correct: Actually, Redis must look at each element to combine or compare sets, so bigger sets take more time.

Interview Connect

Understanding how set operations scale helps you explain performance in real projects and shows you can think about efficiency clearly.

Self-Check

What if we used SUNIONSTORE to save the union result in a new set? How would that affect the time complexity?

Practice

1. What does the Redis command SUNION do when applied to multiple sets?

easy

A. It returns all unique elements from all given sets combined.

B. It returns only the elements common to all given sets.

C. It returns elements unique to the first set only.

D. It deletes all the given sets from the database.

Solution

1. Step 1: Understand SUNION operation

   The SUNION command merges all elements from the given sets and removes duplicates.

2. Step 2: Compare with other set operations

   SINTER returns only common elements, SDIFF returns unique elements from the first set, so SUNION is the only one that merges all uniquely.

3. Final Answer:

   It returns all unique elements from all given sets combined. -> Option A

4. Quick Check:

   SUNION = all unique elements combined [OK]

Hint: SUNION combines all sets without duplicates [OK]

Common Mistakes:

• Confusing SUNION with SINTER (common elements)
• Thinking SUNION returns only first set elements
• Assuming SUNION deletes sets

2. Which of the following is the correct syntax to find the intersection of two sets set1 and set2 in Redis?

easy

A. SINTER set1 set2

B. SUNION set1 set2

C. SDIFF set1 set2

D. SINTERSECTION set1 set2

Solution

1. Step 1: Recall Redis command for intersection

   The correct Redis command to find common elements is SINTER.

2. Step 2: Check syntax correctness

   The syntax is SINTER key1 key2 .... SINTER set1 set2 matches this exactly.

3. Final Answer:

   SINTER set1 set2 -> Option A

4. Quick Check:

   SINTER syntax = SINTER keys [OK]

Hint: Use SINTER for intersection syntax [OK]

Common Mistakes:

• Using SUNION instead of SINTER
• Using non-existent command SINTERSECTION
• Confusing SDIFF with intersection

3. Given the following Redis sets:
set1 = {"apple", "banana", "cherry"}
set2 = {"banana", "date", "fig"}
What is the result of SINTER set1 set2?

medium

A. ["apple", "banana", "cherry", "date", "fig"]

B. ["banana"]

C. ["apple", "cherry"]

D. ["date", "fig"]

Solution

1. Step 1: Identify common elements between set1 and set2

   Elements in set1: apple, banana, cherry; set2: banana, date, fig. The only common element is banana.

2. Step 2: Understand SINTER output

   SINTER returns only elements present in all sets, so the result is ["banana"].

3. Final Answer:

   ["banana"] -> Option B

4. Quick Check:

   SINTER common elements = ["banana"] [OK]

Hint: SINTER returns only common elements [OK]

Common Mistakes:

• Listing all elements instead of common ones
• Confusing SINTER with SUNION or SDIFF
• Including elements unique to one set

4. You run the command SDIFF set1 set2 but get an unexpected empty result. Given:
set1 = {"cat", "dog"}
set2 = {"cat", "dog", "mouse"}
What is the likely reason?

medium

A. set1 is empty, so SDIFF returns empty.

B. SDIFF syntax requires only one set argument.

C. Redis does not support SDIFF with these sets.

D. All elements of set1 are also in set2, so no unique elements remain.

Solution

1. Step 1: Understand SDIFF behavior

   SDIFF returns elements in the first set that are not in the other sets.

2. Step 2: Analyze given sets

   set1 has "cat" and "dog"; set2 has "cat", "dog", and "mouse". Since all set1 elements are in set2, SDIFF returns an empty set.

3. Final Answer:

   All elements of set1 are also in set2, so no unique elements remain. -> Option D

4. Quick Check:

   SDIFF unique first set elements = empty [OK]

Hint: SDIFF returns only unique first set elements [OK]

Common Mistakes:

• Assuming SDIFF requires only one set
• Thinking SDIFF returns common elements
• Believing Redis lacks SDIFF support

5. You have three Redis sets:
setA = {"red", "blue", "green"}
setB = {"blue", "yellow"}
setC = {"green", "yellow", "black"}
Which command returns elements that are in setA but not in setB or setC?

hard

A. SUNION setA setB setC

B. SINTER setA setB setC

C. SDIFF setA setB setC

D. SDIFF setB setA setC

Solution

1. Step 1: Understand SDIFF with multiple sets

   SDIFF returns elements in the first set that are not in any of the other sets.

2. Step 2: Apply SDIFF to given sets

   Elements in setA: red, blue, green. Elements in setB and setC combined: blue, yellow, green, black. Elements unique to setA are only "red".

3. Step 3: Verify command correctness

   SDIFF setA setB setC uses SDIFF with setA first, then setB and setC, which matches the requirement.

4. Final Answer:

   SDIFF setA setB setC -> Option C

5. Quick Check:

   SDIFF first set minus others = unique elements [OK]

Hint: Use SDIFF with first set then others to find unique elements [OK]

Common Mistakes:

• Using SINTER or SUNION instead of SDIFF
• Reversing set order in SDIFF
• Expecting SDIFF to return common elements