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

Array questions IV

two-sum (brute force vs a Map)move zeros to the end keeping orderthe default sort() trap ([1091].sort())

These are the notes for JavaScript Coding Questions, episode 8, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three questions: two sum (probably the most famous interview question of all), move every zero to the end while keeping the order, and one of JavaScript's strangest traps: [10, 9, 1].sort() gives [1, 10, 9].

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 brute force: 1.577s are copied from a real run on one machine; what matters is the size of the gap.

Q1: Two sum

Problem. Given nums and target, return the indexes of two different items that add up to target, or null.

[2, 7, 11, 15], target 9  → [0, 1]   (2 + 7)
[3, 2, 4], target 6       → [1, 2]   (2 + 4, NOT 3 + 3 with the same item)
[3, 3], target 6          → [0, 1]   (two different items with the same value)

Think out loud

  • Indexes, not values; two different positions.
  • Edge cases: the same value twice, no answer, 50,000 numbers.

The obvious attempt: every pair

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}
console.log(twoSum([2, 7, 11, 15], 9), twoSum([3, 2, 4], 6), twoSum([3, 3], 6));
[ 0, 1 ] [ 0, 0 ] [ 0, 0 ]

[3, 2, 4] gives [0, 0]: 3 + 3, the same item used twice, because j starts at i. Fix: j = i + 1.

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return null;
}
console.log(twoSum([2, 7, 11, 15], 9), twoSum([3, 2, 4], 6), twoSum([3, 3], 6), twoSum([1, 2], 10));
const big = Array.from({ length: 50000 }, (_, i) => i * 2);
console.time("brute force");
console.log(twoSum(big, 199994));
console.timeEnd("brute force");

Output:

[ 0, 1 ] [ 1, 2 ] [ 0, 1 ] null
[ 49998, 49999 ]
brute force: 1.577s

Correct, but big holds 0, 2, 4, ..., 99998 and the only pair for 199994 is the last two items, so almost every one of the n(n - 1)/2 ≈ 1.25 billion pairs is tried: O(n²).

The Map: what would complete this one?

Real-life picture: a cashier. A ₹7 note arrives and the bill is ₹9. The cashier doesn't try every pair of notes; they ask "is the ₹2 that completes this already in my drawer?", which they know at a glance. If not, the ₹7 goes into the drawer to be remembered.

For each item: need = target - nums[i]. If need was seen earlier, we have the pair. Otherwise remember nums[i] → i.

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}
console.log(twoSum([2, 7, 11, 15], 9), twoSum([3, 2, 4], 6), twoSum([3, 3], 6), twoSum([1, 2], 10));
const big = Array.from({ length: 50000 }, (_, i) => i * 2);
console.time("Map");
console.log(twoSum(big, 199994));
console.timeEnd("Map");

Output:

[ 0, 1 ] [ 1, 2 ] [ 0, 1 ] null
[ 49998, 49999 ]
Map: 6.785ms

Check before you store. At index 0 of [3, 2, 4] (target 6), need is 3, the Map is still empty, so 3 can't pair with itself. For [3, 3], the first 3 is stored, and the second finds it: [0, 1].

Complexity: O(n) time, O(n) space. Memory traded for speed.

Q2: Move zeros to the end

Problem. Move every 0 to the end, keep the other items in order, change the array in place. [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0].

Real life. A food delivery menu pushing out-of-stock items to the bottom without reshuffling the rest.

The obvious attempt: splice and push

function moveZeros(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 0) {
      arr.splice(i, 1);
      arr.push(0);
    }
  }
}
for (const a of [[0, 1, 0, 3, 12], [0, 0, 1], [1, 2]]) {
  moveZeros(a);
  console.log(a);
}

Output:

[ 1, 3, 12, 0, 0 ]
[ 0, 1, 0 ]
[ 1, 2 ]

[0, 0, 1] keeps a zero at the front. Why: splice(i, 1) removes the item at i and everything after it slides one place left. The second 0 is now at index 0, but the loop moves on to i = 1 and never looks back. Changing an array's length while walking it skips items. (Each splice is also O(n), so this is O(n²) in the worst case.)

The same bug in another form:

const a = [1, 2, 3, 4];
for (let i = 0; i < a.length; i++) if (a[i] % 2 === 0) a.splice(i, 1);
console.log(a);
const b = [2, 4, 6, 7];
for (let i = 0; i < b.length; i++) if (b[i] % 2 === 0) b.splice(i, 1);
console.log(b);
console.log([2, 4, 6, 7].filter(x => x % 2 !== 0));
[ 1, 3 ]
[ 4, 7 ]
[ 7 ]

