Get started with using TypeScript and TDD to solve LeetCode problems in VS Code
Tags: leetcode, typescript, jest, vscode
Published: 2021-01-23 22:51:25

---
title: Get started with using TypeScript and TDD to solve LeetCode problems in VS Code
published: true
description: Introduction to how to use TypeScript and Jest-based TDD to solve LeetCode problems in VS Code
tags: LeetCode, TypeScript, Jest, VSCode
//cover_image: https://direct_url_to_image.jpg
---
# Table Of Contents
* [Introduction](#introduction)
* [Install the LeetCode Extension in VS Code](#install-extension)
* [Configure the LeetCode Extension](#configure-extension)
* [Add Jest-based TDD Support](#add-tdd)
* [Select a Problem](#select-a-problem)
* [Anatomy of the Generated File](#anatomy-of-file)
* [The Initial Attempt](#initial-attempt)
 * [Algorithm](#ia-algorithm)
 * [Test Cases](#ia-test-cases)
 * [Implementation](#ia-implementation)
 * [Result](#ia-result)
* [The Second Attempt](#second-attempt)
 * [Algorithm](#sa-algorithm)
 * [Test Cases](#sa-test-cases)
 * [Implementation](#sa-implementation)
 * [Result](#sa-result)
* [The Final Attempt](#final-attempt)
 * [Algorithm](#fa-algorithm)
 * [Test Cases](#fa-test-cases)
 * [Implementation](#fa-implementation)
 * [Result](#fa-result)
* [Conclusion](#conclusion)

# Introduction <a name="introduction"/>
Recently I attended an in-person interview. In the coding challenge part I was asked to solve the [Anagram](https://leetcode.com/problems/valid-anagram/) problem. Although the problem doesn't look tricky, I was under the self-imposed pressure of needing to solve it quickly. I intuitively chose an algorithm which checks whether every character in the first word also appears in the second one and vice versa. I did realize it has bugs. I tried to save it but failed because at the moment was I in a state of panic. When I got back home, suddenly I thought shouldn't sort-and-match be a solution? What a shame! I could have performed better.

The root cause of my failure is that I didn't catch the essentials of the problem. I need to practice. It's well-known that the [leetcode.com](https://leetcode.com/) is a platform where developers can learn and practice variety of algorithms. What's more, the [leetcode.com](https://leetcode.com/) provides an extension for VS Code so that we can solve LeetCode problems without leaving VS Code. From now on I am going to talk about the experience of using TypeScript and TDD to solve a LeetCode problem in VS Code.

# Install the LeetCode Extension in VS Code <a name="install-extension"/>
Open the **Extensions** panel in VS Code, find the LeetCode extension and install it. After installation, open the LeetCode panel, login to [leetcode.com](https://leetcode.com/) with our own account. We will see a navigation tree in the panel that helps us select a problem. Right clicking on a problem brings a context menu through which we can preview the problem and create a file to work on the problem. 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/vvbt2qkajngs8rd777r0.png)
At present, there is a technical problem that prevents users from logging into the [leetcode.com](https://leetcode.com/). However, the workaround is given in the extension's home page. 

# Configure the LeetCode Extension <a name="configure-extension"/>
The LeetCode extension guides user to configure the default language and the workspace folder. These two settings can also be changed in LeetCode extension's settings page (On Mac: Code > Preferences > settings, input LeetCode in the search box to see the settings). Make sure **typescript** is selected as the default language.

# Add Jest-based TDD Support <a name="add-tdd"/>
1. Run `yarn init` in the LeetCode workspace folder to initialize the project.
2. Run `yarn add -D @types/jest jest typescript ts-jest` to install the dependencies. The [ts-jest](https://kulshekhar.github.io/ts-jest/) is *A TypeScript preprocessor with source map support for Jest that lets you use Jest to test projects written in TypeScript*.
3. Add the **jest.config.js** file in the LeetCode workspace folder with the following content:
    ```javascript
      module.exports = {
        preset: 'ts-jest',
        testEnvironment: 'node',
      };
    ```
4. Add `"test:watch": "jest --watchAll"` to the **scripts** filed in the package.json file.

#Select a Problem <a name="select-a-problem"/>
As you know, I just started to work on LeetCode. So, following the predefined order makes sense. I selected the **[2] Add Two Numbers** problem. Its difficulty level is medium. Operating on linked lists is its key point.  

# Anatomy of the Generated File <a name="anatomy-of-file"/>
Let's have a look at the content of the generated file for the selected problem:
```typescript
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {

};
// @lc code=end
```
After a few trials, the following features about the file are found:
* The file is not a node or ES6 module because there are no statements to import modules and export values in it. 
* The name of the file can be changed, however, the id in the comment is immutable.
* The [leetcode.com](https://leetcode.com/) runtime only cares about the content in the section demarcated by `// @lc code=start` and `// @lc code=end`. The main(addTwoNumbers) and helper functions must be put in this section. The import and export statements, types and classes coming from [leetcode.com](https://leetcode.com/) runtime should be put outside of the section. If these rules are not followed, the [leetcode.com](https://leetcode.com/) runtime will report compilation errors when the file is submitted. 
* The **ListNode** class used in the main function's parameters comes from the [leetcode.com](https://leetcode.com/) runtime. Our local environment doesn't have it. However, its definition is shown in the comment of the main function.

In order to use this file in our local environment, we need to do the following things:
* Export the addTwoNumbers function, so the file turns to a ES6 module.
* Extract the ListNode class from the comment and export it.

The adjusted file looks like:
```typescript
export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {

}
// @lc code=end
export default addTwoNumbers;
```
Now we can use TDD to drive our implementation.

# The Initial Attempt <a name="initial-attempt"/>
## Algorithm <a name="ia-algorithm"/>
**Convert the two linked lists to two numbers, add the numbers to get a sum, convert the sum back to a linked list.**

## Test cases <a name="ia-test-cases"/>
* toNumber: a function that converts a linked list to a number.
* fromNumber: a function that converts a number to a linked list.
```typescript
import addTwoNumbers, {
    ListNode,
    toNumber,
    fromNumber,
} from "./2.add-two-numbers";

describe("convert a number to a linked list", () => {
    test("0 to 0", () => {
        const l: ListNode = fromNumber(0);
        expect(l.val).toBe(0);
        expect(l.next).toBeNull();
    });
    test("123 to 3 > 2 > 1", () => {
        const l: ListNode = fromNumber(123);
        expect(l.val).toBe(3);
        expect(l.next.val).toBe(2);
        expect(l.next.next.val).toBe(1);
        expect(l.next.next.next).toBeNull();
    });
});

describe("Convert a linked list to a number", () => {
    test("0 to 0", () => {
        const l: ListNode = new ListNode(0, null);
        expect(toNumber(l)).toBe(0);
    });
    test("3 > 2 > 1 to 123", () => {
        const l: ListNode = new ListNode(
            3,
            new ListNode(2, new ListNode(1, null))
        );
        expect(toNumber(l)).toBe(123);
    });
});

describe("Add two numbers", () => {
    test("Example 1", () => {
        const l1 = new ListNode(2, new ListNode(4, new ListNode(3, null)));
        const l2 = new ListNode(5, new ListNode(6, new ListNode(4, null)));
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(807);
    });
    test("Example 2", () => {
        const l1 = new ListNode(0, null);
        const l2 = new ListNode(0, null);
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(0);
    });

    test("Example 3", () => {
        const l1 = new ListNode(
            9,
            new ListNode(
                9,
                new ListNode(
                    9,
                    new ListNode(
                        9,
                        new ListNode(9, new ListNode(9, new ListNode(9, null)))
                    )
                )
            )
        );
        const l2 = new ListNode(
            9,
            new ListNode(9, new ListNode(9, new ListNode(9, null)))
        );
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(10009998);
    });
});
```
## Implementation <a name="ia-implementation"/>
```typescript
export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
function toNumber(l: ListNode): number {
    let num = 0;
    let currentNode = l;
    let exponent = 0;
    while (currentNode) {
        num += currentNode.val * Math.pow(10, exponent++);
        currentNode = currentNode.next;
    }
    return num;
}

function fromNumber(num: number): ListNode {
    const numStr = String(num);
    let headNode: ListNode = null;
    for (let i = 0; i < numStr.length; i++) {
        const digit = parseInt(numStr.charAt(i), 10);
        const node = new ListNode(digit);
        node.next = headNode;
        headNode = node;
    }
    return headNode;
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const num1 = toNumber(l1);
    const num2 = toNumber(l2);
    const s = num1 + num2;
    return fromNumber(s);
}
// @lc code=end
export default addTwoNumbers;
export { toNumber, fromNumber };
```
## Result <a name="ia-result"/>
Run `yarn run test:watch`. All local test cases passed. So far so good. How will leetcode.com evaluate this solution? Let's submit it. Gotchas! The 1565 of 1568 test cases passed. 3 test cases failed! 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xt0woltry93wb1abrp1i.png)
Obviously the number represented by the first linked list is too big to be handled by the algorithm. A possible solution could be using BigInt instead of Number in the toNumber and fromNumber functions. However, BigInt is a feature of ES2020, using it in [leetcode.com](https://leetcode.com/) runtime could bring other problems. A more flexible algorithm is required.

# The Second Attempt <a name="second-attempt"/>
## Algorithm <a name="sa-algorithm"/>
**Convert the two linked lists to two arrays, calculate the the array for the sum by iteratively adding the digits from the two arrays in the same position, convert the array for the sum to a linked list.**

## Test cases <a name="sa-test-cases"/>
* fromArray: a function that converts an array of number to a linked list.
* toArray: a function that converts a linked list to an array of number.
* Because of fromArray and toArray, writing test cases becomes easier. 
* The failed test case in the initial attempt has been added.
```typescript
import addTwoNumbers, {
    ListNode,
    fromArray,
    toArray,
} from "./2.add-two-numbers";

describe("convert an array to a linked list", () => {
    test("[0] to 0", () => {
        const l: ListNode = fromArray([0]);
        expect(l.val).toBe(0);
        expect(l.next).toBeNull();
    });

    test("[2, 4, 3] to 2 > 4 > 3", () => {
        const l: ListNode = fromArray([2, 4, 3]);
        expect(l.val).toBe(2);
        expect(l.next.val).toBe(4);
        expect(l.next.next.val).toBe(3);
        expect(l.next.next.next).toBeNull();
    });
});

describe("convert a linked list to an array", () => {
    test("0 to [0]", () => {
        const array = [0];
        const l: ListNode = fromArray(array);
        expect(toArray(l)).toEqual(array);
    });
    test("2 > 4 > 3 to [2, 4, 3]", () => {
        const array = [2, 4, 3];
        const l: ListNode = fromArray(array);
        expect(toArray(l)).toEqual(array);
    });
});

describe("Add two numbers", () => {
    test("Example 1", () => {
        const l1 = fromArray([2, 4, 3]);
        const l2 = fromArray([5, 6, 4]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([7, 0, 8]);
    });
    test("Example 2", () => {
        const l1 = new ListNode(0, null);
        const l2 = new ListNode(0, null);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([0]);
    });

    test("Example 3", () => {
        const l1 = fromArray([9, 9, 9, 9, 9, 9, 9]);
        const l2 = fromArray([9, 9, 9, 9]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([8, 9, 9, 9, 0, 0, 0, 1]);
    });

    test("case 1566", () => {
        const l1 = fromArray([
            1,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            1,
        ]);
        const l2 = fromArray([5, 6, 4]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([
            6,
            6,
            4,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            1,
        ]);
    });
});
```
## Implementation <a name="sa-implementation"/>
```typescript
export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */
// @lc code=start
function fromArray(array: number[]): ListNode {
    let headNode: ListNode = null;
    for (let i = array.length - 1; i > -1; i--) {
        const node = new ListNode(array[i], headNode);
        headNode = node;
    }
    return headNode;
}

function toArray(l: ListNode): number[] {
    const array = [];
    let currentNode = l;
    while (currentNode) {
        array.push(currentNode.val);
        currentNode = currentNode.next;
    }
    return array;
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const array1 = toArray(l1);
    const array2 = toArray(l2);
    const augend = array1.length >= array2.length ? array1 : array2;
    const addend = array1.length >= array2.length ? array2 : array1;
    const sum = [];
    let carry = 0;
    for (let i = 0; i < augend.length; i++) {
        const augendDigit = augend[i];
        const addendDigit = i in addend ? addend[i] : 0;
        const digitSum = augendDigit + addendDigit + carry;
        const sumDigit = digitSum % 10;
        carry = Math.floor(digitSum / 10);
        sum.push(sumDigit);
    }
    if (carry !== 0) {
        sum.push(carry);
    }

    return fromArray(sum);
}
// @lc code=end
export default addTwoNumbers;
export { fromArray, toArray };
```
## Result <a name="sa-result"/>
Run `yarn run test:watch`. All local test cases passed. So far so good. How will [leetcode.com](https://leetcode.com/) evaluate this solution? Let's submit it. All remote test cases passed. Hooray!
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/j5vet2wuciostsq7s8ez.png)
Usually I will stop here because the algorithm seems to work well. However, the performance indicators show that the algorithm doesn't perform well in terms of the memory usage. Yes, I think it is caused by converting the linked lists into arrays and vice versa. How about accessing the digit in the list node directly?

# The Final Attempt <a name="final-attempt"/>
## Algorithm <a name="fa-algorithm"/>
**Basically, the algorithm is the same as the one used in the second attempt, the only difference is that the list nodes are accessed directly.**
## Test cases <a name="fa-test-cases"/>
We didn't add any new functionalities in this attempt. So, the test cases keep the same as the ones used in the second attempt.
## Implementation <a name="fa-implementation"/>
Although the toArray and fromArray functions are not used in the algorithm, the are convenient for writing test cases, so they are retained but moved outside of the LeetCode code section.
```typescript
export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
type Pointer = {
    l1CurrentNode: ListNode;
    l2CurrentNode: ListNode;
    carry: number;
};
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const p: Pointer = {
        l1CurrentNode: l1,
        l2CurrentNode: l2,
        carry: 0,
    };
    const sumList = new ListNode();
    let slCurrentNode: ListNode = null;
    while (p.l1CurrentNode || p.l2CurrentNode) {
        if (!slCurrentNode) {
            slCurrentNode = sumList;
        } else {
            slCurrentNode.next = new ListNode();
            slCurrentNode = slCurrentNode.next;
        }
        const augendDigit = p.l1CurrentNode?.val ?? 0;
        const addendDigit = p.l2CurrentNode?.val ?? 0;
        const digitSum = augendDigit + addendDigit + p.carry;
        const sumDigit = digitSum % 10;
        slCurrentNode.val = sumDigit;

        p.l1CurrentNode = p.l1CurrentNode?.next;
        p.l2CurrentNode = p.l2CurrentNode?.next;
        p.carry = Math.floor(digitSum / 10);
    }
    if (p.carry !== 0) {
        slCurrentNode.next = new ListNode(p.carry);
        slCurrentNode = slCurrentNode.next;
    }

    return sumList;
}
// @lc code=end
export default addTwoNumbers;
export function fromArray(array: number[]): ListNode {
    let headNode: ListNode = null;
    for (let i = array.length - 1; i > -1; i--) {
        const node = new ListNode(array[i], headNode);
        headNode = node;
    }
    return headNode;
}

export function toArray(l: ListNode): number[] {
    const array = [];
    let currentNode = l;
    while (currentNode) {
        array.push(currentNode.val);
        currentNode = currentNode.next;
    }
    return array;
}
```
## Result <a name="fa-result"/>
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/e928d1orri6xvisk07gu.png)
The performance in terms of the memory usage improved a lot!

# Conclusion <a name="conclusion"/>
There are 1700+ problems on [leetcode.com](https://leetcode.com/). The number is intimidating. The process of seeking the most suitable solution to a specific problem is both time-consuming and brain-consuming. However, the good result from the submission is encouraging. LeetCode extension for VS Code is a productivity tool, however, with the help of TDD, the experience can be better.

As to the performance indictors, don't take "**Your runtime beats *% of typescript submissions**" seriously. Sometimes the percentage is high, sometimes it is low. I think it may be affected by the load of the [leetcode.com](https://leetcode.com/) runtime. Try to submit code several times, if it keeps being low then the algorithm may need to be improved. The memory usage indicator is relatively stable and can be used to assess the level of memory usage of the algorithm.