SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 7
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 7 of 30

Array questions III

find the missing number 1..n (sum and XOR)frequency of each element with a Mapmajority element (Boyer-Moore voting)

These are the notes for JavaScript Coding Questions, episode 7, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three array questions: find the missing number in 1 to n, count how often each value appears, and find the majority element. We meet an off-by-one bug, a word counter that breaks on the word constructor, and the Boyer-Moore voting trick that finds a majority with O(1) extra memory.

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 includes: 705.119ms are copied from a real run on one machine; what matters is the size of the gap.

Q1: Find the missing number

Problem. The array holds the numbers 1 to n in any order with exactly one missing. Return it. [3, 1, 4, 5] → 2.

Real life. A teacher's roll call: the class has n students, one is absent.

Think out loud

  • The array length is n - 1, so n = arr.length + 1.
  • Edge cases: 1 is missing, n itself is missing, the empty array (n = 1, so 1 is missing), 100,000 numbers.

The obvious attempt: includes for every i

function missing(arr) {
  const n = arr.length;
  for (let i = 1; i <= n; i++) {
    if (!arr.includes(i)) return i;
  }
}
console.log(missing([3, 1, 4, 5]), missing([2, 3, 4, 5]), missing([1, 2, 3, 4]));
const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
console.time("includes");
console.log(missing(big));
console.timeEnd("includes");

Output:

2 1 undefined
41001
includes: 705.119ms

The big test array is 1 to 100,000 without 41001: Array.from builds i + 1 for the first 41,000 indexes and i + 2 after that.

Two bugs.

  1. Off-by-one. n is the length plus one. With n = arr.length, the loop never checks n, so [1, 2, 3, 4] (missing 5) falls off the end and returns undefined. An off-by-one error is a loop or index that is one too big or too small.
  2. O(n²). includes scans the array from the start each time: n checks × up to n steps.

The sum trick

Real-life picture. Roll numbers 1 to 5 should add up to 1 + 2 + 3 + 4 + 5 = 15. The students present (3, 1, 4, 5) add up to 13. 15 - 13 = 2: roll number 2 is absent.

The sum 1 + 2 + ... + n is n(n + 1) / 2 (pair the first and last: 1 + n, 2 + (n - 1), ...: n/2 pairs of n + 1).

The XOR trick

From episode 4: x ^ x = 0 and x ^ 0 = x, and the order doesn't matter. XOR every number from 1 to n and every number in the array: each present number appears twice and cancels; only the missing one is left.

function missing(arr) {
  const n = arr.length + 1;
  let sum = 0;
  for (const x of arr) sum += x;
  return (n * (n + 1)) / 2 - sum;
}
function missingXor(arr) {
  const n = arr.length + 1;
  let x = 0;
  for (let i = 1; i <= n; i++) x ^= i;
  for (const v of arr) x ^= v;
  return x;
}
console.log(missing([3, 1, 4, 5]), missing([2, 3, 4, 5]), missing([1, 2, 3, 4]), missing([]));
console.log(missingXor([3, 1, 4, 5]), missingXor([2, 3, 4, 5]), missingXor([1, 2, 3, 4]));
const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
console.time("sum");
console.log(missing(big), missingXor(big));
console.timeEnd("sum");

Output:

2 1 5 1
2 1 5
41001 41001
sum: 10.328ms

Both are O(n) time, O(1) space. Why mention XOR? n * (n + 1) grows like n², and past 2⁵³ a Number is no longer exact (episode 3). XOR results never exceed the size of the numbers themselves (for values that fit in 32 bits, since ^ works on 32 bits).

A Set also works in O(n) time, but needs O(n) space:

const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
const s = new Set(big);
console.time("Set lookup");
let missingNo = null;
for (let i = 1; i <= big.length + 1; i++) if (!s.has(i)) { missingNo = i; break; }
console.timeEnd("Set lookup");
console.log(missingNo);
Set lookup: 2.126ms
41001

Q2: Count how often each value appears

Problem. Return the frequency of every value, in the order values first appear. [3, 1, 3, 2, 3] → 3: 3, 1: 1, 2: 1.

Real life. Counting votes, or the words in customer reviews.

