LearnWithKiriti

Intersection of Two Sorted Arrays

πŸ’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.
Play
On this page
  1. Revision notes
  2. Brute
  3. Optimal: Two Pointers
  4. Optimal: Binary Search
  5. Optimal: Hash Map Counts
  6. Follow-up 3: On Disk

Revision notes

Intersection of Two Sorted Arrays (LeetCode 350)

Short revision notes for the LearnWithKiriti episode, starring Kodee.

Problem

Two arrays, shelfA and shelfB. Return every value that appears in both. Each value appears as many times as it shows up in BOTH arrays, so the count is min(countA, countB).

shelfA = [1, 2, 2, 4]
shelfB = [2, 4, 4, 5]
answer = [2, 4]

Why only one 2? shelfB has only ONE 2. Why only one 4? shelfA has only ONE 4.

Blank mind in the interview? Ask three small questions

  1. Can I solve it by hand on a tiny example?
  2. What is the dumbest thing that works? (brute force)
  3. What does it cost? Then improve it one step at a time.

Never jump straight to the optimal answer. It looks memorised. Start with the brute force, state its cost, then improve it.

The approaches

Folder Idea Use it when
Brute For each book in A, find an unused copy in B (taken) Warm-up only
Optimal/1-TwoPointers Compare the two fronts, move the smaller one Both sorted (follow-up 1)
Optimal/2-BinarySearch For each book in the small array, binary search the big one Sorted, and one array is much smaller (follow-up 2)
Optimal/3-HashMapCounts Count the smaller array, walk the bigger one Not sorted (+ intersectSmallValues when values are 0 to 1000)
FollowUp3-OnDisk Count the small array, stream the big one chunk by chunk The big array lives on disk (follow-up 3)

Which one should I pick?

Are both sorted?
β”œβ”€β”€ Yes ── Is one side tiny? ── Yes ── Binary Search
β”‚                            └─ No ─── Two Pointers
└── No ─── Do they fit in memory?
           β”œβ”€β”€ Yes ── Hash Map Counts of the smaller one
           β”‚          (values 0 to 1000? intersectSmallValues)
           └── No ─── Counts of the small one + stream the big one (intersectOnDisk)
                      Both huge? External sort, then Two Pointers while streaming

Complexity (n = size of shelfA, m = size of shelfB)

Approach Time Extra space (not counting common)
Brute (nested loops + taken) O(n x m) O(m)
Two Pointers (sorted) O(n + m) O(1)
Binary Search (sorted) O(small x log big) O(1)
Hash Map Counts (any order) O(n + m) O(min(n, m))
Small values (0..1000) O(n + m) O(1), 1001 slots
On disk (counts of the small shelf) O(n + m) O(small) + one chunk
Sort first, then Two Pointers O(n log n + m log m) depends on the sort

Space, honestly: the answer list common is returned, so it is not counted as extra space. Two Pointers is O(1) extra only because the inputs are already sorted. If you sort them first, the sort’s memory counts:

  • Java Arrays.sort on ints and C++ std::sort use about O(log n) stack.
  • Python sort and JavaScript (V8) use TimSort, which can take up to O(n).

Folder layout

Every approach folder has pseudocode.md and the same code in Java/, C++/, Python/ and JS/. Every file runs as it is and prints Intersection: [2, 4].

javac IntersectSorted.java && java IntersectSorted
g++ intersect_sorted.cpp -o intersect_sorted && ./intersect_sorted
python intersect_sorted.py
node intersectSorted.js

Submitting on LeetCode

LeetCode 350 names the method intersect(nums1, nums2) and its arrays are not sorted. You can submit Hash Map Counts as it is (rename the method). For Two Pointers or Binary Search, sort both arrays first.

Rebuild it (pause, say it out loud, then check)

  • The key observation is… the arrays are sorted, so the smaller front can never meet a partner later.
  • When the fronts are equal I… add one copy and move both pointers.
  • It costs… O(n + m) time, O(1) extra space.

Next up: Majority Element I.

brute

Brute

Brute Force: nested loops + taken

Idea

For every book in shelfA, scan shelfB for a copy you have not used yet. Mark it taken, so the same copy can’t be paired twice.

Pseudocode

intersectBrute(shelfA, shelfB):
    common = empty list
    taken = list of false, one per book of shelfB
    for book in shelfA:
        for spotB from 0 to sizeB - 1:
            if taken[spotB] is false and shelfB[spotB] == book:
                taken[spotB] = true
                add book to common
                stop the inner loop
    return common

Why taken?

Without it, the second 2 in shelfA grabs the SAME 2 in shelfB again. You get [2, 2, 4], which is wrong. shelfB has only one 2.

Dry run: shelfA = [1, 2, 2, 4], shelfB = [2, 4, 4, 5]

