SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 9
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 9 of 30

Array questions V

merge two sorted arraysintersection and unionmaximum subarray sum (Kadane, all-negative case)

These are the notes for JavaScript Coding Questions, episode 9, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three questions: merge two sorted arrays into one sorted array, the intersection and union of two arrays, and the maximum subarray sum with Kadane's algorithm, including the case where every number is negative.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Plain modern JavaScript, no packages.

About the timings. Lines like intersection: 1.640s are copied from a real run on one machine; your numbers will differ. What matters is the size of the gap.

Q1: Merge two sorted arrays

Problem. a and b are each sorted in ascending order (smallest first). Return one array with every item of both, also sorted.

[1, 4, 9] + [2, 3, 10]   → [1, 2, 3, 4, 9, 10]
[1, 3] + [2, 4, 5, 6]    → [1, 2, 3, 4, 5, 6]
[] + [7, 8]              → [7, 8]

Real life: two sections of a class each have a sorted list of marks, and the school wants one merit list.

Think out loud

  • The inputs are already sorted: that is the clue the question gives you.
  • Edge cases: different lengths, an empty array, equal values on both sides.

The obvious attempt: glue and sort

function merge(a, b) {
  return [...a, ...b].sort();
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([5, 20], [8, 100]));
[ 1, 10, 2, 3, 4, 9 ]
[ 100, 20, 5, 8 ]

Episode 8's trap: with no compare function, sort compares items as strings, so "10" comes before "2". With a compare function it is correct:

function merge(a, b) {
  return [...a, ...b].sort((x, y) => x - y);
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([5, 20], [8, 100]));
[ 1, 2, 3, 4, 9, 10 ]
[ 5, 8, 20, 100 ]

Correct, but it ignores that both inputs were sorted and sorts everything again: O((n + m) log(n + m)). An interviewer wants one pass.

Two pointers: two queues, one counter

Picture a bank with two queues, each already in token order, and one counter that must serve everyone in token order. You only look at the front of each queue: call the smaller token, and that queue moves up.

The first version many people write:

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);
    else out.push(b[j++]);
  }
  return out;
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([1, 3], [2, 4, 5, 6]));
console.log(merge([], [7, 8]));
[ 1, 2, 3, 4, 9 ]
[ 1, 2, 3 ]
[]

Items went missing, with no error: 10, then 4, 5, 6, then everything. The loop stops as soon as one array runs out; the rest of the other array is never copied. Fix: copy the leftovers.

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) out.push(a[i++]);
    else out.push(b[j++]);
  }
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([1, 3], [2, 4, 5, 6]));
console.log(merge([], [7, 8]));
console.log(merge([2, 2], [2]), merge([], []));
[ 1, 2, 3, 4, 9, 10 ]
[ 1, 2, 3, 4, 5, 6 ]
[ 7, 8 ]
[ 2, 2, 2 ] []
  • a[i++] uses the old value of i, then adds 1 (postfix increment).
  • Only one of the two leftover loops actually runs.
  • <= takes the item from a first when values are equal, so the merge is stable (equal items keep their order). This exact step is the heart of merge sort (episode 25).

Complexity: every item is pushed once: O(n + m) time, O(n + m) space for the output.

Q2: Intersection and union

Problem. The intersection is the values that appear in both arrays; the union is every value that appears in either. Each value once.

[1, 2, 2, 1] ∩ [2, 2]   → [2]
[1, 2, 2, 1] ∪ [2, 3]   → [1, 2, 3]

Real life: students in both the chess club and the coding club (intersection), and students in at least one of them (union).

Think out loud

  • "Each value once": duplicates must go.
  • Edge cases: duplicates, an empty array, 50,000 items on each side.

The obvious attempt: filter + includes

