Back to Stream Practice: Collections & Numbers
Q1Question 1 of 11

Intersection / common elements of two lists: filter(set::contains), HashSet for O(1)

Key Concepts
  • Convert the lookup list to a HashSet for O(1) contains checks before filtering
  • filter(set::contains) on the first list keeps only elements present in both lists
  • distinct() removes duplicates from the result when the first list has repeated common elements
  • The naive filter(list2::contains) is O(n * m) because List.contains is O(m) per call
  • The HashSet approach runs in O(n + m) total time
  • The same pattern works for difference (filter with negate) and symmetric difference

Definition

Convert the second list to a HashSet for O(1) lookups, then filter the first list with set::contains and apply distinct() to remove duplicates.
  • new HashSet<>(list2) converts the second list to a Set for O(1) contains checks.
  • list1.stream().filter(set2::contains) keeps only elements from list1 that exist in list2.
  • distinct() removes duplicates from the result when list1 contains repeated elements that are also in list2.
  • The naive approach filter(list2::contains) is O(n * m) because List.contains is O(m) for each of n elements.
  • The HashSet approach runs in O(n + m): O(m) to build the Set, O(n) to filter.
  • The pattern generalizes to difference (negate the filter) and symmetric difference.

Rajesh holds stocks [RELIANCE, TCS, HDFC, INFY]. Priya holds [TCS, WIPRO, HDFC, BAJAJ]. To find common holdings, convert Priya's list to a fast-lookup set, then scan Rajesh's list and keep only stocks that Priya also holds. Result: [TCS, HDFC].

Understanding the Concepts

What is list intersection?

Intersection finds elements that appear in both lists. The result contains only elements common to both.

How do you find the intersection efficiently?

JAVA
package com.bank.util;

import java.util.*;

public class ListIntersectionDemo {
    public static void main(String[] args) {
        List<String> rajesh = List.of("RELIANCE", "TCS", "HDFC", "INFY", "TCS");
        List<String> priya = List.of("TCS", "WIPRO", "HDFC", "BAJAJ");

        // GOOD: O(n + m) with HashSet
        Set<String> priyaSet = new HashSet<>(priya);
        List<String> common = rajesh.stream()
            .filter(priyaSet::contains)
            .distinct()
            .toList();

        System.out.println("Common: " + common);
    }
}
TEXT
Common: [TCS, HDFC]

Why is the naive approach slow?

JAVA
// BAD: O(n * m) -- list.contains scans linearly for each element
List<String> slow = rajesh.stream()
    .filter(priya::contains)   // O(m) per element
    .distinct()
    .toList();

For 500 elements in each list: HashSet approach = ~1,000 operations. Naive approach = ~250,000 operations.

How do you find the difference (elements in list1 but not in list2)?

JAVA
// Difference: elements in rajesh but NOT in priya
List<String> difference = rajesh.stream()
    .filter(s -> !priyaSet.contains(s))
    .distinct()
    .toList();

System.out.println("Only Rajesh: " + difference);  // [RELIANCE, INFY]

How do you find the symmetric difference?

JAVA
// Symmetric difference: elements in either but not both
Set<String> rajeshSet = new HashSet<>(rajesh);
Set<String> priyaOnlySet = new HashSet<>(priya);

List<String> symDiff = new ArrayList<>();
rajesh.stream().filter(s -> !priyaOnlySet.contains(s)).distinct().forEach(symDiff::add);
priya.stream().filter(s -> !rajeshSet.contains(s)).distinct().forEach(symDiff::add);

System.out.println("Symmetric diff: " + symDiff);
// [RELIANCE, INFY, WIPRO, BAJAJ]

What about intersection with custom objects?

For custom objects, ensure equals and hashCode are based on the comparison field.

JAVA
record Account(String id, String holder) {}

// Intersection by account ID
Set<String> branchAccountIds = branchAccounts.stream()
    .map(Account::id)
    .collect(Collectors.toSet());

List<Account> common = hqAccounts.stream()
    .filter(a -> branchAccountIds.contains(a.id()))
    .toList();

What are common mistakes?

WRONG: Forgetting distinct() when the first list has duplicates.

JAVA
// rajesh has TCS twice -- without distinct, TCS appears twice in result
List<String> withDupes = rajesh.stream()
    .filter(priyaSet::contains)
    .toList();  // [TCS, HDFC, TCS] -- TCS appears twice!

CORRECT: Always add distinct() for clean results.

What should a senior engineer know?

  • Always convert the smaller list to a HashSet for optimal performance. If list1 has 1 million elements and list2 has 100, convert list2 to a Set.
  • For parallel streams, HashSet.contains is not thread-safe. Use ConcurrentHashMap.newKeySet() or ensure the set is not modified during the stream operation (immutable reference is fine).
  • The retainAll method on Set computes intersection in place, but it mutates the set. The stream approach is non-mutating.

Visual Overview

DIAGRAM
  rajesh: [RELIANCE, TCS, HDFC, INFY, TCS]
  priya:  [TCS, WIPRO, HDFC, BAJAJ]
       │
       ▼
  priyaSet = HashSet{TCS, WIPRO, HDFC, BAJAJ}
       │
       ▼
  rajesh.stream().filter(priyaSet::contains)
  ┌──────────────────────────────────────┐
  │ RELIANCE → contains? NO  → skip     │
  │ TCS      → contains? YES → keep     │
  │ HDFC     → contains? YES → keep     │
  │ INFY     → contains? NO  → skip     │
  │ TCS      → contains? YES → keep     │
  └──────────────┬───────────────────────┘
                 │
                 ▼
  distinct() → [TCS, HDFC]

Key Takeaway

Finding common elements between two lists uses the pattern: convert the second list to a HashSet for O(1) contains lookups, then filter the first list with filter(set::contains), and apply distinct() to remove duplicates. This runs in O(n + m) time. The naive approach filter(list2::contains) is O(n * m) because List.contains scans linearly.

The same pattern adapts for difference (negate the filter) and symmetric difference (combine both differences). Always convert the smaller list to a Set for optimal performance.

At National Bank of India, Rajesh and Priya's stock portfolios are compared. The HashSet approach finds their common holdings (TCS, HDFC) in linear time.

Remember one sentence: always convert the lookup list to a HashSet before filtering, turning O(n * m) into O(n + m).

---

Share
Use ← → arrow keys to navigate