The obvious attempt: a plain object

function frequency(items) {
  const counts = {};
  for (const x of items) counts[x] = (counts[x] || 0) + 1;
  return counts;
}
console.log(frequency([3, 1, 3, 2, 3]));
console.log(frequency([1, "1", 1]));
console.log(frequency("to be or not to be".split(" ")));
console.log(frequency("the constructor of the class".split(" ")));

Output:

{ '1': 1, '2': 1, '3': 3 }
{ '1': 3 }
{ to: 2, be: 2, or: 1, not: 1 }
{
  the: 2,
  constructor: 'function Object() { [native code] }1',
  of: 1,
  class: 1
}

Three problems.

  1. Keys become strings. 1 and "1" are the same key '1', so they are merged into a count of 3.
  2. Integer-like keys are listed in ascending order, before other keys, so the order of first appearance is lost.
  3. Inherited properties. Every object inherits from Object.prototype, which has a constructor property (the Object function). counts["constructor"] already exists, || 0 keeps it, and function + 1 turns into the text 'function Object() { [native code] }1'.
const o = {};
console.log("constructor" in o, o.constructor === Object, Object.hasOwn(o, "constructor"));
const safe = Object.create(null);
safe["constructor"] = (safe["constructor"] || 0) + 1;
console.log(safe.constructor, Object.keys({ b: 1, 10: 1, 2: 1, a: 1 }));
true true false
1 [ '2', '10', 'b', 'a' ]

in sees inherited properties; Object.hasOwn sees only the object's own. Object.create(null) makes an object with no prototype, so nothing is inherited; it still turns keys into strings and reorders integer keys, which the last line shows.

The fix: a Map

Real-life picture. A printed form that comes with some rows already filled in (a plain object) vs a blank tally sheet where rows are added in arrival order (a Map). A Map is a collection of key → value pairs that starts truly empty, keeps any type of key exactly, and remembers insertion order.

function frequency(items) {
  const counts = new Map();
  for (const x of items) counts.set(x, (counts.get(x) ?? 0) + 1);
  return counts;
}
console.log(frequency([3, 1, 3, 2, 3]));
console.log(frequency([1, "1", 1]));
console.log(frequency("the constructor of the class".split(" ")));
const f = frequency("to be or not to be".split(" "));
for (const [word, count] of f) console.log(word, count);
console.log(f.get("to"), f.get("xyz"), f.size);

Output:

Map(3) { 3 => 3, 1 => 1, 2 => 1 }
Map(2) { 1 => 2, '1' => 1 }
Map(4) { 'the' => 2, 'constructor' => 1, 'of' => 1, 'class' => 1 }
to 2
be 2
or 1
not 1
2 undefined 4
  • get(key) returns the value or undefined; ?? 0 turns undefined into 0 (and, unlike ||, would keep a real 0).
  • for (const [key, value] of map) loops over entries in insertion order.
  • size is the number of keys.

Complexity: O(n) time (each get/set is O(1) on average), O(k) space for k distinct values.

Plain object {} Map
Key types strings (and symbols) only any value, kept exactly
Inherited keys yes (constructor, toString...) none
Order integer keys first, ascending insertion order
Size Object.keys(o).length m.size
Best for fixed records, JSON counting, lookups, caches

Q3: The majority element

Problem. Return the value that appears more than n / 2 times, or null if there is none. [2, 2, 1, 2, 3] → 2; [1, 2, 3] and [1, 1, 2, 2] → null. Follow-up: O(n) time and O(1) extra space (a counting Map is O(n) space).

The obvious attempt: the middle of the sorted array

A majority fills more than half the array, so after sorting it must cover the middle position.

function majority(arr) {
  const sorted = [...arr].sort((a, b) => a - b);
  return sorted[Math.floor(sorted.length / 2)];
}
console.log(majority([2, 2, 1, 2, 3]), majority([7, 7, 5, 7]));
console.log(majority([1, 2, 3]), majority([1, 1, 2, 2]));
2 7
2 2

Right when a majority exists, but wrong when it doesn't: the middle is then just some value. And sorting is O(n log n).

Boyer-Moore majority vote