function intersection(a, b) {
  return a.filter(x => b.includes(x));
}
function union(a, b) {
  return [...a, ...b];
}
console.log(intersection([1, 2, 2, 1], [2, 2]));
console.log(union([1, 2, 2, 1], [2, 3]));
[ 2, 2 ]
[ 1, 2, 2, 1, 2, 3 ]

Duplicates everywhere: filter keeps every matching item of a (and a has 2 twice), and spread just glues the arrays. Now the size test:

function intersection(a, b) {
  return a.filter(x => b.includes(x));
}
const a = Array.from({ length: 50000 }, (_, i) => i * 2);
const b = Array.from({ length: 50000 }, (_, i) => i * 3);
console.time("intersection");
console.log(intersection(a, b).length);
console.timeEnd("intersection");
16667
intersection: 1.640s

includes scans b from the start for every item of a: up to 50,000 × 50,000 comparisons. O(n · m).

A Set: the guest list at the door

Reading the whole printed guest list for every guest is slow; a guard who knows every name answers in one glance. A Set answers has in O(1) on average, and holds each value once.

function intersection(a, b) {
  const inB = new Set(b);
  return [...new Set(a)].filter(x => inB.has(x));
}
function union(a, b) {
  return [...new Set([...a, ...b])];
}
console.log(intersection([1, 2, 2, 1], [2, 2]));
console.log(union([1, 2, 2, 1], [2, 3]));
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4]), intersection([1], []));
const a = Array.from({ length: 50000 }, (_, i) => i * 2);
const b = Array.from({ length: 50000 }, (_, i) => i * 3);
console.time("intersection");
console.log(intersection(a, b).length);
console.timeEnd("intersection");
[ 2 ]
[ 1, 2, 3 ]
[ 4, 9 ] []
16667
intersection: 11.126ms

From 1.6 seconds to about 11 milliseconds. A Set remembers insertion order, so the results keep the order of a.

Complexity: O(n + m) time, O(n + m) space.

Built-in Set methods (Node 22+)

const a = new Set([1, 2, 2, 1]);
const b = new Set([2, 3]);
console.log(a.intersection(b));
console.log(a.union(b));
console.log([...a.union(b)]);
Set(1) { 2 }
Set(3) { 1, 2, 3 }
[ 1, 2, 3 ]

They return Sets; spread to get an array. There are also difference, symmetricDifference, isSubsetOf, isSupersetOf and isDisjointFrom. In an interview, write the filter version first to show the idea, then mention the built-ins.