Removing even numbers works on [1, 2, 3, 4] by luck, but leaves the 4 in [2, 4, 6, 7], which had two evens in a row. filter builds a new array and has no such problem; for in-place work, use the pattern below.

A reader and a writer

A reader pointer looks at every item; a writer pointer marks the next free slot at the front. Non-zero items are copied to the writer's slot; at the end, everything from the writer onwards becomes 0. Nothing is inserted or removed, so nothing slides.

function moveZeros(arr) {
  let write = 0;
  for (let read = 0; read < arr.length; read++) {
    if (arr[read] !== 0) arr[write++] = arr[read];
  }
  while (write < arr.length) arr[write++] = 0;
}
for (const a of [[0, 1, 0, 3, 12], [0, 0, 1], [1, 2], [0, 0], []]) {
  moveZeros(a);
  console.log(a);
}

Output:

[ 1, 3, 12, 0, 0 ]
[ 1, 0, 0 ]
[ 1, 2 ]
[ 0, 0 ]
[]

arr[write++] = x uses the old value of write as the index, then adds 1 (postfix increment). Time O(n), space O(1).

Q3: The sort() trap

console.log([10, 9, 1].sort());
console.log([5, 25, 100, 1].sort());
console.log([-1, -2, 3].sort());
console.log(["banana", "apple", "Cherry"].sort());

Output:

[ 1, 10, 9 ]
[ 1, 100, 25, 5 ]
[ -1, -2, 3 ]
[ 'Cherry', 'apple', 'banana' ]

Why. With no compare function, sort converts every item to a string and compares the strings by their UTF-16 code units, character by character, like words in a dictionary. "10" starts with "1", which comes before "9". "-1" and "-2" both start with -, then 1 < 2. And capital letters have smaller codes than lowercase ones ("C" is 67, "a" is 97), so "Cherry" comes first.

Compare functions

sort(compare) calls compare(a, b) and reads its result:

compare(a, b) returns Meaning
a negative number a goes before b
a positive number b goes before a
0 equal: keep their current order

a - b gives exactly that for ascending numbers; b - a for descending. For text, a.localeCompare(b) compares by the rules of a language.

console.log([10, 9, 1].sort((a, b) => a - b));
console.log([5, 25, 100, 1].sort((a, b) => b - a));
console.log([-1, -2, 3].sort((a, b) => a - b));
console.log(["banana", "apple", "Cherry"].sort((a, b) => a.localeCompare(b)));
[ 1, 9, 10 ]
[ 100, 25, 5, 1 ]
[ -2, -1, 3 ]
[ 'apple', 'banana', 'Cherry' ]

Never return a boolean

const nums = [5, 1, 4, 2, 3, 10, 9, 8, 7, 6, 15, 11, 14, 12, 13];
console.log(nums.toSorted((a, b) => a > b).join(" "));
console.log(nums.toSorted((a, b) => a - b).join(" "));
5 1 4 2 3 10 9 8 7 6 15 11 14 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

a > b returns true (1) or false (0), never a negative number, so sort is never told that a should come first. The result depends on the engine and the input; here nothing moved at all. Always return a number.

Copies, objects and stability

const marks = [72, 100, 9, 88];
console.log(marks.toSorted(), marks.toSorted((a, b) => a - b), marks);
const students = [
  { name: "Ravi", marks: 88 },
  { name: "Asha", marks: 95 },
  { name: "Neha", marks: 88 },
];
students.sort((a, b) => b.marks - a.marks);
console.log(students.map(s => s.name + " " + s.marks).join(", "));
[ 100, 72, 88, 9 ] [ 9, 72, 88, 100 ] [ 72, 100, 9, 88 ]
Asha 95, Ravi 88, Neha 88
  • toSorted returns a sorted copy (episode 5); with no compare function it has the same string trap.
  • Sort objects by subtracting a numeric key.
  • JavaScript's sort is stable (guaranteed since ES2019): items that compare equal keep their original order, so Ravi stays before Neha.

More text sorting:

console.log(["b", "a", "C"].sort(), ["éclair", "apple", "zebra"].sort(), ["éclair", "apple", "zebra"].sort((x, y) => x.localeCompare(y)));
console.log(["item10", "item9", "item1"].sort((x, y) => x.localeCompare(y, undefined, { numeric: true })));
console.log([3, 1, 2].sort((a, b) => b - a), [0.5, -0.1, 0.25].sort((a, b) => a - b));
[ 'C', 'a', 'b' ] [ 'apple', 'zebra', 'éclair' ] [ 'apple', 'éclair', 'zebra' ]
[ 'item1', 'item9', 'item10' ]
[ 3, 2, 1 ] [ -0.1, 0.25, 0.5 ]

