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.On this page
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
- Can I solve it by hand on a tiny example?
- What is the dumbest thing that works? (brute force)
- 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.sorton ints and C++std::sortuse about O(log n) stack. - Python
sortand 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 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.
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);
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> intersectBrute(vector<int>& shelfA, vector<int>& shelfB) {
int sizeB = (int)shelfB.size();
vector<bool> taken(sizeB, false);
vector<int> common;
for (int book : shelfA) {
for (int spotB = 0; spotB < sizeB; spotB++) {
if (!taken[spotB] && shelfB[spotB] == book) {
taken[spotB] = true;
common.push_back(book);
break;
}
}
}
return common;
}
int main() {
vector<int> shelfA = {1, 2, 2, 4};
vector<int> shelfB = {2, 4, 4, 5};
vector<int> common = intersectBrute(shelfA, shelfB);
cout << "Intersection: [";
for (int spot = 0; spot < (int)common.size(); spot++) {
if (spot > 0) {
cout << ", ";
}
cout << common[spot];
}
cout << "]" << endl;
return 0;
}def intersect_brute(shelf_a, shelf_b):
taken = [False] * len(shelf_b)
common = []
for book in shelf_a:
for spot_b in range(len(shelf_b)):
if not taken[spot_b] and shelf_b[spot_b] == book:
taken[spot_b] = True
common.append(book)
break
return common
shelf_a = [1, 2, 2, 4]
shelf_b = [2, 4, 4, 5]
common = intersect_brute(shelf_a, shelf_b)
print("Intersection: " + str(common))function intersectBrute(shelfA, shelfB) {
const sizeB = shelfB.length;
const taken = new Array(sizeB).fill(false);
const common = [];
for (const book of shelfA) {
for (let spotB = 0; spotB < sizeB; spotB++) {
if (!taken[spotB] && shelfB[spotB] === book) {
taken[spotB] = true;
common.push(book);
break;
}
}
}
return common;
}
const shelfA = [1, 2, 2, 4];
const shelfB = [2, 4, 4, 5];
const common = intersectBrute(shelfA, shelfB);
console.log("Intersection: [" + common.join(", ") + "]");Optimal: Two Pointers
Optimal 1: Two Pointers (both sorted, LeetCode follow-up 1)
Derive it under stress
- Is there an order I can use? Yes, both arrays are sorted.
- Where can the answer hide? Look at the fronts. Everything behind a front is even bigger.
- 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 fromspotBonwards is at leastshelfB[spotB], so it is bigger thanshelfA[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.
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);
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> intersectSorted(vector<int>& shelfA, vector<int>& shelfB) {
vector<int> common;
int sizeA = (int)shelfA.size();
int sizeB = (int)shelfB.size();
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.push_back(shelfA[spotA]);
spotA++;
spotB++;
}
}
return common;
}
int main() {
vector<int> shelfA = {1, 2, 2, 4};
vector<int> shelfB = {2, 4, 4, 5};
vector<int> common = intersectSorted(shelfA, shelfB);
cout << "Intersection: [";
for (int spot = 0; spot < (int)common.size(); spot++) {
if (spot > 0) {
cout << ", ";
}
cout << common[spot];
}
cout << "]" << endl;
return 0;
}def intersect_sorted(shelf_a, shelf_b):
common = []
spot_a = 0
spot_b = 0
while spot_a < len(shelf_a) and spot_b < len(shelf_b):
if shelf_a[spot_a] < shelf_b[spot_b]:
spot_a += 1
elif shelf_a[spot_a] > shelf_b[spot_b]:
spot_b += 1
else:
common.append(shelf_a[spot_a])
spot_a += 1
spot_b += 1
return common
shelf_a = [1, 2, 2, 4]
shelf_b = [2, 4, 4, 5]
common = intersect_sorted(shelf_a, shelf_b)
print("Intersection: " + str(common))function intersectSorted(shelfA, shelfB) {
const common = [];
let spotA = 0;
let spotB = 0;
while (spotA < shelfA.length && spotB < shelfB.length) {
if (shelfA[spotA] < shelfB[spotB]) {
spotA++;
} else if (shelfA[spotA] > shelfB[spotB]) {
spotB++;
} else {
common.push(shelfA[spotA]);
spotA++;
spotB++;
}
}
return common;
}
const shelfA = [1, 2, 2, 4];
const shelfB = [2, 4, 4, 5];
const common = intersectSorted(shelfA, shelfB);
console.log("Intersection: [" + common.join(", ") + "]");Optimal: Binary Search
Optimal 2: Binary Search (sorted, one array much smaller, LeetCode follow-up 2)
Derive it under stress
- Which part costs the most? Walking the huge shelf, book by book.
- What do I need for each small book? Only one answer: is it on the big shelf, and where?
- 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
fromSpotis smaller, or already paired.shelfAis sorted too, so later books never need it. lowerBoundfinds the FIRST unused copy, so each copy inshelfBis 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:
spotBwalks 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 fromfromSpot. 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).
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);
}
}#include <bits/stdc++.h>
using namespace std;
int lowerBound(vector<int>& shelf, int value, int fromSpot) {
int low = fromSpot;
int high = (int)shelf.size();
while (low < high) {
int middle = low + (high - low) / 2;
if (shelf[middle] < value) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
vector<int> intersectBinary(vector<int>& shelfA, vector<int>& shelfB) {
vector<int> common;
int sizeB = (int)shelfB.size();
int fromSpot = 0;
for (int book : shelfA) {
int found = lowerBound(shelfB, book, fromSpot);
if (found < sizeB && shelfB[found] == book) {
common.push_back(book);
fromSpot = found + 1;
}
}
return common;
}
int main() {
vector<int> shelfA = {1, 2, 2, 4};
vector<int> shelfB = {2, 4, 4, 5};
vector<int> common = intersectBinary(shelfA, shelfB);
cout << "Intersection: [";
for (int spot = 0; spot < (int)common.size(); spot++) {
if (spot > 0) {
cout << ", ";
}
cout << common[spot];
}
cout << "]" << endl;
return 0;
}def lower_bound(shelf, value, from_spot):
low = from_spot
high = len(shelf)
while low < high:
middle = low + (high - low) // 2
if shelf[middle] < value:
low = middle + 1
else:
high = middle
return low
def intersect_binary(shelf_a, shelf_b):
common = []
from_spot = 0
for book in shelf_a:
found = lower_bound(shelf_b, book, from_spot)
if found < len(shelf_b) and shelf_b[found] == book:
common.append(book)
from_spot = found + 1
return common
shelf_a = [1, 2, 2, 4]
shelf_b = [2, 4, 4, 5]
common = intersect_binary(shelf_a, shelf_b)
print("Intersection: " + str(common))function lowerBound(shelf, value, fromSpot) {
let low = fromSpot;
let high = shelf.length;
while (low < high) {
const middle = low + Math.floor((high - low) / 2);
if (shelf[middle] < value) {
low = middle + 1;
} else {
high = middle;
}
}
return low;
}
function intersectBinary(shelfA, shelfB) {
const common = [];
let fromSpot = 0;
for (const book of shelfA) {
const found = lowerBound(shelfB, book, fromSpot);
if (found < shelfB.length && shelfB[found] === book) {
common.push(book);
fromSpot = found + 1;
}
}
return common;
}
const shelfA = [1, 2, 2, 4];
const shelfB = [2, 4, 4, 5];
const common = intersectBinary(shelfA, shelfB);
console.log("Intersection: [" + common.join(", ") + "]");Optimal: Hash Map Counts
Optimal 3: Hash Map Counts (any order)
Derive it under stress
- Is there an order? No, so Two Pointers and Binary Search are out.
- What must I remember about A while I walk B? How many copies of each value are still unused.
- 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.
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);
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> intersectCounts(vector<int>& shelfA, vector<int>& shelfB) {
vector<int> smallShelf;
vector<int> bigShelf;
if (shelfA.size() <= shelfB.size()) {
smallShelf = shelfA;
bigShelf = shelfB;
} else {
smallShelf = shelfB;
bigShelf = shelfA;
}
unordered_map<int, int> counts;
for (int book : smallShelf) {
counts[book]++;
}
vector<int> common;
for (int book : bigShelf) {
if (counts[book] > 0) {
common.push_back(book);
counts[book]--;
}
}
return common;
}
vector<int> intersectSmallValues(vector<int>& shelfA, vector<int>& shelfB) {
vector<int> counts(1001, 0);
for (int book : shelfA) {
counts[book]++;
}
vector<int> common;
for (int book : shelfB) {
if (counts[book] > 0) {
common.push_back(book);
counts[book]--;
}
}
return common;
}
void printShelf(vector<int>& common) {
cout << "Intersection: [";
for (int spot = 0; spot < (int)common.size(); spot++) {
if (spot > 0) {
cout << ", ";
}
cout << common[spot];
}
cout << "]" << endl;
}
int main() {
vector<int> shelfA = {1, 2, 2, 4};
vector<int> shelfB = {2, 4, 4, 5};
vector<int> common = intersectCounts(shelfA, shelfB);
printShelf(common);
vector<int> commonSmall = intersectSmallValues(shelfA, shelfB);
printShelf(commonSmall);
return 0;
}from collections import Counter
def intersect_counts(shelf_a, shelf_b):
if len(shelf_a) <= len(shelf_b):
small_shelf = shelf_a
big_shelf = shelf_b
else:
small_shelf = shelf_b
big_shelf = shelf_a
counts = Counter()
for book in small_shelf:
counts[book] += 1
common = []
for book in big_shelf:
if counts[book] > 0:
common.append(book)
counts[book] -= 1
return common
def intersect_small_values(shelf_a, shelf_b):
counts = [0] * 1001
for book in shelf_a:
counts[book] += 1
common = []
for book in shelf_b:
if counts[book] > 0:
common.append(book)
counts[book] -= 1
return common
shelf_a = [1, 2, 2, 4]
shelf_b = [2, 4, 4, 5]
common = intersect_counts(shelf_a, shelf_b)
print("Intersection: " + str(common))
common_small = intersect_small_values(shelf_a, shelf_b)
print("Intersection: " + str(common_small))function intersectCounts(shelfA, shelfB) {
let smallShelf;
let bigShelf;
if (shelfA.length <= shelfB.length) {
smallShelf = shelfA;
bigShelf = shelfB;
} else {
smallShelf = shelfB;
bigShelf = shelfA;
}
const counts = {};
for (const book of smallShelf) {
counts[book] = (counts[book] || 0) + 1;
}
const common = [];
for (const book of bigShelf) {
if (counts[book] > 0) {
common.push(book);
counts[book] -= 1;
}
}
return common;
}
function intersectSmallValues(shelfA, shelfB) {
const counts = new Array(1001).fill(0);
for (const book of shelfA) {
counts[book] += 1;
}
const common = [];
for (const book of shelfB) {
if (counts[book] > 0) {
common.push(book);
counts[book] -= 1;
}
}
return common;
}
const shelfA = [1, 2, 2, 4];
const shelfB = [2, 4, 4, 5];
const common = intersectCounts(shelfA, shelfB);
console.log("Intersection: [" + common.join(", ") + "]");
const commonSmall = intersectSmallValues(shelfA, shelfB);
console.log("Intersection: [" + commonSmall.join(", ") + "]");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.
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);
}
}#include <bits/stdc++.h>
using namespace std;
vector<int> intersectOnDisk(vector<int>& smallShelf, vector<vector<int>>& bigShelfChunks) {
unordered_map<int, int> counts;
for (int book : smallShelf) {
counts[book]++;
}
vector<int> common;
for (vector<int>& chunk : bigShelfChunks) {
for (int book : chunk) {
if (counts[book] > 0) {
common.push_back(book);
counts[book]--;
}
}
}
return common;
}
int main() {
vector<int> smallShelf = {4, 2, 1, 2};
vector<vector<int>> bigShelfChunks = {{5, 2}, {4, 4}};
vector<int> common = intersectOnDisk(smallShelf, bigShelfChunks);
cout << "Intersection: [";
for (int spot = 0; spot < (int)common.size(); spot++) {
if (spot > 0) {
cout << ", ";
}
cout << common[spot];
}
cout << "]" << endl;
return 0;
}from collections import Counter
def intersect_on_disk(small_shelf, big_shelf_chunks):
counts = Counter()
for book in small_shelf:
counts[book] += 1
common = []
for chunk in big_shelf_chunks:
for book in chunk:
if counts[book] > 0:
common.append(book)
counts[book] -= 1
return common
small_shelf = [4, 2, 1, 2]
big_shelf_chunks = [[5, 2], [4, 4]]
common = intersect_on_disk(small_shelf, big_shelf_chunks)
print("Intersection: " + str(common))function intersectOnDisk(smallShelf, bigShelfChunks) {
const counts = {};
for (const book of smallShelf) {
counts[book] = (counts[book] || 0) + 1;
}
const common = [];
for (const chunk of bigShelfChunks) {
for (const book of chunk) {
if (counts[book] > 0) {
common.push(book);
counts[book] -= 1;
}
}
}
return common;
}
const smallShelf = [4, 2, 1, 2];
const bigShelfChunks = [[5, 2], [4, 4]];
const common = intersectOnDisk(smallShelf, bigShelfChunks);
console.log("Intersection: [" + common.join(", ") + "]");