Real-life picture: an election where votes cancel. The first vote makes its candidate the leader with 1 vote. A vote for the leader adds 1; a vote for anyone else cancels one of the leader's votes (one supporter and one opponent leave together). At 0 votes, the next voter's choice becomes the leader. A real majority has more votes than all the others together, so it can never be cancelled out completely.

const arr = [2, 2, 1, 2, 3];
let candidate = null, votes = 0;
for (const x of arr) {
  if (votes === 0) candidate = x;
  votes += x === candidate ? 1 : -1;
  console.log(x, "->", candidate, votes);
}
2 -> 2 1
2 -> 2 2
1 -> 2 1
2 -> 2 2
3 -> 2 1

If there is no majority, someone is still left standing, so a second pass confirms the candidate:

function majority(arr) {
  let candidate = null, votes = 0;
  for (const x of arr) {
    if (votes === 0) candidate = x;
    votes += x === candidate ? 1 : -1;
  }
  let count = 0;
  for (const x of arr) if (x === candidate) count++;
  return count > arr.length / 2 ? candidate : null;
}
for (const a of [[2, 2, 1, 2, 3], [7, 7, 5, 7], [1, 2, 3], [1, 1, 2, 2], [4], []]) {
  console.log(JSON.stringify(a), majority(a));
}
[2,2,1,2,3] 2
[7,7,5,7] 7
[1,2,3] null
[1,1,2,2] null
[4] 4
[] null

Complexity: O(n) time (two passes), O(1) space. If the problem guarantees a majority exists, the second pass can be skipped; ask the interviewer.

Complexity summary

Question Approach Time Extra space
Missing number includes for each i O(n²) O(1)
Missing number Set O(n) O(n)
Missing number sum formula / XOR O(n) O(1)
Frequency plain object O(n) O(k), but wrong keys
Frequency Map O(n) O(k)
Majority sort + middle O(n log n) O(n) copy; wrong without a majority
Majority Map of counts O(n) O(k)
Majority Boyer-Moore + confirm O(n) O(1)

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
n = length const n = arr.length missing([1, 2, 3, 4]) → undefined one number is missing arr.length + 1
Search inside a loop arr.includes(i) for each i includes: 705.119ms O(n²) sum, XOR or a Set
Counting in {} counts[x] = (counts[x] \|\| 0) + 1 constructor: 'function Object() { [native code] }1' inherited keys new Map()
Mixed key types in {} frequency([1, "1", 1]) { '1': 3 } keys become strings Map keeps types
Expecting insertion order from {} [3, 1, 3, 2, 3] { '1': 1, '2': 1, '3': 3 } integer keys sorted Map
Middle of sorted = majority sorted[n >> 1] [1, 2, 3] → 2 only valid if one exists Boyer-Moore + confirm
Skipping the confirm pass candidate only a "majority" that isn't someone always survives count again

Mini project: top words in a review

const review = `The food was good, the service was slow.
Good food, good price! The constructor of this building did a good job.`;
const words = review.toLowerCase().match(/[a-z]+/g);
const counts = new Map();
for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
const top = [...counts].sort((a, b) => b[1] - a[1]).slice(0, 3);
console.log(words.length, "words,", counts.size, "different");
for (const [word, count] of top) console.log(word.padEnd(8), "#".repeat(count), count);
21 words, 14 different
good     #### 4
the      ### 3
food     ## 2

match(/[a-z]+/g) returns every run of letters (punctuation dropped). [...counts] turns the Map into [word, count] pairs to sort by count. Because sort is stable, words with equal counts keep their first-seen order. Extend it: ignore common words like "the" and "a" with a Set of stop words.

Your turn: find the duplicate (solution)

Problem. The array has n + 1 numbers, each from 1 to n, and exactly one value appears twice. Find it. [3, 1, 3, 4, 2] → 3.

Solution

Three ways:

function duplicateSum(arr) {
  const n = arr.length - 1;
  let sum = 0;
  for (const x of arr) sum += x;
  return sum - (n * (n + 1)) / 2;
}
function duplicateSet(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return x;
    seen.add(x);
  }
  return null;
}
function duplicateFloyd(arr) {
  let slow = arr[0], fast = arr[0];
  do {
    slow = arr[slow];
    fast = arr[arr[fast]];
  } while (slow !== fast);
  slow = arr[0];
  while (slow !== fast) {
    slow = arr[slow];
    fast = arr[fast];
  }
  return slow;
}
for (const a of [[3, 1, 3, 4, 2], [1, 1], [2, 5, 4, 1, 3, 5]]) {
  console.log(JSON.stringify(a), duplicateSum(a), duplicateSet(a), duplicateFloyd(a));
}
console.log(duplicateSum([2, 2, 2, 1]), duplicateSet([2, 2, 2, 1]), duplicateFloyd([2, 2, 2, 1]));
[3,1,3,4,2] 3 3 3
[1,1] 1 1 1
[2,5,4,1,3,5] 5 5 5
1 2 2
  • Sum (turned around): the array sums to 1 + ... + n plus the duplicate, so subtract n(n + 1) / 2. O(n), O(1), but it only works if every number 1..n is present and exactly one is doubled; the last line shows it breaks when a value appears three times ([2, 2, 2, 1] gives 1).
  • Set: the first value already seen. O(n), O(n) space; works for any input.
  • Floyd's cycle detection (the LeetCode follow-up, O(1) space without changing the array): treat each value as a pointer to an index. The duplicate value is pointed to twice, which creates a cycle; a slow and a fast pointer meet inside it, and restarting one from the beginning finds the cycle's entrance. We'll meet this "tortoise and hare" idea again with linked lists in episode 26.

Practice questions (with solutions)

1. Two missing numbers in 1..n.

Solution

Use the sum and the sum of squares: a + b = S and a² + b² = Q give (a - b)² = 2Q - S².

function twoMissing(arr) {
  const n = arr.length + 2;
  let sum = (n * (n + 1)) / 2, squares = (n * (n + 1) * (2 * n + 1)) / 6;
  for (const x of arr) { sum -= x; squares -= x * x; }
  // a + b = sum, a² + b² = squares  →  a - b = √(2·squares − sum²)
  const diff = Math.sqrt(2 * squares - sum * sum);
  return [(sum - diff) / 2, (sum + diff) / 2];
}
console.log(twoMissing([1, 3, 5]), twoMissing([3, 4]), twoMissing([1, 2, 3, 4]));
[ 2, 4 ] [ 1, 2 ] [ 5, 6 ]

O(n), O(1). (For large n the squares overflow 2⁵³; a Set is the safe fallback.)

2. The most frequent element (first one to reach the top count wins ties).

Solution
function mostFrequent(arr) {
  const counts = new Map();
  let best = null, bestCount = 0;
  for (const x of arr) {
    const c = (counts.get(x) ?? 0) + 1;
    counts.set(x, c);
    if (c > bestCount) { best = x; bestCount = c; }
  }
  return arr.length ? [best, bestCount] : null;
}
console.log(mostFrequent([3, 1, 3, 2, 1, 1]), mostFrequent(["a", "b", "a"]), mostFrequent([]));
[ 1, 3 ] [ 'a', 2 ] null

One pass, O(n) time, O(k) space.

3. Every element that appears more than n / 3 times (at most two can).

Solution

Boyer-Moore with two candidates, then confirm both:

function majorityThird(arr) {
  let c1 = null, v1 = 0, c2 = null, v2 = 0;
  for (const x of arr) {
    if (x === c1) v1++;
    else if (x === c2) v2++;
    else if (v1 === 0) { c1 = x; v1 = 1; }
    else if (v2 === 0) { c2 = x; v2 = 1; }
    else { v1--; v2--; }
  }
  const result = [];
  for (const c of [c1, c2]) {
    if (c !== null && arr.filter(x => x === c).length > arr.length / 3) result.push(c);
  }
  return result;
}
for (const a of [[3, 2, 3], [1, 1, 1, 3, 3, 2, 2, 2], [1, 2, 3], [5]]) console.log(JSON.stringify(a), majorityThird(a));
[3,2,3] [ 3 ]
[1,1,1,3,3,2,2,2] [ 1, 2 ]
[1,2,3] []
[5] [ 5 ]

O(n) time, O(1) space.

Quick quiz

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