é has a bigger code than z, so the default puts éclair last; localeCompare places it with the e's. { numeric: true } compares digit runs as numbers ("natural sort").

Complexity. Sorting is O(n log n) time. V8 (Node's engine) uses TimSort, which needs up to O(n) extra space.

Complexity summary

Question Approach Time Extra space
Two sum all pairs O(n²) O(1)
Two sum Map of value → index O(n) O(n)
Two sum, sorted input two pointers O(n) O(1)
Move zeros splice + push O(n²) O(1), and wrong
Move zeros reader + writer O(n) O(1)
Sorting sort / toSorted O(n log n) up to O(n)

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
Inner loop from i for (let j = i; ...) [3, 2, 4], 6 → [ 0, 0 ] an item paired with itself j = i + 1
Two nested loops all pairs brute force: 1.577s O(n²) a Map
Storing before checking seen.set(...) then has self-pairs again the item finds itself check, then store
splice inside a for arr.splice(i, 1) [0, 0, 1] → [ 0, 1, 0 ] the next item slides into i reader + writer, or filter
Default sort on numbers [10, 9, 1].sort() [ 1, 10, 9 ] compared as strings (a, b) => a - b
Boolean comparator (a, b) => a > b unsorted never negative return a number
Default sort on words ["apple", "Cherry"].sort() 'Cherry' first capitals have smaller codes localeCompare

Mini project: spend a gift card exactly

Which two dishes use a ₹500 gift card exactly? Two sum with names.

// Gift card: which two dishes use a ₹500 card exactly?
const menu = [
  { dish: "Masala dosa", price: 120 },
  { dish: "Paneer tikka", price: 260 },
  { dish: "Thali", price: 240 },
  { dish: "Lassi", price: 80 },
  { dish: "Biryani", price: 380 },
];
function pairForCard(items, card) {
  const seen = new Map();
  for (const item of items) {
    const need = card - item.price;
    if (seen.has(need)) return [seen.get(need).dish, item.dish];
    seen.set(item.price, item);
  }
  return null;
}
console.log(pairForCard(menu, 500), pairForCard(menu, 200), pairForCard(menu, 1000));
[ 'Paneer tikka', 'Thali' ] [ 'Masala dosa', 'Lassi' ] null

Extend it: return every pair (keep a list of items per price), or the pair closest to the card value without going over (sort by price, then two pointers).

Your turn: two sum on a sorted array (solution)

Problem. The array is sorted; find two items adding up to target with O(1) extra space. [1, 3, 4, 6, 8, 11], target 10 → [2, 3].

Solution

Start one pointer at each end. If the sum is too small, the only way to grow it is to move the left pointer right; if too big, move the right pointer left.

function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10), twoSumSorted([2, 7, 11, 15], 9), twoSumSorted([1, 2], 10), twoSumSorted([3, 3], 6));
[ 2, 3 ] [ 0, 1 ] null [ 0, 1 ]

Why it never misses a pair: when sum < target, nums[left] plus even the biggest remaining item is too small, so nums[left] can't be in any answer and can be dropped (and the mirror argument for right). O(n) time, O(1) space.

Practice questions (with solutions)

1. Move zeros to the front (keep the order of the rest).

Solution

The same reader/writer, walking from the right:

function zerosToFront(arr) {
  let write = arr.length - 1;
  for (let read = arr.length - 1; read >= 0; read--) {
    if (arr[read] !== 0) arr[write--] = arr[read];
  }
  while (write >= 0) arr[write--] = 0;
}
for (const a of [[0, 1, 0, 3, 12], [1, 0, 0], [5]]) { zerosToFront(a); console.log(a); }
[ 0, 0, 1, 3, 12 ]
[ 0, 0, 1 ]
[ 5 ]

2. Sort students by marks (highest first), then by name.

Solution
const students = [
  { name: "Ravi", marks: 88 },
  { name: "asha", marks: 95 },
  { name: "Neha", marks: 88 },
  { name: "Arjun", marks: 72 },
];
students.sort((a, b) => b.marks - a.marks || a.name.localeCompare(b.name));
console.log(students.map(s => `${s.name} ${s.marks}`).join(", "));
asha 95, Neha 88, Ravi 88, Arjun 72

When the marks differ, b.marks - a.marks is non-zero and decides; when it's 0 (falsy), || falls through to the name comparison.

3. Three sum: all unique triplets that add up to 0.

Solution

Sort a copy, fix the first number, then two-sum-sorted on the rest; skip repeated values so each triplet appears once.

