Intersection

Given two slices of integers, return the values that appear in both, with no duplicates, sorted in ascending order.

intersection(a, b)

Input format: a | b — two space-separated integer lists divided by a pipe. Output the shared values, sorted, space-separated (empty line if none).

Examples

intersection([]int{1, 2, 3, 4}, []int{3, 4, 5})  // → [3, 4]
intersection([]int{1, 2}, []int{3, 4})           // → []
intersection([]int{2, 2, 3}, []int{2, 3, 3})     // → [2, 3]

Walkthrough

Thinking it through

You want the values shared between two lists, with no duplicates in the answer. The brute-force instinct: for every value in the first list, scan the whole second list to check if it's there. That works, but the total work grows with the product of the two lists' sizes — expensive fast as either grows.

The real question being asked repeatedly

The brute-force approach spends nearly all its time answering the same question: "is this value present in the other list?" That's a membership question, and a hash set answers those in constant time on average, versus scanning a list in time proportional to its length.

Building the approach

Convert one list into a set — a one-time cost proportional to that list's size.
Walk the other list. For each value, ask the set: "do you contain this?" A yes means it's part of the intersection.
As soon as you use a value, remove it from the set. Without this, a value appearing once in the set but multiple times in the second list would get added to the result more than once. Removing it after the first match means later duplicates simply won't find it anymore.
Sort the collected values at the end — neither the set's iteration order nor the second list's order is guaranteed sorted.

Why this is efficient

Building the set costs time proportional to the first list's size; scanning the second list with constant-time lookups costs time proportional to its size. Together that's linear in the combined sizes, instead of the multiplicative cost of comparing every pair. The tradeoff is extra memory for the set — usually a good deal for a large cut in running time.

Why removing from the set (not just checking) matters

"Check and remove" beats "check and mark used" with a separate structure: removing from the set is a single O(1) operation that both answers "was it there?" and prevents reuse, with no extra bookkeeping.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.