Q3: Maximum subarray sum (Kadane's algorithm)

Problem. A subarray is a run of items next to each other, with at least one item. Return the largest sum any subarray has.

[-2, 1, -3, 4, -1, 2, 1, -5, 4]  → 6    (4, -1, 2, 1)
[5, 4, -1, 7, 8]                 → 23   (the whole array)
[-3, -1, -2]                     → -1   (just -1: at least one item!)

Real life: a tea stall writes down its profit or loss every day. What was its best run of consecutive days?

The obvious attempt: every subarray

function maxSubarray(arr) {
  let best = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    let sum = 0;
    for (let j = i; j < arr.length; j++) {
      sum += arr[j];
      best = Math.max(best, sum);
    }
  }
  return best;
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
6
23
-1
124
max: 397.57ms

Correct, because best starts at -Infinity (any real sum beats it). But 30,000 starts, each extended to the end, is about 450 million additions: O(n²). Double the input, four times the time.

Kadane: should I keep the streak?

Walk once, carrying cur: the best total of a streak that ends today. Each day: if the streak you carry is negative, it can only drag today down, so drop it and start fresh today. Add today's value. If cur is the best ever, remember it.

The short version seen in many tutorials, with a bug:

function maxSubarray(arr) {
  let best = 0, cur = 0;
  for (const x of arr) {
    cur = Math.max(x, cur + x);
    best = Math.max(best, cur);
  }
  return best;
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
6
23
0
124
max: 2.007ms

Fast, but [-3, -1, -2] gives 0. best started at 0 and no real sum beat it. 0 is the sum of the empty subarray, which the question does not allow. Fix: start best at arr[0]. This version also records where the best run starts and ends:

function maxSubarray(arr) {
  let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
  for (let i = 0; i < arr.length; i++) {
    if (cur < 0) { cur = 0; start = i; }
    cur += arr[i];
    if (cur > best) { best = cur; from = start; to = i; }
  }
  return { best, from, to };
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
console.log(maxSubarray([7]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
{ best: 6, from: 3, to: 6 }
{ best: 23, from: 0, to: 4 }
{ best: -1, from: 1, to: 1 }
{ best: 7, from: 0, to: 0 }
{ best: 124, from: 15, to: 62 }
max: 0.718ms

Trace of [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

i arr[i] cur before dropped? cur after best
0 -2 0 no -2 -2
1 1 -2 yes, start = 1 1 1
2 -3 1 no -2 1
3 4 -2 yes, start = 3 4 4
4 -1 4 no 3 4
5 2 3 no 5 5
6 1 5 no 6 6 (from 3 to 6)
7 -5 6 no 1 6
8 4 1 no 5 6

Complexity: one pass, a few variables: O(n) time, O(1) space.

Complexity summary

Question Approach Time Extra space
Merge sorted concat + sort O((n + m) log(n + m)) O(n + m)
Merge sorted two pointers + leftovers O(n + m) O(n + m) output
Intersection filter + includes O(n · m) O(n)
Intersection / union Set O(n + m) O(n + m)
Intersection of sorted arrays two pointers O(n + m) O(1) besides output
Max subarray every subarray O(n²) O(1)
Max subarray Kadane O(n) O(1)

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
Default sort on merged numbers [...a, ...b].sort() [ 1, 10, 2, 3, 4, 9 ] compared as strings two pointers (or (x, y) => x - y)
Forgetting the leftovers while (i < a.length && j < b.length) only [ 1, 2, 3 ] for [1, 3] + [2, 4, 5, 6] the loop stops at the shorter side copy what's left
filter + includes a.filter(x => b.includes(x)) [ 2, 2 ], intersection: 1.640s duplicates kept; O(n · m) new Set(b) then has
Spread for union [...a, ...b] [ 1, 2, 2, 1, 2, 3 ] nothing removes duplicates [...new Set([...a, ...b])]
Comparing with the wrong type in a Set new Set([5, 1, 4]).has("4") false "4" and 4 are different values convert first: Number(x)
Kadane with best = 0 let best = 0 0 for [-3, -1, -2] 0 is the empty subarray best = arr[0]

Mini project: the tea stall's best run

Two weeks of daily profit and loss; find the best run of days and print it.

// A tea stall's daily profit (+) and loss (-) in rupees for two weeks.
const days = [120, -300, 80, 150, -40, 210, -90, -250, 60, 90, 130, -20, 70, -400];
function bestStreak(arr) {
  let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
  for (let i = 0; i < arr.length; i++) {
    if (cur < 0) { cur = 0; start = i; }
    cur += arr[i];
    if (cur > best) { best = cur; from = start; to = i; }
  }
  return { best, from, to };
}
const { best, from, to } = bestStreak(days);
console.log(`Best run: day ${from + 1} to day ${to + 1}, profit ₹${best}`);
console.log(days.slice(from, to + 1).join(" + "), "=", best);
Best run: day 3 to day 6, profit ₹400
80 + 150 + -40 + 210 = 400

Extend it: also find the worst run (flip the signs, or track the minimum), or read the numbers from stdin (episode 14 of the JavaScript course).

Your turn: intersection of two SORTED arrays (solution)

Problem. Both arrays are sorted. Return the common values, each once, without a Set (O(1) extra space besides the output). [1, 2, 2, 4, 7] and [2, 2, 3, 7, 9] → [2, 7].

Solution

Walk both with two pointers, like the merge. If the fronts differ, the smaller one can't be in the other array any more (everything after it there is bigger), so move that pointer. If they are equal, it's common: push it once and move both.

function intersectSorted(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else {
      if (out.at(-1) !== a[i]) out.push(a[i]);
      i++;
      j++;
    }
  }
  return out;
}
console.log(intersectSorted([1, 2, 2, 4, 7], [2, 2, 3, 7, 9]));
console.log(intersectSorted([1, 1, 1], [1, 1]), intersectSorted([1, 3], [2, 4]), intersectSorted([], [1]));
[ 2, 7 ]
[ 1 ] [] []

out.at(-1) is the last item pushed; because the input is sorted, a repeat can only be equal to the last one. O(n + m) time, O(1) extra space. Here the leftovers can be ignored: once one side runs out, nothing else can be common.

Practice questions (with solutions)

1. Difference: the values in a but not in b, each once.

Solution
function difference(a, b) {
  const inB = new Set(b);
  return [...new Set(a)].filter(x => !inB.has(x));
}
console.log(difference([1, 2, 3, 4, 2], [2, 4]), difference([1], [1]));
console.log(new Set([1, 2, 3, 4]).difference(new Set([2, 4])));
[ 1, 3 ] []
Set(2) { 1, 3 }

2. Merge three sorted arrays.

Solution

Merge two, then merge the result with the third.

function merge(a, b) {
  const out = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}
const mergeThree = (a, b, c) => merge(merge(a, b), c);
console.log(mergeThree([1, 7], [2, 3, 9], [0, 8]));
console.log(mergeThree([], [5], []));
[
  0, 1, 2, 3,
  7, 8, 9
]
[ 5 ]

(Node prints arrays of more than 6 numbers over several lines.) For k arrays, merging them in pairs, like a tournament, keeps the total work at O(N log k), where N is the total number of items.

3. Maximum subarray, returning the subarray itself.

Solution
function maxSubarrayItems(arr) {
  let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
  for (let i = 0; i < arr.length; i++) {
    if (cur < 0) { cur = 0; start = i; }
    cur += arr[i];
    if (cur > best) { best = cur; from = start; to = i; }
  }
  return arr.slice(from, to + 1);
}
console.log(maxSubarrayItems([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarrayItems([-3, -1, -2]), maxSubarrayItems([2, -1, 2]));
[ 4, -1, 2, 1 ]
[ -1 ] [ 2, -1, 2 ]

4. Merge in place (a common interview version): nums1 has length m + n, its first m items are sorted and the rest are 0 placeholders; merge nums2 (n sorted items) into it.

Solution

Fill from the back, so nothing that is still needed gets overwritten.

function mergeInPlace(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, w = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) nums1[w--] = nums1[i--];
    else nums1[w--] = nums2[j--];
  }
  return nums1;
}
console.log(mergeInPlace([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3));
console.log(mergeInPlace([0], 0, [1], 1), mergeInPlace([4, 5, 0, 0], 2, [1, 2], 2));
[ 1, 2, 2, 3, 5, 6 ]
[ 1 ] [ 1, 2, 4, 5 ]

The loop only needs to run while nums2 has items: leftovers of nums1 are already in place. O(m + n) time, O(1) space.

Quick quiz

1. (From the video.) What does this print?

const s = new Set([3, 1, 3, 2, 1]);
console.log([...s]);

(A) [ 1, 2, 3 ] (B) [ 3, 1, 2 ] (C) [ 3, 1, 3, 2, 1 ] (D) [ 3, 2, 1 ]

Answer

(B) [ 3, 1, 2 ]. A Set drops duplicates and keeps the order values were first added. It does not sort.

2. What do these print?

console.log([...new Set([1, 2]).union(new Set([2, 3]))].length);
const best = [-5, -2, -8].reduce((b, x) => Math.max(b, x), 0);
console.log(best);
Answer
3
0

The union is {1, 2, 3}. And the same trap as Kadane with best = 0: starting the maximum at 0 hides that every number is negative. Use Math.max(...arr) for small arrays, or start from arr[0].

3. What does this print?

console.log([5, 1, 4].includes(4), new Set([5, 1, 4]).has("4"));
Answer
true false

Sets compare values with the same rule as === (except that NaN equals NaN), so the string "4" is not the number 4.

Interview questions

  1. Merge two sorted arrays in O(n + m). Two pointers, push the smaller front item, then copy the leftovers.
  2. What bug do people make in the merge? Stopping when one array runs out and losing the rest of the other.
  3. Why is <= better than < in the merge? Equal items come from the first array first: a stable merge, which merge sort relies on.
  4. Intersection of two arrays in O(n + m)? Put one in a Set, filter the unique values of the other with has.
  5. Why is filter + includes slow? includes is a linear scan, so the whole thing is O(n · m).
  6. Intersection of two sorted arrays with O(1) extra space? Two pointers; move the smaller front.
  7. Does a Set keep order? Yes, insertion order. It does not sort.
  8. Explain Kadane's algorithm. Carry the best sum ending here; if it becomes negative, drop it and start fresh; track the best seen. O(n), O(1).
  9. What happens if every number is negative? The answer is the largest (least negative) single item; starting best at 0 wrongly returns 0.
  10. How do you also return the subarray? Remember the start index when you restart, and save from and to whenever best improves.

Glossary

Term Meaning Example
Sorted ascending Smallest first [1, 4, 9]
Merge Combine two sorted arrays into one sorted array [1, 4] + [2] → [1, 2, 4]
Two pointers Two indexes that move through the data i in a, j in b
Leftovers Items still waiting in one array after the other runs out 10 in [2, 3, 10]
Postfix increment (i++) Uses the old value, then adds 1 out.push(a[i++])
Stable Equal items keep their original order <= in the merge
Merge sort A sort that splits the array and merges sorted halves episode 25
Spread (...) Expands an array (or Set) into items [...a, ...b]
Intersection Values in both collections [1, 2] ∩ [2, 3] → [2]
Union Values in either collection, each once [1, 2] ∪ [2, 3] → [1, 2, 3]
Difference Values in the first but not the second [1, 2] − [2] → [1]
includes Linear scan: is x in the array? O(n) b.includes(x)
Set A collection of unique values, in insertion order new Set([1, 1, 2]) → {1, 2}
set.has(x) Is x in the Set? O(1) on average inB.has(2)
O(n · m) Work grows with the product of two sizes filter + includes
Subarray Items next to each other, at least one [4, -1, 2, 1]
Maximum subarray sum The largest sum of any subarray 6
Kadane's algorithm One-pass maximum subarray: drop a negative running sum if (cur < 0) cur = 0
Running sum A total updated as you walk cur += arr[i]
Empty subarray A subarray with no items; its sum is 0 (not allowed here) why best = 0 is wrong
-Infinity A number smaller than every other number let best = -Infinity
Array.prototype.at Item by index, negative counts from the end out.at(-1)
slice(from, to) A copy of the items from from up to (not including) to arr.slice(3, 7)

Summary

  • Merge sorted arrays: use the clue that they are sorted. Two pointers, push the smaller front, then copy the leftovers. O(n + m). Concatenating and sorting is slower, and without a compare function it sorts numbers as strings.
  • Intersection and union: filter + includes keeps duplicates and is O(n · m). A Set gives unique values and O(1) has: intersection = unique a filtered by inB.has, union = new Set([...a, ...b]). Node 22+ has intersection, union and difference built in.
  • Maximum subarray (Kadane): carry the best sum ending here, drop it when it goes negative, track the best. O(n), O(1). Start best at arr[0], never 0, or an all-negative array returns 0.

Next episode: Array questions VI: flattening a nested array (recursion vs flat(Infinity)), splitting an array into chunks, and grouping items by a key with Object.groupBy.