The TypeScript toolbox for DSA

Every lesson from here on writes TypeScript. Some built-in methods look like one step but walk the whole array. Others give a wrong answer with no error at all.

This lesson lists what each tool costs, the five traps that break correct ideas, and what JavaScript does not give you.

Arrays: cheap at the end, costly at the front

An array keeps its items in numbered slots. Changing the end touches one slot. Changing the front renumbers every item.

┌────────────────────────────────────────────┐
│                                            │
│   push(5): add at the end, nothing moves   │
│   ┌───┬───┬───┬───┬───┐                    │
│   │ 4 │ 9 │ 2 │ 7 │ 5 │   O(1)             │
│   └───┴───┴───┴───┴───┘                    │
│                     ▲                      │
│                    new                     │
│                                            │
│   shift(): take 4, the rest move left      │
│   ┌───┬───┬───┬───┐                        │
│   │ 9 │ 2 │ 7 │ 5 │       O(n)             │
│   └───┴───┴───┴───┘                        │
│     ◀   ◀   ◀   ◀    each moved one slot   │
│                                            │
└────────────────────────────────────────────┘

The difference is real. In a test with Node:

• Emptying 100,000 items with shift() took about half a second.
• Twice the items took about four times as long: the mark of O(n²).
• Reading from a moving index took under a millisecond.

What each operation costs

A method call is not one step. includes inside a loop is a hidden loop inside a loop: O(n²).

Map and Set

Two tools solve a large share of array problems:

• Set answers "have I seen this?" in one step.
• Map answers "how many?" or "where?" in one step.

The counting pattern you will write most often:

ts

const count = new Map<string, number>();
for (const ch of "banana") {
  count.set(ch, (count.get(ch) ?? 0) + 1);
}
console.log(count); // Map(3) { 'b' => 1, 'a' => 3, 'n' => 2 }

count.get(ch) is undefined the first time, so ?? 0 starts the count at 0.

Two rules keep a Map or Set correct:

• Arrays are compared by identity, not by content. new Set([[1, 2]]).has([1, 2]) is false, because the second [1, 2] is a new array. For a grid cell, use a string key such as `${row},${col}`.
• Prefer Map to a plain object. An object turns every key into a string, so obj[1] and obj["1"] are the same slot. A Map keeps 1 and "1" apart.

Five traps

1. sort() compares as text

Without a comparator, sort() turns numbers into strings and compares those.

ts

console.log([10, 9, 1].sort()); // [1, 10, 9]
const nums = [10, 9, 1];
const sorted = nums.toSorted((a, b) => a - b);
console.log(sorted, nums); // [1, 9, 10] [10, 9, 1]

• (a, b) => a - b sorts small to large. A negative result puts a first.
• sort changes the array. toSorted returns a sorted copy and leaves the input alone.

2. Strings cannot change

s[0] = "b" is a type error in TypeScript, and it throws in strict JavaScript. Every string method returns a new string.

To build a string piece by piece, push the pieces into an array and join once:

ts

function reverseString(s: string): string {
  const parts: string[] = [];
  for (let i = s.length - 1; i >= 0; i--) parts.push(s[i]);
  return parts.join("");
}
console.log(reverseString("hello")); // "olleh"

Why not result += s[i]? In many languages, each += copies the whole string, so n appends cost O(n²).

JavaScript engines often avoid that copy, but interviewers still count it as O(n²). The array and join are O(n) everywhere.

3. Division keeps the fraction, and % keeps the sign

ts

console.log(7 / 2); // 3.5
console.log(Math.floor(7 / 2)); // 3
console.log(Math.floor(-7 / 2), Math.trunc(-7 / 2)); // -4 -3
console.log(-7 % 3); // -1: the sign follows the left side
const mod = (x: number, m: number): number => ((x % m) + m) % m;
console.log(mod(-7, 3)); // 2

• / never drops the fraction. Use Math.floor for whole-number division of positive values.
• For negative values, Math.floor rounds down and Math.trunc rounds toward zero. Pick the one the problem means.
• % can return a negative number. mod above always returns a value from 0 to m − 1.

You use % 10 and Math.floor(n / 10) in the next lesson to take a number apart, digit by digit.

4. Infinity, and the spread limit

Infinity is the right start value for a minimum: any real value beats it. Use -Infinity for a maximum.

ts

function smallest(nums: number[]): number {
  let best = Infinity; // any real value beats it
  for (const x of nums) best = Math.min(best, x);
  return best;
}
console.log(smallest([5, 3, 8]), smallest([])); // 3 Infinity

Math.max(...nums) looks shorter, but the spread passes every item as a separate argument. In Node, it throws a RangeError at about 130,000 items. The limits allow 10⁵ and more, so use the loop.

5. The shared-row grid

fill puts the same row object in every slot. Change one row, and all rows change.

┌────────────────────────────────────────────┐
│                                            │
│         fill(row): one shared row          │
│         grid[0] ──┐                        │
│         grid[1] ──┼──▶ [ 1, 0, 0 ]         │
│         grid[2] ──┘                        │
│                                            │
│         Array.from: three rows             │
│         grid[0] ─────▶ [ 1, 0, 0 ]         │
│         grid[1] ─────▶ [ 0, 0, 0 ]         │
│         grid[2] ─────▶ [ 0, 0, 0 ]         │
│                                            │
└────────────────────────────────────────────┘

ts

const bad = new Array(3).fill(new Array(3).fill(0));
bad[0][0] = 1; // [[1,0,0],[1,0,0],[1,0,0]]

const grid = Array.from({ length: 3 }, () => new Array<number>(3).fill(0));
grid[0][0] = 1; // [[1,0,0],[0,0,0],[0,0,0]]

Array.from calls the arrow function once per row, so each row is a new array.

What JavaScript does not give you

Java, C++ and Python ship more structures than JavaScript does. Here is what to use in their place.

The queue with a head index, for when you need first in, first out before those lessons:

ts

const queue: number[] = [4, 9, 2];
let head = 0; // index of the first item not taken yet
while (head < queue.length) {
  const x = queue[head++];
  if (x === 9) queue.push(7);
  console.log(x); // 4, 9, 2, 7
}

head moves forward instead of the items moving back, so taking an item is O(1). The array keeps the used items, which costs memory but no time.

Read more

• Array.prototype.sort() on MDN, with how the default order works
• Map on MDN, including how it differs from a plain object
• Remainder (%) on MDN, on the sign of the result
• Array.from() on MDN, the safe way to build a grid

Next: working with digits. Skip the other toolbox lessons unless you code in those languages too. You will take a number apart with % and /.