book scan of shelfB taken common
1 no 1 anywhere F F F F []
2 spot 0 is 2 and free T F F F [2]
2 spot 0 is taken, no other 2 T F F F [2]
4 spot 1 is 4 and free T T F F [2, 4]

Cost

  • Time O(n x m): for each of the n books, scan up to m books.
  • Extra space O(m), for taken.
  • It ignores the gift that both arrays are sorted. The optimal answers use it.
IntersectBrute.java
import java.util.ArrayList;
import java.util.List;

public class IntersectBrute {

    static List<Integer> intersectBrute(int[] shelfA, int[] shelfB) {
        int sizeA = shelfA.length;
        int sizeB = shelfB.length;
        boolean[] taken = new boolean[sizeB];
        List<Integer> common = new ArrayList<>();
        for (int book : shelfA) {
            for (int spotB = 0; spotB < sizeB; spotB++) {
                if (!taken[spotB] && shelfB[spotB] == book) {
                    taken[spotB] = true;
                    common.add(book);
                    break;
                }
            }
        }
        return common;
    }

    public static void main(String[] args) {
        int[] shelfA = {1, 2, 2, 4};
        int[] shelfB = {2, 4, 4, 5};
        List<Integer> common = intersectBrute(shelfA, shelfB);
        System.out.println("Intersection: " + common);
    }
}
optimal

Optimal: Two Pointers

Optimal 1: Two Pointers (both sorted, LeetCode follow-up 1)

Derive it under stress

  1. Is there an order I can use? Yes, both arrays are sorted.
  2. Where can the answer hide? Look at the fronts. Everything behind a front is even bigger.
  3. What does the smaller front tell me? It can never find a partner, because every book left on the other shelf is bigger. So skip it.

Pseudocode

intersectSorted(shelfA, shelfB):
    common = empty list
    spotA = 0
    spotB = 0
    while spotA < sizeA and spotB < sizeB:
        if shelfA[spotA] < shelfB[spotB]:
            spotA = spotA + 1
        else if shelfA[spotA] > shelfB[spotB]:
            spotB = spotB + 1
        else:
            add shelfA[spotA] to common
            spotA = spotA + 1
            spotB = spotB + 1
    return common

Why it works (proof)

  • Smaller front: say shelfA[spotA] < shelfB[spotB]. Every book from spotB onwards is at least shelfB[spotB], so it is bigger than shelfA[spotA]. That book has no partner left, and skipping it loses nothing.
  • Equal fronts: pair them. Each copy is used exactly once, so you get min(countA, countB) copies of every value.
  • One shelf runs out: nothing left to pair with, so stop. No leftover loops are needed.

Dry run: shelfA = [1, 2, 2, 4], shelfB = [2, 4, 4, 5]

spotA spotB compare action common
0 0 1 < 2 spotA++ []
1 0 2 == 2 add 2, move both [2]
2 1 2 < 4 spotA++ [2]
3 1 4 == 4 add 4, move both [2, 4]
4 2 shelfA ran out stop [2, 4]

Cost

  • Time O(n + m): every step moves at least one pointer.
  • Extra space O(1).
  • Same idea as the merge step of Merge Sort, and the Union episode.
IntersectSorted.java
import java.util.ArrayList;
import java.util.List;

public class IntersectSorted {

    static List<Integer> intersectSorted(int[] shelfA, int[] shelfB) {
        List<Integer> common = new ArrayList<>();
        int sizeA = shelfA.length;
        int sizeB = shelfB.length;
        int spotA = 0;
        int spotB = 0;
        while (spotA < sizeA && spotB < sizeB) {
            if (shelfA[spotA] < shelfB[spotB]) {
                spotA++;
            } else if (shelfA[spotA] > shelfB[spotB]) {
                spotB++;
            } else {
                common.add(shelfA[spotA]);
                spotA++;
                spotB++;
            }
        }
        return common;
    }

    public static void main(String[] args) {
        int[] shelfA = {1, 2, 2, 4};
        int[] shelfB = {2, 4, 4, 5};
        List<Integer> common = intersectSorted(shelfA, shelfB);
        System.out.println("Intersection: " + common);
    }
}
optimal

Optimal: Binary Search

Optimal 2: Binary Search (sorted, one array much smaller, LeetCode follow-up 2)

Derive it under stress

  1. Which part costs the most? Walking the huge shelf, book by book.
  2. What do I need for each small book? Only one answer: is it on the big shelf, and where?
  3. How do I find one thing fast on a sorted shelf? Binary search.

The duplicate trap: both 2s from shelfA would find the SAME 2 in shelfB. The fix is a bookmark, fromSpot. After a match, the next search starts just after it.

Pseudocode