function threeSum(nums) {
  const a = nums.toSorted((x, y) => x - y);
  const result = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (i > 0 && a[i] === a[i - 1]) continue;
    let left = i + 1, right = a.length - 1;
    while (left < right) {
      const sum = a[i] + a[left] + a[right];
      if (sum < 0) left++;
      else if (sum > 0) right--;
      else {
        result.push([a[i], a[left], a[right]]);
        while (left < right && a[left] === a[left + 1]) left++;
        while (left < right && a[right] === a[right - 1]) right--;
        left++;
        right--;
      }
    }
  }
  return result;
}
console.log(threeSum([-1, 0, 1, 2, -1, -4]), threeSum([0, 0, 0, 0]), threeSum([1, 2, 3]));
[ [ -1, -1, 2 ], [ -1, 0, 1 ] ] [ [ 0, 0, 0 ] ] []

O(n²) time (n two-pointer passes), O(n) for the sorted copy.

Quick quiz

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

console.log([3, 20, 100].sort());

(A) [ 3, 20, 100 ] (B) [ 100, 20, 3 ] (C) [ 20, 3, 100 ] (D) [ 3, 100, 20 ]

Answer

(B) [ 100, 20, 3 ]. As strings the first characters are 1, 2 and 3, so "100" < "20" < "3".

2. What does [1, 2, 3].sort((a, b) => b - a) return, and is it a new array?

Answer

[ 3, 2, 1 ], and no: sort returns the same array, sorted in place.

3. In the Map two sum, why must we check seen.has(need) before seen.set(nums[i], i)?

Answer

Otherwise, when need === nums[i] (like 3 with target 6), the item would find itself and return [i, i].

Interview questions

  1. Solve two sum in O(n). One pass with a Map of value → index; for each x look up target - x before storing x.
  2. What's the space/time trade-off? O(n) extra space buys O(n) instead of O(n²) time.
  3. Two sum on a sorted array with O(1) space? Two pointers from both ends.
  4. Why is removing items with splice inside a for loop buggy? The following items shift left and the loop skips one. Walk backwards, use filter, or use reader/writer pointers.
  5. Move zeros to the end in place. Reader/writer pointers, then fill with zeros. O(n), O(1).
  6. Why does [10, 9, 1].sort() give [1, 10, 9]? Without a comparator, items are compared as strings by UTF-16 code units.
  7. What must a compare function return? A negative number, 0 or a positive number; never a boolean.
  8. Is Array.prototype.sort stable? Yes, guaranteed since ES2019.
  9. How do you sort by two keys? (a, b) => (primary difference) || (secondary comparison).
  10. How do you sort words correctly? localeCompare, with { numeric: true } for "file2" before "file10".

Glossary

Term Meaning Example
Two sum Find two different items that add up to a target [2, 7] for 9
Brute force Trying every possibility every pair i, j
Complement The value that completes a pair: target - x need = 9 - 7
Map.has / get / set Check / read / write a key seen.has(need)
Space/time trade-off Using more memory to run faster the Map in two sum
splice(i, 1) Removes 1 item at i; later items slide left [0, 0, 1].splice(0, 1)
push(x) Adds x at the end arr.push(0)
Reader / writer pointers One index reads every item, one writes the kept ones move zeros
Postfix increment (i++) Uses the old value, then adds 1 arr[write++] = x
filter A new array of the items that pass a test nums.filter(x => x !== 0)
Lexicographic order Dictionary order, character by character "10" < "9"
UTF-16 code unit The number that represents a character in a JavaScript string "C" 67, "a" 97
Compare function (a, b) => negative, 0 or positive (a, b) => a - b
Ascending / descending Smallest first / biggest first a - b / b - a
localeCompare Compares strings by a language's rules "a".localeCompare("b") is -1
Natural sort Digit runs compared as numbers { numeric: true }
Stable sort Equal items keep their original order Ravi before Neha
TimSort The merge/insertion hybrid sort V8 uses O(n log n)
toSorted Returns a sorted copy marks.toSorted((a, b) => a - b)
Three sum All triplets that add to 0 [-1, 0, 1]

Summary

  • Two sum: for each item ask "what completes it?" (target - x) and look it up in a Map, checking before storing. O(n) time, O(n) space; the all-pairs version is O(n²), and starting j at i pairs an item with itself. On a sorted array, two pointers need only O(1) space.
  • Move zeros: splice inside a loop skips the item that slides into place. A reader and a writer pointer do it in O(n) time, O(1) space.
  • sort(): with no compare function, items are compared as strings: [10, 9, 1] → [1, 10, 9]. Pass a compare function that returns a number (a - b), never a boolean; use localeCompare for words; sort is in place and stable; toSorted copies.

Next episode: Array questions V: merging two sorted arrays, the intersection and union of two arrays, and the maximum subarray sum with Kadane's algorithm (including the all-negative case).