Good idea, Bad idea, TypeScript edition

TypeScript Compiler Solves LeetCode Problems

It counts as 0 nanoseconds at runtime if the compiler does everything right?

The mantra in my head the past 4 months…

I’ve been messing around with TypeScript for some other projects (you should check them out) and thought it would be fun to take on a few LeetCode challenges. As a twist though, we can’t use any functional code, just the type system to get our results! To kick things off, I’ll start with the first challenge:

https://leetcode.com/problems/two-sum/

There are a couple of caveats we’ll make to this process right away though.

1. TypeScript has no mathematical operations for numbers in the type system. Given that we have to build them, we’re going to limit our number range to [-512,512].
2. We can’t submit these results obviously, but I will add some of the test cases to check our “solutions”.
3. Everything has to compile with just stock tsc to ensure we are getting the full type checking fun though we will be using the latest versions of the language to get the best chance for success.

Our Strategy

Since we’re going for something fun anyway, we might as well just go straight into a more complex solution to this problem You could use two for loops as a naive approach to finding the pairs, but since looping in the type system is already hard, this isn’t necessarily the best strategy anyway. Instead, I’m going to do a single pass through the data while keeping a “hash map” of previously calculated deltas to find the pairs.

Since we don’t have any mathematical primitives in the type system, let’s create a few. We need a way to detect negative values, an addition and subtraction component and a higher level Subtract that handles positive/negative combinations. We’ll also use the increment/decrement strategy from the TypeScript SQL Parser series and just recursively call them until the add/subtract operations finish.

/**
 * Test for a negative number
 */
export type IsNegative<N extends number> = `${N}` extends `-${number}`
  ? true
  : false;

/**
 * Get the ABS of a number
 */
export type Abs<N extends number> = `${N}` extends `-${infer A extends number}`
  ? A
  : N;

/**
 * "Increment" the number
 */
export type Increment<N> = N extends keyof AscendingNumbers
  ? AscendingNumbers[N]
  : never;

/**
 * "Decrement" the number
 */
export type Decrement<N> = N extends keyof DescendingNumbers
  ? DescendingNumbers[N]
  : never;

/**
 * Add two positive numbers
 */
type _Add<Left extends number, Right extends number> = Right extends 0
  ? Left
  : _Add<Increment<Left>, Decrement<Right>>;

/**
 * Subtract one positive number from the other positive number
 */
type _Subtract<Left extends number, Right extends number> = Right extends 0
  ? Left
  : Left extends 0
  ? Right extends keyof PositiveToNegative
    ? PositiveToNegative[Right]
    : never
  : _Subtract<Decrement<Left>, Decrement<Right>>;

/**
 * Subtract the right number from the left
 */
export type Subtract<
  Left extends number,
  Right extends number
> = IsNegative<Left> extends true
  ? IsNegative<Right> extends true
    ? _Subtract<Abs<Right>, Abs<Left>> // -a - (-b) = b - a
    : _Add<Abs<Left>, Right> extends infer V extends keyof PositiveToNegative // -a - b = -(a + b)
    ? PositiveToNegative[V]
    : never
  : IsNegative<Right> extends true
  ? _Add<Left, Abs<Right>> // a - (-b) = a + b
  : _Subtract<Left, Right>; // a - b

Using these we can calculate the difference between the current value and the desired value to populate our hash map. Now we can work on the single pass solution that will approximate our for loop while tracking the current state.

import type { Increment, Subtract } from "../utils/numbers.js";

/** Solve the two sums problem */
export type TwoSum<
  Values extends number[],
  Target extends number
> = Values extends [infer Next extends number, ...infer Rest]
  ? Rest extends never[]
    ? "No valid solution, too few elements"
    : Rest extends number[]
    ? SinglePassHashMap<Rest, Target, 1, { [key in Subtract<Target, Next>]: 0 }>
    : never
  : never;

/** Define our hashmap */
type HashMap = { [key: number]: number };

/**
 * Single pass through the data looking for matches
 */
type SinglePassHashMap<
  Values extends number[],
  Target extends number,
  Idx extends number = 0,
  H extends HashMap = {}
> = Values extends [infer Next extends number, ...infer Rest]
  ? Next extends keyof H
    ? [H[Next], Idx] // Solution, return the index pairs
    : Rest extends never[]
    ? "Exhausted all values, no valid solution"
    : Rest extends number[]
    ? SinglePassHashMap<
        Rest,
        Target,
        Increment<Idx>,
        H & { [key in Subtract<Target, Next>]: Idx }
      >
    : never
  : never;

If we put this into our simple main.ts driver, the results for the sample solutions come back correctly and it will also tell us when there is no valid combinations.

No type errors, that’s a good sign

However, if we look at the compile time and the generated traces…

github/nathannorthcutt/ts-leetcode$ tsc --generateTrace traces
Files:               81
Lines:            43240
Identifiers:      44452
Symbols:          31974
Types:           174944
Instantiations:   83802
Memory used:    435345K
I/O read:         0.01s
I/O write:        0.00s
Parse time:       0.31s
Bind time:        0.12s
Check time:       7.04s
Emit time:        0.05s
Total time:       7.53s

Yikes!

Optimizing The Solution

Our numeric creativity seems pretty solid, but if we look at the types in the structuredTypeRelatedTo blocks, Subtract shows up like a sore thumb. While I messed around a little with those methods at first, it seemed like a bit of a red herring. The actual source of the problem is the recursive search where we call a recursive subtract and use the result as a key in a dynamic object 🙉. In retrospect that was a bit of a bad idea…

import type { Increment, Subtract } from "../utils/numbers.js";

/** Solve the two sums problem */
export type TwoSum<
  Values extends number[],
  Target extends number
> = Values extends [infer Next extends number, ...infer Rest]
  ? Rest extends never[]
    ? "No valid solution, too few elements"
    : Rest extends number[]
    ? Subtract<Target, Next> extends infer K extends number
      ? SinglePassHashMap<Rest, Target, 1, { [key in K]: 0 }>
      : never
    : never
  : never;

/** Define our hashmap */
type HashMap = { [key: number]: number };

/**
 * Single pass through the data looking for matches
 */
type SinglePassHashMap<
  Values extends number[],
  Target extends number,
  Idx extends number = 0,
  H extends HashMap = {}
> = Values extends [infer Next extends number, ...infer Rest]
  ? Next extends keyof H
    ? [H[Next], Idx]
    : Rest extends never[]
    ? "Exhausted all values, no valid solution"
    : Rest extends number[]
    ? Subtract<Target, Next> extends infer K extends number
      ? SinglePassHashMap<Rest, Target, Increment<Idx>, H & { [key in K]: Idx }>
      : never
    : never
  : never;

Just adding another layer to infer the Subtract calls appropriately as numbers helps to make everything happy (and saves us about 170k types). Here are the compiler outputs and trace now:

github/nathannorthcutt/ts-leetcode$ tsc --generateTrace traces
Files:              81
Lines:           43242
Identifiers:     44456
Symbols:         34033
Types:            4664
Instantiations:   3243
Memory used:    67983K
I/O read:        0.01s
I/O write:       0.00s
Parse time:      0.26s
Bind time:       0.11s
Check time:      0.09s
Emit time:       0.05s
Total time:      0.51s

A much happier compiler!

One Problem Down, More To Come!

That was a fun little break from some of my other work and I hope you enjoyed it as well. I’ll work on some solutions for other problems in the future and if there are some that are your favorites (that seem just barely do-able) let me know and I’ll try them out. You can find solutions in the following repo:

GitHub - nathannorthcutt/ts-leetcode: Doing dumb things with TypeScript to solve leetcode problems