intersectBinary(shelfA, shelfB):      # shelfA is the small shelf
    common = empty list
    fromSpot = 0
    for book in shelfA:
        found = lowerBound(shelfB, book, fromSpot)
        if found < sizeB and shelfB[found] == book:
            add book to common
            fromSpot = found + 1
    return common

lowerBound(shelf, value, fromSpot):
    low = fromSpot
    high = size of shelf
    while low < high:
        middle = low + (high - low) / 2, rounded down
        if shelf[middle] < value:
            low = middle + 1
        else:
            high = middle
    return low

lowerBound returns the first spot (from fromSpot on) whose value is at least value.

Why it works (proof)

  • Everything to the left of fromSpot is smaller, or already paired. shelfA is sorted too, so later books never need it.
  • lowerBound finds the FIRST unused copy, so each copy in shelfB is used once at most.
  • You get min(countA, countB) copies of every value.

Why not just Two Pointers and stop when the small shelf ends?

It does stop there, but the small shelf can’t end until spotB has walked up to its books.

  • shelfA = [98, 99, 100], shelfB = [1, 2, …, 100]
  • Two Pointers: spotB walks past 97 books before the first pair, about 100 steps.
  • Binary Search: lowerBound(98) needs 6 halvings, then 99 and 100 take 2 and 1 more, starting from fromSpot. That’s 9 in total.

The walking depends on the BIG shelf, so Two Pointers is O(n + m), never O(n + n). Binary Search is Two Pointers where spotB jumps instead of walking.

When does it win?

Compare small x log(big) with small + big.

  • 3 books against 100: about 3 x 7 = 21 steps, against 103.
  • 4 books against 1,000,000: about 4 x 20 = 80 steps, against 1,000,004. Binary Search wins.
  • Equal sizes: Two Pointers wins.

Dry run: shelfA = [1, 2, 2, 4], shelfB = [2, 4, 4, 5]

book search from found match? fromSpot common
1 0 0 (value 2) no 0 []
2 0 0 (value 2) yes 1 [2]
2 1 1 (value 4) no 1 [2]
4 1 1 (value 4) yes 2 [2, 4]

Cost

  • Time O(small x log big).
  • Extra space O(1).
IntersectBinary.java
import java.util.ArrayList;
import java.util.List;

public class IntersectBinary {

    static int lowerBound(int[] shelf, int value, int fromSpot) {
        int low = fromSpot;
        int high = shelf.length;
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (shelf[middle] < value) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }

    static List<Integer> intersectBinary(int[] shelfA, int[] shelfB) {
        List<Integer> common = new ArrayList<>();
        int sizeB = shelfB.length;
        int fromSpot = 0;
        for (int book : shelfA) {
            int found = lowerBound(shelfB, book, fromSpot);
            if (found < sizeB && shelfB[found] == book) {
                common.add(book);
                fromSpot = found + 1;
            }
        }
        return common;
    }

    public static void main(String[] args) {
        int[] shelfA = {1, 2, 2, 4};
        int[] shelfB = {2, 4, 4, 5};
        List<Integer> common = intersectBinary(shelfA, shelfB);
        System.out.println("Intersection: " + common);
    }
}
optimal

Optimal: Hash Map Counts

Optimal 3: Hash Map Counts (any order)

Derive it under stress

  1. Is there an order? No, so Two Pointers and Binary Search are out.
  2. What must I remember about A while I walk B? How many copies of each value are still unused.
  3. What remembers things by value? A hash map.

Count the smaller array, because memory is the cost.

Pseudocode

intersectCounts(shelfA, shelfB):
    if sizeA <= sizeB:
        smallShelf = shelfA
        bigShelf = shelfB
    else:
        smallShelf = shelfB
        bigShelf = shelfA
    counts = empty map, a missing value counts as 0
    for book in smallShelf:
        counts[book] = counts[book] + 1
    common = empty list
    for book in bigShelf:
        if counts[book] > 0:
            add book to common
            counts[book] = counts[book] - 1
    return common

Challenge: write the swap the recursive way (call yourself with the arrays swapped), and share it in the comments.

Variant: values are only 0 to 1000 (its own method)

intersectSmallValues(shelfA, shelfB):     # every value is 0 to 1000
    counts = list of 1001 zeros
    for book in shelfA:
        counts[book] = counts[book] + 1
    common = empty list
    for book in shelfB:
        if counts[book] > 0:
            add book to common
            counts[book] = counts[book] - 1
    return common

A plain array replaces the hash map. It has a fixed size of 1001, so the extra space is O(1).

Why it works (proof)

counts[v] = unused copies of v on the counted shelf. Each pairing uses one copy. When the count hits 0, further copies of v stay behind. So v is added exactly min(countA, countB) times.

