-
Notifications
You must be signed in to change notification settings - Fork 0
/
IntersectArray.js
110 lines (81 loc) · 2.58 KB
/
IntersectArray.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Union Sorted Arrays
// Efficiently combine two already-sorted multiset arrays
// into a new sorted array containing the multiset union.
// Unions by default will take the set of dupes
// that has the highest occurences from one array.
// Input: [1,2,2,2,7], [2,2,6,6,7]
// Output: [1, 6]
// arrays could be different sizes
// all positive integers
// could be empty
// https://prod.liveshare.vsengsaas.visualstudio.com/join?CB04E68C2F05CF5355590769EA2420480100
// share this if a group member drops or connects late
// arr1 = [1,2,2,2,7]
// 5
// arr2 = [2,2,6,6,7] x
// 5
// result = [2, 7];
// function intersection(array[19]){}
// {}
function intersectSortedArrays(arr1, arr2) {
let idx1 = 0;
let idx2 = 0;
const len1 = arr1.length;
const len2 = arr2.length;
const result = [];
while (idx1 < len1 && idx2 < len2) {
if (arr1[idx1] < arr2[idx2]) {
result.push(arr1[idx1]);
idx1++;
} else if (arr1[idx1] > arr2[idx2]) {
result.push(arr2[idx2]);
idx2++;
}
// current num from both arrays are equal
else {
if (result[result.length - 1] !== arr1[idx1]) {
result.push(arr1[idx1]);
}
idx1++;
idx2++;
}
}
return result;
}
arr1 = [1,2,2,2,7]
arr2 = [2,2,6,6,7]
// === GLOSSARY ===
// collection: grouped data. arrays, lists, sets, multisets
// set: a collection with no duplicates, does not track count of values
// multiset: a collection that allows duplicates, tracks count of values
// intersection: all the values that exist across multiple collections, deduped
// union multiset: the higher count of duped values are kept. if there are 3 number ones
// in one set and 2 number ones in the other set, 3 number ones would be kept
function unionSortedArrs(arr1, arr2) {
const res = [];
let idx1 = 0;
let idx2 = 0;
while (idx1 < arr1.length || idx2 < arr2.length) {
if (idx1 === arr1.length) {
res.push(arr2[idx2]);
idx2++;
continue;
} else if (idx2 === arr2.length) {
res.push(arr1[idx1]);
idx1++;
continue;
}
if (arr1[idx1] === arr2[idx2]) {
res.push(arr1[idx1]);
idx1++;
idx2++; // since both were same, increment both
} else if (arr1[idx1] < arr2[idx2]) {
res.push(arr1[idx1]);
idx1++;
} else {
res.push(arr2[idx2]);
idx2++;
}
}
return res;
}