const m = new Map([[1, "a"]]);
const o = { 1: "a" };
console.log(m.get("1"), o["1"]);

(A) a a (B) undefined a (C) a undefined (D) undefined undefined

Answer

(B) undefined a. The Map's key is the number 1, so the string "1" is a different key. The object turned its key into the string "1", so o["1"] (and o[1]) find it.

2. What does console.log(5 ^ 3 ^ 5) print?

Answer

3: the two 5s cancel (x ^ x = 0), leaving 3. That's why the XOR missing-number trick works.

3. Boyer-Moore on [1, 2, 3] ends with which candidate before the confirm pass?

Answer

3 (1 is cancelled by 2, then 3 becomes the leader). The confirm pass counts one 3, not more than 1.5, so the answer is null.

Interview questions

  1. Find the missing number in 1..n. n = length + 1; n(n + 1)/2 - sum, or XOR of 1..n and the array. O(n), O(1).
  2. Why might you prefer XOR to the sum? The sum formula grows like n² and can pass 2⁵³; XOR stays small.
  3. What's wrong with includes inside a loop? It is a hidden O(n) scan, making the whole thing O(n²).
  4. Why use a Map rather than an object for counting? Keys keep their type, insertion order is kept, and there are no inherited keys like constructor.
  5. What does Object.create(null) give you? An object with no prototype: no inherited keys (but keys are still strings).
  6. Explain the Boyer-Moore majority vote. Keep a candidate and a counter; same value +1, different -1, new candidate at 0. A true majority survives. Confirm with a second pass. O(n), O(1).
  7. When can you skip the confirm pass? When the problem guarantees a majority exists.
  8. Why is sorted[n / 2] not enough? It's only the majority if one exists; for [1, 2, 3] it returns 2.
  9. How many elements can appear more than n/3 times? At most two; extend Boyer-Moore to two candidates.

Glossary

Term Meaning Example
Off-by-one error A loop or index that is one too big or too small n = arr.length instead of + 1
includes True if the array contains a value (scans: O(n)) [1, 2].includes(2)
Arithmetic series sum 1 + 2 + ... + n = n(n + 1) / 2 n = 5 → 15
XOR (^) Bitwise "differ"; x ^ x = 0, x ^ 0 = x 5 ^ 3 ^ 5 is 3
Frequency How many times a value appears 3 appears 3 times
Plain object {}: string keys, inherits from Object.prototype counts["to"]
Prototype The object another object inherits properties from Object.prototype
Inherited property A property found on the prototype, not the object itself constructor
in operator True for own and inherited properties "constructor" in {}
Object.hasOwn True only for the object's own properties Object.hasOwn({}, "constructor") is false
Object.create(null) An object with no prototype a "safe" dictionary
Map Key → value pairs; any key type, insertion order new Map()
map.get / map.set Read / write the value for a key m.set("to", 2)
map.size Number of keys f.size is 4
Nullish coalescing (??) Right side only for null/undefined undefined ?? 0
Majority element Appears more than n / 2 times 2 in [2, 2, 1, 2, 3]
Boyer-Moore majority vote One-pass candidate + counter algorithm O(n), O(1)
Candidate The current leader in the vote candidate = x
Confirm pass A second pass to check the candidate really is a majority count > n / 2
Floyd's cycle detection Slow and fast pointers meet inside a cycle find the duplicate
match(/[a-z]+/g) All runs of lowercase letters in a string words of a review
O(k) space Grows with the number of distinct values k the counting Map

Summary

  • Missing number: n = length + 1; n(n + 1) / 2 - sum or XOR of 1..n and the array. O(n) time, O(1) space. includes in a loop is a hidden O(n²).
  • Frequencies: count with a Map (get, set, ?? 0): keys keep their type, insertion order is kept, nothing is inherited. A plain object merges 1 and "1", sorts integer keys, and breaks on constructor.
  • Majority: Boyer-Moore voting finds a candidate in one pass with O(1) space; a second pass confirms it. The middle of a sorted array is only right when a majority exists.

Next episode: Array questions IV: two sum (brute force vs a Map), moving zeros to the end while keeping the order, and the default sort() trap: [10, 9, 1].sort() gives [1, 10, 9].