Dry run: smallShelf = [1, 2, 2, 4], bigShelf = [2, 4, 4, 5]

counts = {1: 1, 2: 2, 4: 1}

book counts[book] action common
2 2 -> 1 add [2]
4 1 -> 0 add [2, 4]
4 0 skip [2, 4]
5 missing = 0 skip [2, 4]

The answer follows the walked shelf’s order. LeetCode accepts any order.

Cost

  • Time O(n + m).
  • Extra space O(min(n, m)) for the map, or O(1) (1001 slots) for the small-values method.
IntersectCounts.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IntersectCounts {

    static List<Integer> intersectCounts(int[] shelfA, int[] shelfB) {
        int[] smallShelf;
        int[] bigShelf;
        if (shelfA.length <= shelfB.length) {
            smallShelf = shelfA;
            bigShelf = shelfB;
        } else {
            smallShelf = shelfB;
            bigShelf = shelfA;
        }
        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int book : smallShelf) {
            int count = counts.getOrDefault(book, 0);
            counts.put(book, count + 1);
        }
        List<Integer> common = new ArrayList<>();
        for (int book : bigShelf) {
            int left = counts.getOrDefault(book, 0);
            if (left > 0) {
                common.add(book);
                counts.put(book, left - 1);
            }
        }
        return common;
    }

    static List<Integer> intersectSmallValues(int[] shelfA, int[] shelfB) {
        int[] counts = new int[1001];
        for (int book : shelfA) {
            counts[book]++;
        }
        List<Integer> common = new ArrayList<>();
        for (int book : shelfB) {
            int left = counts[book];
            if (left > 0) {
                common.add(book);
                counts[book] = left - 1;
            }
        }
        return common;
    }

    public static void main(String[] args) {
        int[] shelfA = {1, 2, 2, 4};
        int[] shelfB = {2, 4, 4, 5};
        List<Integer> common = intersectCounts(shelfA, shelfB);
        System.out.println("Intersection: " + common);
        List<Integer> commonSmall = intersectSmallValues(shelfA, shelfB);
        System.out.println("Intersection: " + commonSmall);
    }
}
follow-up

Follow-up 3: On Disk

Follow-up 3: the big array lives on disk, memory is small

Idea

Keep the counts of the SMALL array in memory. Read the big array one chunk at a time, check each book against the counts, then throw the chunk away.

Pseudocode

intersectOnDisk(smallShelf, bigShelfChunks):
    counts = counts of smallShelf        # fits in memory
    common = empty list
    for chunk in bigShelfChunks:         # a real program reads each chunk from a file
        for book in chunk:
            if counts[book] > 0:
                add book to common
                counts[book] = counts[book] - 1
    return common

In this code, bigShelfChunks is a list of small lists that stands in for the file. A real program would read each chunk from the file.

Dry run: smallShelf = [4, 2, 1, 2], chunks [5, 2] then [4, 4] (nothing is sorted)

counts = {4: 1, 2: 2, 1: 1}

chunk book counts[book] action common
[5, 2] 5 missing skip []
[5, 2] 2 2 -> 1 add [2]
[4, 4] 4 1 -> 0 add [2, 4]
[4, 4] 4 0 skip [2, 4]

The order never mattered: counts don’t care where a book sits. Two Pointers would have to sort first.

If BOTH are too big for memory (pseudocode only)

externalSort(shelfA)                 # sort pieces, write them out, merge them
externalSort(shelfB)
run Two Pointers, streaming both     # only the two front books in memory

External sort: sort pieces that fit in memory, write each one back to disk, then merge them. Two Pointers then needs only the two front books in memory.

Cost

  • Time O(n + m).
  • Extra space: O(small) for the counts, plus one chunk.
IntersectOnDisk.java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class IntersectOnDisk {

    static List<Integer> intersectOnDisk(int[] smallShelf, List<int[]> bigShelfChunks) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int book : smallShelf) {
            int count = counts.getOrDefault(book, 0);
            counts.put(book, count + 1);
        }
        List<Integer> common = new ArrayList<>();
        for (int[] chunk : bigShelfChunks) {
            for (int book : chunk) {
                int left = counts.getOrDefault(book, 0);
                if (left > 0) {
                    common.add(book);
                    counts.put(book, left - 1);
                }
            }
        }
        return common;
    }

    public static void main(String[] args) {
        int[] smallShelf = {4, 2, 1, 2};
        List<int[]> bigShelfChunks = new ArrayList<>();
        bigShelfChunks.add(new int[] {5, 2});
        bigShelfChunks.add(new int[] {4, 4});
        List<Integer> common = intersectOnDisk(smallShelf, bigShelfChunks);
        System.out.println("Intersection: " + common);
    }
}