leetcode - freeCodeCamp.org

LeetCode Meditations: A Visual Handbook of Data Structures and Algorithms Concepts

Eda Eren — Thu, 29 May 2025 19:52:13 +0000

It may seem like an oxymoron when the words "LeetCode" and "meditation" are used together – after all, one thing that almost everyone can agree is that LeetCode is challenging. It's called grinding LeetCode for a reason.

It doesn't have anything to do with the platform, of course, but rather what it represents: tackling problems for hours on end, usually to find a solution that is even harder to understand.

But what is more challenging is finding a roadmap to solve those problems with very little knowledge of data structures and algorithms. This handbook is more or less based on the Blind 75 list that's included in neetcode.io's practice problems. This is an amazing resource that offers an organized study roadmap for solving LeetCode problems.

In fact, why not take a more structured and calmer approach? We can treat learning about the topics on the list like taking a brief walk in nature – a sort of meditation, if you will.

That said, this handbook is not about specific problems. Rather it’s about understanding the concepts behind them in a casual manner. It is also language agnostic – sometimes you’ll see TypeScript, sometimes Python, and sometimes JavaScript.

This handbook also requires you to be patient, to relax, to take a step back and pay attention. The mid-quality GIFs used in the handbook (maybe ironically!) intend to encourage this. They are not videos, so you can wait for it to come to a moment that you didn't understand or missed instead of hastily rewinding it back or rushing to a certain point in the future.

Solving hundreds of LeetCode problems may be the gate to go through to get an interview at big tech companies…but learning the topics that the problems are about is not under anyone's monopoly.

With that said, let's start the first chapter.

Prerequisites
Chapter One: Arrays & Hashing
Chapter Two: Two Pointers
- Palindrome example
- Squares of a sorted array example
Chapter Three: Sliding Window
- Fixed window size
- Dynamic window size
Chapter Four: Stack
Chapter Five: Binary Search
Chapter Six: Linked Lists
Interlude: Fast & Slow Pointers
- Finding the middle node of a linked list
Chapter Seven: Trees
- Binary trees, binary search trees (BSTs)
Chapter Eight: Heap / Priority Queue
Chapter Nine: Backtracking
- Subsets
Chapter Ten: Tries
Chapter Eleven: Graphs
- Representing graphs
- Traversals
  - Breadth-First Search
  - Depth-First Search
Chapter Twelve: Dynamic Programming
Chapter Thirteen: Intervals
Chapter Fourteen: Bit Manipulation
Conclusion
Resources & Credits

Prerequisites

Before diving in, some familiarity with TypeScript/JavaScript and Python may be helpful, as these are the languages I use for the examples. Also, a basic understanding of Big O notation is useful as we go over time and space complexities.

Even though we don't go through the mathematics behind the concepts, some basic mathematical knowledge can also help. That said, it's definitely not necessary to enjoy or learn something useful from this handbook.

Chapter One: Arrays & Hashing

Let's very briefly get to know our topics for this chapter: dynamic arrays, hash tables, and prefix sums.

Dynamic Arrays

Dynamic arrays are, well, dynamic. They're flexible and can change their size during execution.

Python's list type is a dynamic array. We can create an items list, for example:

items = [3, 5]

The length of items is 2, as you can see, but its capacity is greater than or equal to its length. In fact, capacity refers to the total size, whereas length is the actual size.

Since dynamic arrays are still arrays, they need a contiguous block of memory.

We can easily add an item to items:

items.append(7)

And add some more:

items.append(9)
items.append(11)
items.append(13)

All the while, the length and capacity of items keep growing dynamically.

Time and space complexity

Accessing an element is $O(1)$ as we have random access.

Inserting a new element or deleting an element is $O(n)$ (think about having to shift all the elements before inserting or after deleting an item). But, in order to not be too pessimistic, we can look at amortized analysis – in that case, inserting/deleting at the end of the array becomes $O(1)$.

Space complexity is $O(n)$, as the need for space will grow proportionately as the input increases.

If you need more info about time and space complexity, you can refer to this guide.

Hash Tables

A hash table maps keys to values, implementing an associative array.

Python's dict is one example:

number_of_petals = {
    'Euphorbia': 2, 
    'Trillium': 3, 
    'Columbine': 5,
}

Also JavaScript's "object"s:

let numberOfMoons = {
  'Earth': 1,
  'Mars': 2,
  'Jupiter': 95,
  'Saturn': 146,
  'Uranus': 27,
  'Neptune': 14,
};

There are two important ingredients for a hash table:

an array of "buckets" to store the data
a hash function to map the data to a specific index in the array

Hashes are usually large integers, so to find an index, we can take the result of the hash modulo the array's length.

Note: The hash function that's mapping the elements to buckets is not the hash() used in the visual (it's just a Python function to calculate the hash value of an object). The hash function in this case is the modulo ( % ) operation.

Here, with the hash value of each item's key, we calculate the remainder when it's divided by the length of the array to find which "bucket" it should go to.

The ratio of the number of elements to the number of buckets is called the load factor, and the higher it gets, the more collisions (when elements have to be inserted at the same place in the array) occur.

There are some collusion resolution tactics like linear probing (probing through the array until finding an empty bucket) and chaining (chaining multiple elements as linked lists), but we'll not go into those for now.

Time and space complexity

The average case for searching, inserting, and deleting operations are $O(1)$ as we use keys to look up the values.

Space complexity is $O(n)$ as it grows linearly with the amount of elements.

Prefix Sums

A prefix sum is the sequence of numbers we get after adding the sums of running totals of another sequence. It's also called the cumulative sum.

The first element of the resulting array is the first element of the input array. That's fine. We start at the second item, and add the previous numbers each time as we go. That is:

$$result[i] = \begin{cases} nums[0] & \text{if } i \text{ is zero} \\ result[i - 1] + nums[i] & \text{if } i \geq 1 \end{cases}$$

In code, we can implement that easily:

def runningSum(nums):
    result = [nums[0]]

    for i in range(1, len(nums)):
        result.append(result[i - 1] + nums[i])

    return result

Time and space complexity

Time complexity for a prefix sum is $O(n)$ because we're iterating over each of the elements in the array.

The space complexity is also $O(n)$ because the need for external space grows as the length of the original array grows.

Chapter Two: Two Pointers

One of the techniques of iterating through an array is the two pointers technique, and it is as simple as it sounds: we just keep two pointers, one starting from the left, and the other from the right, gradually getting closer to each other.

Palindrome example

A very basic example can be the one where we check if a string is a palindrome or not. A palindrome is a string that reads the same forwards and backwards.

In an imaginary world where all the inputs always consist of lowercase English letters, we can do it like this:

// s consists of lowercase English letters
function isPalindrome(s: string) {
  let left = 0;
  let right = s.length - 1;

  while (left <= right) {
    if (s[left++] !== s[right--]) {
      return false;
    }
  }

  return true;
}

We initialize two pointers: left and right. left points to the start of the array, while the right points to the last element. As we loop while left is less than right, we check if they are equal. If not, we return false immediately. Otherwise, our left pointer is increased – that is, it's moved to the right one step, and our right pointer is decreased, meaning that it's moved to the left one step. When they eventually overlap, the loop terminates, and we return true.

Let's say our string is 'racecar', which is a palindrome. It will go like this:

Squares of a sorted array example

Another example where we can use the two pointers technique is the problem Squares of a Sorted Array.

The description says:

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

For example, if the input is [-4, -1, 0, 3, 10], the output should be [0, 1, 9, 16, 100].

Now obviously, we can just square each one, and then sort the array with a built-in sort method, and be done with it. But a sorting operation is never better than $O(n \ log \ n)$ runtime, so we can do it using two pointers in just $O(n)$ time:

function sortedSquares(nums: number[]): number[] {
  let left = 0;
  let right = nums.length - 1;
  let result = [];

  while (left <= right) {
    if (Math.abs(nums[left]) > Math.abs(nums[right])) {
      result.push(nums[left++] ** 2);
    } else {
      result.push(nums[right--] ** 2);
    }
  }

  return result.reverse();
}

We compare the absolute value of the items that left and right are pointing to, and push the square of the greater one to our result array. And we return the reversed version of it.

Note: The reason we return the reversed result is that the array is initially already sorted, and we get the largest absolute value first. The reason that works is related to how two pointers work: as we start from both ends, we initially start with the smallest and largest values in the array.

Because we only make one pass through the array while comparing, and then later reversing, it ends up being $O(n)$, a better runtime than $O(n \ log \ n)$.

Chapter Three: Sliding Window

Now that we're familiar with the Two Pointers technique, we can add another one to our toolbox: the Sliding Window. It's usually used for operations done on the subsets of a given data. It also comes in two flavors: fixed window size and dynamic window size.

Fixed window size

If we have a size constraint in a given problem – say, we need to check a $k$-sized subarray – sliding window is an appropriate technique to use.

For example, getting the maximum subarray (of size $k$) sum of a given array can be done like this:

Note that the window size is $k$, and it doesn't change throughout the operation – hence, fixed size.

A very cool thing to notice here is that with each slide, what happens to our sum is that we add the right element, and decrease the left element.

Let's look at an example for getting the maximum sum of subarray with given size k:

function maxSubarray(numbers: number[], k: number) {
  if (numbers.length < k) {
    return 0;
  }

  let currentSum = 0;

  // Initial sum of the first window 
  for (let i = 0; i < k; i++) {
    currentSum += numbers[i];
  }

  let maxSum = currentSum;

  let left = 0;
  let right = k;

  while (right < numbers.length) {
    currentSum = currentSum - numbers[left++] + numbers[right++];
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

Note: Updating the pointers can be done outside the brackets as well, like this:

while (right < numbers.length) {
  currentSum = currentSum - numbers[left] + numbers[right];
  maxSum = Math.max(maxSum, currentSum);
  left++;
  right++;
}

Since the postfix operator returns the value first, they can be used inside the brackets to be slightly more concise.

Here, we first get the initial sum of our window using the for loop, and set it as the maximum sum.

Then we initialize two pointers: left that points to the left end of the window, and right that points to the right end of the window. As we loop, we update our currentSum, decreasing the left value, and adding the right value. When our current sum is more than the maximum sum, maxSum variable is updated as well.

Dynamic window size

As opposed to the fixed window size version, the size of the window changes dynamically this time.

For example, let's take a brief look at the problem Best Time to Buy and Sell Stock. We need to choose a day to buy a stock, and sell it in the future. The numbers in the array are prices, and we need to buy the stock at as low a price as we can, and sell it as high as we can.

We can initialize left and right pointers again, but this time, we'll update them depending on a condition. When the left item is less than the one on the right, that means it's good – we can buy and sell at those prices, so we get their difference and update our maxDiff variable that holds the maximum difference between the two.

If, however, the left one is greater than the right one, we update our left pointer to be where the right is at. In both cases, we'll continue updating right until we reach the end of the array.

With the blue arrow indicating the left pointer, and the red the right one, the process looks like this:

The solution looks like this:

function maxProfit(prices: number[]): number {
  let left = 0;
  let right = left + 1;
  let maxDiff = 0;

  while (right < prices.length) {
    if (prices[left] < prices[right]) {
      let diff = prices[right] - prices[left];
      maxDiff = Math.max(maxDiff, diff);
    } else {
      left = right;
    }

    right++;
  }

  return maxDiff;
}

Note: This one is also called fast/catch-up version of dynamic sliding window, because the left pointer jumps to catch up with the right pointer in the else block.

Time and space complexity

Both examples have the same time and space complexity: The time complexity is $O(n)$ because in the worst case we iterate through all the elements in the array. The space complexity is $O(1)$ as we don't need additional space.

Chapter Four: Stack

A stack data type is perhaps one of the most well-known ones. A stack of books might be a good example to visualize, but insertion and deletion can only happen from the one end. A stack operates through the last-in first-out (LIFO) principle: the last item to go in is the first to go out.

Usually we'll have methods for pushing an element onto the stack, and popping an element from the stack.

For example, let's say we're looking for valid parentheses in a given string, and the operation we'll do goes like this.

As we iterate over the characters in the string, we push the character onto the stack. If we pushed a closing parenthesis (one of ), }, or ]), then, if the previous pushed element is its opening pair, we'll pop that pair from the stack.

If, at the end, the stack is empty, the string consists of valid parentheses.

A stack can be implemented as an array or a linked list. But using linked lists is more common because with arrays, we have a potential stack overflow when we predefine a maximum stack size. On the other hand, linked lists are not static when it comes to memory, so they are a good candidate to implement stacks.

Linked lists are also efficient because we are using one end of the stack for insertion and deletion, and doing these are constant time operations.

Let's look at one easy stack implementation in Python.

Now, we can use a list, but a list in Python is implemented as a dynamic array underneath, so at one point, pushing an item can be an $O(n)$ operation if the list needs to be copied into another memory location. For that reason, we'll use a deque, which is implemented as a doubly-linked list, so that we know push and pop operations will be $O(1)$.

from collections import deque

class Stack:
    def __init__(self):
        self._stack = deque()

    def push(self, item):
        self._stack.append(item)

    def pop(self):
        return self._stack.pop()

    def peek(self):
        return self._stack[-1]

    def is_empty(self):
        return not bool(len(self._stack))

    def size(self):
        return len(self._stack)

In addition to push and pop, we'll also usually have functions like peek to get the topmost item in the stack, is_empty to check if the stack is empty, and size to get the size of the stack.

We can also do it using JavaScript. Now, we can do it using an array, but we want to use a linked list instead. Since we don't have a robust built-in library like Python this time, we'll implement a very simple version of it ourselves. Even though we haven't seen linked lists so far, the basic idea is that we have nodes, each of which has a data value, and a next pointer pointing to the next node.

Let's create a simple node first:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

We can write our stack now:

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item);
    node.next = this.top;
    this.top = node;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) { return null; }

    const data = this.top.data;
    this.top = this.top.next;
    this.length--;

    return data;
  }

  peek() {
    if (this.isEmpty()) { return null; }

    return this.top.data;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.length;
  }
}

Now, let’s use it:

let myStack = new Stack();

myStack.push(5);
myStack.push(17);
myStack.push(55345);
myStack.push(0);
myStack.push(103)

console.log(myStack.size()) // 5
console.log(myStack.peek()) // 103

myStack.pop()

console.log(myStack.size()) // 4
console.log(myStack.peek()) // 0

Time and space complexity

Each method we defined for our stack has $O(1)$ time complexity, and it would be the same if we were to use an array as well. However, as mentioned above, arrays have limitations in that having to allocate a predefined stack size can lead to a stack overflow. And if we were to use a dynamic array, the whole array might need to be copied to go into another memory location after a certain size is reached, leading to $O(n)$ time. So, linked lists are ideal to implement a stack data type.

If the space complexity is linear – $O(n)$– the stack will grow linearly with the number of items in it.

Chapter Five: Binary Search

Binary search is one of the most well-known algorithms. It's also a divide-and-conquer algorithm, where we break the problem into smaller components.

The crux of binary search is to find a target element in a given sorted array. We have two pointers: high to point to the largest element, and low to point to the smallest element. We first initialize them for the whole array itself, with high being the last index and low being the first index.

Then, we calculate the midpoint. If the target is greater than the midpoint, then we adjust our low pointer to point to the mid + 1, otherwise if the target is less than the midpoint, we adjust high to be mid - 1. With each iteration, we eliminate half the array until the midpoint equals the target or the low pointer passes high.

If we find the index of the target, we can return it as soon as we find it. Otherwise, we can just return -1 to indicate that the target doesn't exist in the array.

For example, if we have a nums array [-1, 0, 3, 5, 9, 12] and our target is 9, the operation looks like this:

We can write it in TypeScript like this:

function search(nums: number[], target: number): number {
  let high = nums.length - 1;
  let low = 0;

  while (high >= low) {
    let mid = Math.floor((high + low) / 2);

    if (target > nums[mid]) {
      low = mid + 1;
    } else if (target < nums[mid]) {
      high = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}

Time and space complexity

The time complexity of a binary search algorithm is $O(log \ n)$ in the worst case. (For example, if the target is not in the array, we'll be halving the array until there is one element left.) The space complexity is $O(1)$ as we don't need extra space.

Chapter Six: Linked Lists

A linked list is a linear data structure that you're likely to be familiar with. It is also a data structure that can grow and shrink dynamically – so unlike arrays, there's no need to allocate memory beforehand.

An important part of a linked list is the head pointer that points to the beginning of the list. There may or may not be a tail pointer that also points to the end of the list.

The core ingredient of a linked list is a simple node, which consists of two parts: data and the next pointer. So, it is an important idea to remember: a node only knows about its data and its neighbor.

The very last node in the linked list points to null to indicate it's the end of the list.

But there are different types of linked lists that differ from each other slightly, so let's briefly take a look at them.

Singly linked lists

The core idea with singly linked lists is that each node, along with the data it has, has a pointer that points only to the next node:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

And here is an example where we have three nodes, holding the values 1, 2, and 3 consecutively:

Here is a simple implementation of a singly linked list in JavaScript:

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add value to the end of the list
  append(value) {
    let node = new Node(value);
    // If the list is empty
    if (this.head === null) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

  // Add value to the beginning of the list
  prepend(value) {
    let node = new Node(value);
    // If the list is empty
    if (this.head === null) {
      this.head = node;
      this.tail = this.head;
    } else {
      node.next = this.head;
      this.head = node;
    }

    this.length++;
    return this;
  }

  remove(value) {
    // If the list is empty, return null
    if (this.head === null) { 
      return null; 
    }

    // If it is the first element
    if (this.head.data === value) {
      this.head = this.head.next;
      this.length--;
      // If it is the only element 
      // (we don't have anything after removing it)
      if (this.head === null) {
        this.tail = null;
      } 
      return;
    }

    let currentNode = this.head;

    while (currentNode.next) {
      if (currentNode.next.data === value) {
        currentNode.next = currentNode.next.next;
        // If it is the last element, update tail
        if (currentNode.next === null) {
          this.tail = currentNode;
        } 
        this.length--;
        return;
      }
      currentNode = currentNode.next;
    }
  }

  search(value) {
    let currentNode = this.head;

    while (currentNode) {
      if (currentNode.data === value) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    // If the value does not exist, return null
    return null;
  }

  printList() {
    let values = [];
    let currentNode = this.head;
    while (currentNode) {
      values.push(currentNode.data);
      currentNode = currentNode.next;
    }

    console.log(values);
  }
}

Note: We'll keep a tail pointer in all these examples for convenience. It doesn't hurt to have a tail pointer.

We can now use it:

const mySinglyLinkedList = new SinglyLinkedList();

mySinglyLinkedList.prepend(3);
mySinglyLinkedList.prepend(143);
mySinglyLinkedList.prepend(5);

mySinglyLinkedList.printList(); // [ 5, 143, 3 ]

mySinglyLinkedList.append(21);
mySinglyLinkedList.printList(); // [ 5, 143, 3, 21 ]

console.log(mySinglyLinkedList.search(143));
// Node {
//   data: 143,
//   next: Node { data: 3, next: Node { data: 21, next: null } }
// }

mySinglyLinkedList.remove(143);
mySinglyLinkedList.printList(); // [ 5, 3, 21 ]

console.log(mySinglyLinkedList.search(143)); // null

Doubly linked lists

Doubly linked lists differ from the "singly" ones in that each node also has another pointer that points to the previous element.

So, this time, a single node will look different:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.previous = null;
  }
}

Here is the same example as above, but as a doubly linked list:

A simple implementation might look like this:

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add value to the end of the list
  append(value) {
    let node = new Node(value);
    // If the list is empty
    if (this.head === null) {
      this.head = node;
      this.tail = this.head;
    } else {
      node.previous = this.tail;
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

  // Add value to the beginning of the list
  prepend(value) {
    let node = new Node(value);
    // If the list is empty
    if (this.head === null) {
      this.head = node;
      this.tail = this.head;
    } else {
      this.head.previous = node;
      node.next = this.head;
      this.head = node;
    }

    this.length++;
    return this;
  }

  remove(value) {
    // If the list is empty, return null
    if (this.head === null) { 
      return null;
    }

    let currentNode = this.head;

    // If it is the first element
    if (currentNode.data === value) {
      this.head = currentNode.next;
      // If the removed element is not the only one,
      // make the previous pointer of the new head null
      if (this.head) {
        this.head.previous = null;
      // If the removed element was the only element,
      // point the tail to null as well
      } else {
        this.tail = null;
      }
      this.length--;
      return;
    }

    while (currentNode) {
      if (currentNode.data === value) {
        if (currentNode.previous) {
          currentNode.previous.next = currentNode.next;
        }
        if (currentNode.next) {
          currentNode.next.previous = currentNode.previous;
        // If it's the last element in the list, update tail
        // to point to the previous node
        } else {
          this.tail = currentNode.previous;
        }

        this.length--;
        return;
      }

      currentNode = currentNode.next;
    }
  }

  search(value) {
    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.data === value) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    // If the value does not exist, return null
    return null;
  }

  printList() {
    let values = [];
    let currentNode = this.head;

    while (currentNode) {
      values.push(currentNode.data);
      currentNode = currentNode.next;
    }

    console.log(values);
  }
}

Circular linked lists

With circular linked lists, we have the last node also pointing to the first element, creating circularity.

We'll only look at the singly circular linked list for simplicity's sake, so our node will look the same as in the first example:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

The same example, in a circular linked list fashion:

Here is a simple implementation:

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add value to the "end" of the list
  append(value) {
    let node = new Node(value);
    // If the list is empty
    if (this.head === null) {
      this.head = node;
      this.tail = node;
      // As the only node in the list, it should point to itself
      node.next = node;
    } else {
      // As the "last" node, it should point to the head (this.tail.next)
      node.next = this.tail.next;
      this.tail.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

  // Add value to the beginning of the list
  prepend(value) {
    let node = new Node(value);
    node.next = this.head;
    // Update last node's next pointer to point to the new node
    this.tail.next = node;
    this.head = node;
    this.length++;
    return this;
  }  

  remove(value) {
    // If the list is empty, return null
    if (this.head === null) { 
      return null; 
    }

    // If it is the first element
    if (this.head.data === value) {
      // If it's the only element
      if (this.head.next === this.head) {
        this.head = null;
        this.tail = null;
        return;
      }
      this.head = this.head.next;
      this.tail.next = this.head;
      this.length--;
      return;
    }

    let currentNode = this.head;
    let prevNode = null;

    // Iterate until you find the value or
    // you don't find it after traversing the whole list
    while (currentNode.data !== value || prevNode === null) {
      if (currentNode.next === this.head) { 
        break; 
      }
      prevNode = currentNode;
      currentNode = currentNode.next;
    }

    if (currentNode.data === value) {
      // If there is a previous node before the element to be removed,
      // update the previous node's next pointer to point to
      // the one after the element to be removed
      // (unlink it)
      if (prevNode) {
        prevNode.next = currentNode.next;
        // If the element to be removed is the last one,
        // update tail to be the previous node
        if (this.tail === currentNode) {
          this.tail = prevNode;
        }
      // If the element to be removed is the first one in the list
      } else {
        // If it's the only one in the list
        if (this.head.next === this.head) {
          this.head = null;
          this.tail = null;
        } else {
          this.head = this.head.next;
          this.tail.next = this.head;
        }
      }
    }
  }

  printList() {
    let nodes = [];
    let currentNode = this.head;
    if (this.head === null) { 
      console.log(nodes); 
      return;
    }

    // Traverse the list once to add the values, 
    // don't go in circles
    do {
      nodes.push(currentNode.data);
      currentNode = currentNode.next;
    } while (currentNode !== this.head);

    console.log(nodes);
  }
}

Time and space complexity

With linked lists, the time complexity for accessing an element is in the worst case $O(n)$. Prepending and appending an element depends on whether we have a tail pointer. If we have it, then both operations are $O(1)$, as we only need to arrange pointers. But if we don't have a tail pointer, appending an element requires traversing the whole list, so it is an $O(n)$ operation. Removing an element is similar – in the worst case, it is $O(n)$.

If the space complexity is linear – $O(n)$– then the amount of data to store grows linearly with the number of nodes in the list.

Interlude: Fast & Slow Pointers

Let's take a quick look at a technique that comes in handy when it comes to working with linked lists.

We can keep two pointers while traversing a linked list: fast and slow. While the fast one increases by two steps, the slow pointer will increase by just one step.

Finding the middle node of a linked list

When the fast pointer reaches the end of the list, the slow pointer will be at the "middle" node.

Let's see how it might work:

let slow = head;
let fast = head;

while (fast !== null && fast.next !== null) {
  slow = slow.next;
  fast = fast.next.next;
}

We can think of a list like [1, 2, 3, 4, 5] (where each value is a node in the linked list).

Both fast and slow start pointing to the head, that is, 1.

Then, we update the slow pointer one step, which will be 2. And, fast will be at 3.

When we update slow again, it will be at 3. When the fast pointer increases, it will be two steps ahead, and its next pointer will point to the null value, at which point our loop will stop iterating.

slow will end up pointing to the node with the value 3, which is the middle node.

With an even number of nodes, there are two candidates for the middle node. For example, with a list like [1, 2, 3, 4], our current implementation will find the middle as 3. This technique is also useful to detect cycles in a linked list.

Chapter Seven: Trees

Let’s take a look at a non-linear data structure that is pretty familiar to many developers: trees.

Whether familiarity breeds contempt or not is arguable, so let's start with the simplest component of a tree: a node.

Trees, like linked lists, are made up of nodes. The simplest version of a tree is just the root node which doesn't have any edges (links) pointing to it; that is, it has no parent nodes. It is the starting point, in a way.

A tree can only have one root node, and when you think about it, if there are $n$ nodes in a tree, that means there are $n - 1$ edges (links) because there is no edge (link) pointing to the root node.

If you've looked at a tree long enough, you might've had a moment of epiphany: a tree has smaller trees within itself. A branch may as well be a trunk, having other branches for the little tree it constitutes.

The tree data structure is like this, it is recursive: a child node can be the root of a subtree.

Two terms that are important when it comes to a tree node are depth and height.

The depth of a node is how far away it is from the root node (how many edges (links) does it take to travel from the root node to it), and the height of a node is how far away it is from its furthest leaf node (which is a node that has no children).

Note: The height of the root node is the same as the height of the whole tree.

A balanced tree is one where the heights of the left and right subtrees of every node differ by at most 1.

Binary trees, binary search trees (BSTs)

A binary tree is a tree where each node has at most two children. That is, a node can have a left child node and a right child node, and no more.

The maximum number of nodes in a binary tree is $2^h - 1$ where $h$ is the height of the tree. This is where the binary of the binary tree makes sense: on each level, the number of nodes grows proportionately to the exponents of $2$.

For example, the number of nodes on the first level (the 0th level) is $2^0 = 1$, which is just the root node. The second level has at most 2 nodes: $2^1 = 2$ (remember that we're counting from $0$, so the second level is $1$).

A binary search tree is a binary tree where the values smaller than the node go to its left and those greater than it go to its right:

$$\text{left children } \lt \text{ node } \lt \text{ right children}$$

Here is an example:

We can define a tree node like this:

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val;
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
  }
}

Inserting into a binary search tree

If we want to insert a new node into a binary search tree, we need to insert it into its proper place to keep the properties of a BST intact.

Recursive solution:

function insertIntoBST(root: TreeNode | null, val: number) {
  if (root === null) {
    return new TreeNode(val);
  }

  if (val < root.val) {
    root.left = insertIntoBST(root.left, val);
  } else {
    root.right = insertIntoBST(root.right, val);
  }

  return root;
}

Here, we traverse the tree until we find a space (a null position) for our value that is waiting to be a TreeNode. We start with the root node. If the value of the node-to-be-inserted is less than the value of the root node, we go left (passing root.left as the root argument to the function). Otherwise, we go right (passing root.right as the root argument).

Time and space complexity

The time complexity is $O(h)$ where $h$ is the height of the tree. On each level in the tree, we either go left or right, so we don't necessarily visit every single node. The space complexity is also $O(h)$ because we use recursion, creating a new stack frame for each function call.

Note that if the tree is unbalanced, the time and space complexity can be said to be $O(n)$.

Iterative solution:

We can also do it iteratively, using pointers only:

function insertIntoBST(root: TreeNode | null, val: number) {
  if (root === null) {
    return new TreeNode(val);
  }

  let prevNode: TreeNode | null = null;
  let currentNode: TreeNode | null = root;

  while (currentNode !== null) {
    prevNode = currentNode;
    if (val < currentNode.val) {
      currentNode = currentNode.left;
    } else {
      currentNode = currentNode.right;
    }
  }

  if (prevNode) {
    if (val < prevNode.val) {
      prevNode.left = new TreeNode(val);
    } else {
      prevNode.right = new TreeNode(val);
    }
  }

  return root;
}

Here, we do the same thing: iterating until we find the correct place, but also keeping track of the parent node. Then, we insert the node as either the left or the right child of the parent, depending on its value.

Time and space complexity

The time complexity is again $O(h)$ (or if the tree is unbalanced, $O(n)$) for the same reason as in the recursive solution. But the space complexity is constant – $O(1)$ – as we only use pointers.

Deleting from a binary search tree

The challenging thing when deleting a node from a BST is keeping the BST as a BST. All smaller values should still go to the root node's left subtree, and all those that are larger should go to the root node's right subtree.

Let's take a look at how we might do it in JavaScript:

function deleteNode(root: TreeNode | null, key: number) {
  if (root === null) {
    return root;
  }

  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Node-to-be-deleted has no children
    if (root.left === null && root.right === null) {
      return null;
    } 

    // If either the left or the right child exists,
    // return the one that exists as the new child 
    // of the parent node (of the node-to-be-deleted)
    if (root.left === null || root.right === null) {
      return root.left ? root.left : root.right;
    }

    // If both children exist, traverse the left subtree, get its maximum value...
    let currentNode = root.left;

    while (currentNode.right !== null) {
      currentNode = currentNode.right;
    }

    // ...replace it with the node-to-be-deleted
    root.val = currentNode.val;
    // ...then apply the recursion to the left subtree to get rid of the duplicate value
    root.left = deleteNode(root.left, root.val);
  }

  return root;
}

We traverse the tree until we find the node to be deleted. Once we find it, there are several things to do.

In the case where it doesn't have any child nodes, we can return null and be done with it.

If it has one child node, we can return the one that exists using the ternary operation (return root.left ? root.left : root.right).

Note: In this case, we're essentially making the root of the subtree the child of the parent node.

For example, in the image, if the node-to-be-deleted is 10 (it has only right child node with the value 14), we make 14 the right child of 8. It doesn't break our BST, because those that are larger than 8 continue to be in the right subtree of 8:

Otherwise, if both the left and right children of the node-to-be-deleted exist, we need to do something different.

In this case, we'll replace the node-to-be-deleted with the largest value in the left subtree.

But, after replacing, we'll have two nodes of the same value in both places, so we need to apply deleteNode itself to the subtree that we've taken our replacement node from.

This is all done to keep the BST as BST. It might be a bit difficult to wrap your head around at first, but NeetCode has a detailed explanation of this problem.

Note that we can also use the smallest value in the right subtree as well. In that case, our code would look like this:

let currentNode = root.right;

while (currentNode.left !== null) {
  currentNode = currentNode.left;
}

root.val = currentNode.val;
root.right = deleteNode(root.right, root.val);

Time and space complexity

Similar to inserting into a BST, both the time and space complexity of deleting from a BST will be $O(h)$ where $h$ is the height of the tree.

Traversals

We'll take a brief look at two of the most famous ways to traverse a tree where the order in which we visit the nodes matters: depth-first search and breadth-first search.

1. Depth-First Search (DFS)

In a depth-first search, we traverse through a branch until we get to a leaf node. Then, we backtrack and do the same thing with another branch.

There are three common ways to do a depth-first search:

preorder traversal
inorder traversal
postorder traversal

Preorder traversal:

It goes like this: We first visit the node, then go on to its left subtree, then the right subtree.

node ➞ left subtree ➞ right subtree

We can do a preorder walk recursively:

function preorderWalk(node) {
  if (node === null) {
    return;
  }

  console.log(node.val);
  preorderWalk(node.left);
  preorderWalk(node.right);
}

Inorder traversal:

It goes like this: we first visit the left subtree, then the node, then the right subtree.

left subtree ➞ node ➞ right subtree

Note: The inorder traversal gives us the sorted values.

We can do an inorder walk recursively as well:

function inorderWalk(node) {
  if (node === null) {
    return;
  }

  inorderWalk(node.left);
  console.log(node.val);
  inorderWalk(node.right);
}

Postorder traversal:

It goes like this: we first visit the left subtree, then the right subtree, and finally the node.

left subtree ➞ right subtree ➞ node

We can do a postorder walk recursively:

function postorderWalk(node) {
  if (node === null) {
    return;
  }

  postorderWalk(node.left);
  postorderWalk(node.right);
  console.log(node.val);
}

2. Breadth-First Search (BFS)

In breadth-first search, we visit the nodes level by level, that is, visiting every child of a node first before moving on.

A queue is used when implementing a BFS. Since we don't have edges connecting all the children on one level together, it makes sense to keep them in a queue and visit each one when their time comes. When a node is added to the queue and has not been visited yet, it's called a discovered node.

A simple BFS operation looks like this (which is repeated until the queue is empty):

visit node
enqueue left child
enqueue right child

Note that the breadth-first search is also known as level-order traversal.

A simple example of a level-order traversal in JavaScript might look like this:

function levelOrderWalk(root) {
  if (root === null) {
    return;
  }

  let queue = [];
  queue.push(root);

  while (queue.length > 0) {
    let currentNode = queue[0];

    console.log(currentNode.val);

    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }

    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }

    // Remove the current node
    queue.shift();
  }
}

This example is based on Vaidehi Joshi's GitHub Gist.

Chapter Eight: Heap / Priority Queue

It’s now time to take a look at a data structure called a heap, which is a great way to implement an abstract data type called a priority queue. They're so interrelated that priority queues are sometimes referred to as heaps – because heaps are a very efficient way to create a priority queue.

Heap properties

The kind of heap we're interested in is also called a binary heap because it's just a binary tree that has specific properties.

One of them is that it must be a complete binary tree, meaning that all the levels must be filled, and all nodes in the last level should be as far left as possible.

For example, when it comes to shape, this is a complete binary tree:

But heaps must also be either a max heap or a min heap – all the parent nodes must be either greater than or equal to the values of their children (if it's a max heap) or less than or equal to the values of their children (if it's a min heap).

A max heap might look like this:

Note: A left child doesn't have to be less than the right child at all, as in a binary search tree. Also, we can always have duplicate values in a heap.

A min heap, on the other hand, has the values of parent nodes less than those of their children:

Note: When we have a max heap, the root node will have the maximum value. And, if we have a min heap instead, the root node will have the minimum value.

Heaps with arrays

We can create a heap using an array. Since the root node is the most interesting element with either a maximum or minimum value, it'll be the first element in our array, residing at the 0th index.

What's nice about using an array is that, given a parent node's index $i$, its left child will be at the index $2i + 1$, and its right child will be at the index $2i + 2$.

Given that, any child node's parent will be at the index $\lfloor{\frac{(n - 1)}{2}}\rfloor$.

Note: $\lfloor$ and $\rfloor$indicate the floor function.

One question we might ask at this moment is that why should we use an array at all?

The answer lies in the word queue of a priority queue. Since a queue is mainly concerned with the first element (following the FIFO principle), an array can be an ideal choice. In a priority queue, each element has a priority, and the value with the highest priority is dequeued first.

Inserting/removing elements

Let's take a look at how we can add an element to a heap.

We know that we have to add the new element to the bottom leftmost place, but once we do that, it might violate the max heap or the min heap property. Then, how can we avoid violating the heap-order property?

We'll heapify, of course!

Let's say that we want to add a node with the value 20:

So, heapify is the swapping of nodes until we know that the heap-order property is maintained.

A similar thing happens when we need to remove an element. But since we're mainly concerned with the maximum or the minimum element, we just need to remove the root node. So, how are we going to do that?

We start off by swapping the last element (the bottom leftmost one) with the root. Now we can easily remove the "root," which resides as a leaf node. But we still need to maintain the heap-order property, so we need to heapify again.

Heapsort

Even better thing is that if we have a heap, and continually heapify it, we can sort an array.

Let's build a max heap first:

function buildMaxHeap(arr: number[]) {
  /*
  Index of the last internal node 
  (i.e., the parent of the last leaf node, 
   or, the last non-leaf node).
  The last leaf node will reside at index arr.length - 1,
  so, we're getting its parent using the formula mentioned above.
  */
  let i = Math.floor((arr.length - 1) / 2);

  while (i >= 0) {
    heapify(arr, i, arr.length);
    i--;
  }

  return arr;
}

Then, the heapify function:

function heapify(arr: number[], i: number, maxLength: number) {
  while (i < maxLength) {
    let index = i;
    let leftChildIdx = 2 * i + 1;
    let rightChildIdx = leftChildIdx + 1;

    if (leftChildIdx < maxLength && arr[leftChildIdx] > arr[index]) {
      index = leftChildIdx;
    }

    if (rightChildIdx < maxLength && arr[rightChildIdx] > arr[index]) {
      index = rightChildIdx;
    }

    if (index === i) { return; }

    // Swap
    [arr[i], arr[index]] = [arr[index], arr[i]];

    i = index;
  }
}

With a given index i, we get its left and right children indices, and if the indices are within bounds, we check if they are out of order. In that case, we make the index the index of the child, and swap the two nodes. Then, we continue with that new index, assigning it to i.

Now, heapify is nice and all, but how can we actually use it for sorting?

function heapSort(arr: number[]) {
  buildMaxHeap(arr);

  let lastElementIdx = arr.length - 1;

  while (lastElementIdx > 0) {
    [arr[0], arr[lastElementIdx]] = [arr[lastElementIdx], arr[0]];

    heapify(arr, 0, lastElementIdx);
    lastElementIdx--;
  }

  return arr;
}

Note that our max heap [42, 19, 36, 17, 3, 25, 1, 2] won't change when used in the buildMaxHeap function, as it's already a max heap! But if it were to have 17 as the right child of 42, then 17 would have 25 as a child, which breaks the heap-order property. So, using buildMaxHeap with this broken version will correctly swap the 17 and 25, making it a max heap:

buildMaxHeap([42, 36, 17, 19, 3, 25, 1, 2]);

// -> [42, 36, 25, 19, 3, 17, 1, 2]

In heapSort, with our newly built max heap, we'll start with swapping the first and last nodes. Then, we'll keep heapifying until we get all the elements in their place. If we use it with our very own max heap, we can see that it returns the sorted array:

heapSort([42, 19, 36, 17, 3, 25, 1, 2]);
// -> [1, 2, 3, 17, 19, 25, 36, 42]

The examples are adapted from Vaidehi Joshi's article.

Time and space complexity

Heap sort, as a nice sorting algorithm it is, runs in $O(n \ log \ n)$ time.

In this example, building the max heap starts from the last non-leaf node and goes up to the root node, each time calling heapify. The heapify function has a time complexity of $O(log \ n)$ as we're working with a binary tree, and in the worst case, we get to do it for all the levels. Since we do it $n / 2$ times, overall, buildMaxHeap has $O(n \ log \ n)$ time complexity.

We're swapping the first and last elements, and heapifying as we go through each element, so this is also overall an $O(n \ log \ n)$ operation — which makes the time complexity of heapSort $O(n \ log \ n)$.

Note: Building the max heap can be improved to have $O(n)$ runtime.

Since there is no use of auxiliary space, the space complexity is constant, $O(1)$.

Chapter Nine: Backtracking

Let's start with admitting this one fact: backtracking is hard. Or rather, understanding it the first time is hard. Or, it's one of those concepts that you think you grasped it, only to realize later that you actually didn't.

We'll focus on one problem of finding the subsets of an array, but before that, let's imagine that we're walking along a path.

Then, we reach a fork. We pick one of the paths, and walk.

Then, we reach another fork in the path. We pick one of the paths again, and go on walking, then we reach a dead end. So, we backtrack to the last point we had a fork, then go through the other path that we didn't choose the first time.

Then we reach another dead end. So, we backtrack once more and realize that there are no other paths we can go from there. So we backtrack again, and explore the other path we didn't choose the first time we came to this point.

We reach yet another dead end, so we backtrack. We see that there are no more paths to explore, so we backtrack once more.

Now, we're at our starting point. There are no more paths left to explore, so we can stop walking.

It was a nice but tiring walk, and it went like this:

Now, let's take a look at a LeetCode problem.

Subsets

The description for Subsets says:

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

For example:

Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Or:

Input: nums = [0]
Output: [[], [0]]

Before diving into the solution code, let's take a look at how backtracking will work in this case. Let's call the nums array items instead:

For each item in items, we have initially two choices: to include the item, or not to include it.

For each level $n$ in this decision tree, we have the option to include the next item in items. We have $2^n$ possible subsets in total.

Let's simplify the example a bit, and say that items is now ['a', 'b'] (We'll ignore the problem specifics for now).

In this case, we can use backtracking like this:

function subsets(items: string[]) {
  let result: string[][] = [];
  let currentSubset: string[] = [];

  function backtrack(idx: number) {
    if (idx >= items.length) {
      result.push([...currentSubset]);
      return;
    }

    currentSubset.push(items[idx]);
    backtrack(idx + 1);

    currentSubset.pop();
    backtrack(idx + 1);
  }

  backtrack(0);

  return result;
}

console.log(subsets(['a', 'b']));
// -> [['a', 'b'], ['a'], ['b'], []]

Well, it looks simple at first glance, but what's going on?

One thing to notice is that we pop from the currentSubset, then call backtrack. In our example of walking, that's the part we go back to our previous point, and continue our walk.

In the first animation, we indicated a dead end with a cross mark, and in this case, a dead end is the base case we reach.

It might still be tough to understand, so let's add some helpful console.logs, and see the output:

function subsets(items: string[]) {
  let result: string[][] = [];
  let currentSubset: string[] = [];

  function backtrack(idx: number) {
    console.log(`======= this is backtrack(${arguments[0]}) =======`)
    if (idx >= items.length) {
      console.log(`idx is ${idx}, currentSubset is [${currentSubset}], adding it to result...`);
      result.push([...currentSubset]);
      console.log(`backtrack(${arguments[0]}) is returning...\n`)
      return;
    }

    currentSubset.push(items[idx]);
    console.log(`added ${items[idx]} to currentSubset, inside backtrack(${arguments[0]})`);
    console.log(`calling backtrack(${idx + 1})...`)
    backtrack(idx + 1);

    let item = currentSubset.pop();
    console.log(`popped ${item} from currentSubset, inside backtrack(${arguments[0]})`);
    console.log(`calling backtrack(${idx + 1})...`)
    backtrack(idx + 1);

    console.log(`******* done with backtrack(${arguments[0]}) *******\n`);
  }

  backtrack(0);

  return result;
}

console.log(subsets(['a', 'b']));

The output looks like this:

======= this is backtrack(0) =======
added a to currentSubset, inside backtrack(0)
calling backtrack(1)...
======= this is backtrack(1) =======
added b to currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [a,b], adding it to result...
backtrack(2) is returning...

popped b from currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [a], adding it to result...
backtrack(2) is returning...

******* done with backtrack(1) *******

popped a from currentSubset, inside backtrack(0)
calling backtrack(1)...
======= this is backtrack(1) =======
added b to currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [b], adding it to result...
backtrack(2) is returning...

popped b from currentSubset, inside backtrack(1)
calling backtrack(2)...
======= this is backtrack(2) =======
idx is 2, currentSubset is [], adding it to result...
backtrack(2) is returning...

******* done with backtrack(1) *******

******* done with backtrack(0) *******

[ [ 'a', 'b' ], [ 'a' ], [ 'b' ], [] ]

If you noticed, Add 'a'? and Go ahead? arrows on the first level are calls to backtrack(0).

Add 'b'? and Go ahead? arrows on the second level are calls to backtrack(1).

backtrack(2) calls are when we reach the "dead ends". In those cases, we add currentSubset to the result. We always reach the base case in a backtrack(2) call because it's only when the idx equals items.length.

Note: We modified the function in the above examples to work with strings, but in the actual solution we'll only deal with numbers, so in TypeScript, result and currentSubset will look like this:

let result: number[][] = [];
let currentSubset: number[] = [];

Also, the function parameter and return types are different:

function subsets(nums: number[]): number[][] { ... }

Otherwise, everything stays the same.

Time and space complexity

A subset is, in the worst case, length $n$ which is the length of our input. We'll have $2^n$ subsets and since we also use a spread operator in our example to copy currentSubset, the time complexity will be $O(n \cdot 2^n)$. The space complexity is – I think – $O(n \cdot 2^n)$ as well because of the recursive call stack (which is of depth n), and the space needed for result (which is in the worst case $2^n$).

Chapter Ten: Tries

The trie data structure gets its name from the word retrieval – and it's usually pronounced as "try," so that we don't get confused with another familiar and friendly data structure, "tree."

But a trie is still a tree (or tree-like) data structure whose nodes usually store individual letters. So, by traversing the nodes in a trie, we can retrieve strings.

Tries are useful for applications such as autocompletion and spellchecking – and the larger our trie is, the less work we have to do for inserting a new value.

Note: Using arrays is not very memory-efficient, but for now, we'll stick to the array implementation.

First, let's see what a trie looks like:

In this trie, we can retrieve the strings "sea" and "see" – but not "sew", for example.

There is a lot going on, but we can try to understand it piece by piece.

Let's look at a trie node.

We'll create a TrieNode class that has children, which is an array of length 26 (so that each index corresponds to a letter in the English alphabet), and a flag variable isEndOfWord to indicate whether that node represents the last character of a word:

class TrieNode {
  children: (TrieNode | null)[];
  isEndOfWord: boolean;

  constructor() {
    this.children = Array.from({ length: 26 }, () => null);
    this.isEndOfWord = false;
  }
}

We're initializing children with null values. As we add a character to our trie, the index that corresponds to that character will be filled.

Note: We're not storing the actual character itself in this implementation – it's implicit in the usage of indices.

In a trie, we start with an empty root node.

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }
  // ...
}

To insert a word, we're going to loop through each character, and initialize a new TrieNode to the corresponding index.

insert(word: string) {
  let currentNode = this.root;
  for (const char of word) {
    let idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
    if (currentNode.children[idx] === null) {
      currentNode.children[idx] = new TrieNode();
    }
    currentNode = currentNode.children[idx];
  }

  currentNode.isEndOfWord = true;
}

Once we reach the node that indicates the last character of the word we inserted, we also mark the isEndOfWord variable as true.

Note: word is going to be lowercase in these examples – otherwise, we have to convert it, such as:

word = word.toLowerCase();

For searching a word's existence in the trie, we'll do a similar thing. We'll look at the nodes for each character, and if we reach the last one that has isEndOfWord marked as true. That means we've found the word:

search(word: string) {
  let currentNode = this.root;
  for (const char of word) {
    let idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
    if (currentNode.children[idx] === null) {
      return false;
    }      
    currentNode = currentNode.children[idx];
  }

  return currentNode.isEndOfWord;
}

Note: If we find the word we're looking for, then it's called a search hit. Otherwise, we have a search miss and the word doesn't exist in our trie.

Removing a word is a bit more challenging. Let's say that we want to remove the word "see." But, there is also another word "sea," with the same prefix ('s' and 'e'). So, we should remove only the nodes that we're allowed to.

For this reason, we'll define a recursive function. Once we reach the last character of the word we want to remove, we'll back up and remove the characters we can remove:

const removeRecursively = (node: TrieNode | null, word: string, depth: number) => {
  if (node === null) {
    return null;
  }

  if (depth === word.length) {
    if (node.isEndOfWord) {
      node.isEndOfWord = false;
    }
    if (node.children.every(child => child === null)) {
      node = null;
    }

    return node;
  }

  let idx = word[depth].charCodeAt(0) - 'a'.charCodeAt(0);
  node.children[idx] = removeRecursively(node.children[idx], word, depth + 1);

  if (node.children.every(child => child === null) && !node.isEndOfWord) {
    node = null;
  }

  return node;
}

depth indicates the index of the word, or the depth of the trie we reach.

Once depth is equal to the word's length (one past the last character), we check if it's the end of the word. If that's the case, we'll mark it as false now, because that word won't exist from here on. Then, we can only mark the node as null if it doesn't have any children (in other words, if all of them are null). We'll apply this logic to each child node recursively until the word is removed as far as it can be removed.

Here is the final example implementation of a trie:

class TrieNode {
  children: (TrieNode | null)[];
  isEndOfWord: boolean;

  constructor() {
    this.children = Array.from({ length: 26 }, () => null);
    this.isEndOfWord = false;
  }
}

class Trie {
  root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  insert(word: string) {
    let currentNode = this.root;
    for (const char of word) {
      let idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
      if (currentNode.children[idx] === null) {
        currentNode.children[idx] = new TrieNode();
      }
      currentNode = currentNode.children[idx];
    }

    currentNode.isEndOfWord = true;
  }

  search(word: string) {
    let currentNode = this.root;
    for (const char of word) {
      let idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
      if (currentNode.children[idx] === null) {
        return false;
      }      
      currentNode = currentNode.children[idx];
    }

    return currentNode.isEndOfWord;
  }

  remove(word: string) {
    const removeRecursively = (node: TrieNode | null, word: string, depth: number) => {
      if (node === null) {
        return null;
      }

      if (depth === word.length) {
        if (node.isEndOfWord) {
          node.isEndOfWord = false;
        }
        if (node.children.every(child => child === null)) {
          node = null;
        }

        return node;
      }

      let idx = word[depth].charCodeAt(0) - 'a'.charCodeAt(0);
      node.children[idx] = removeRecursively(node.children[idx], word, depth + 1);

      if (node.children.every(child => child === null) && !node.isEndOfWord) {
        node = null;
      }

      return node;
    }

    removeRecursively(this.root, word, 0);
  }
}

let t = new Trie();

t.insert('sea');
t.insert('see');

console.log(t.search('sea')); // true
console.log(t.search('see')); // true

console.log(t.search('hey')); // false
console.log(t.search('sew')); // false

t.remove('see');

console.log(t.search('see')); // false 
console.log(t.search('sea')); // true

Time and space complexity

The time complexity of creating a trie is going to be $O(m * n)$ where $m$ is the longest word and $n$ is the total number of words. Inserting, searching, and deleting a word is $O(a * n)$ where $a$ is the length of the word and $n$ is the total number of words.

When it comes to space complexity, in the worst case, each node can have children for all the characters in the alphabet we're representing. But, the size of the alphabet is constant, so the growth of storage needs will be proportionate to the number of nodes we have, which is $O(n)$ where $n$ is the number of nodes.

Chapter Eleven: Graphs

A graph is probably the data structure that everyone is familiar with, regardless of their profession or interests.

Graph theory is a very broad topic, but we'll simply look at some of the main ingredients of what makes a graph and how to represent it, as well as basic graph traversals.

In a graph, there are two main components: vertices (or nodes) and edges that connect those vertices.

Note: Here, we're going to use "vertex" and "node" interchangeably. The terms "adjacent vertices" and "neighbors" are used interchangeably as well.

A graph can be directed or undirected. With a directed edge, we have an origin and a destination vertex. On the other hand, an undirected edge is bidirectional, origin and destination are not fixed.

Note: There might also be mixed graphs that have both directed and undirected edges.

A graph can also be weighted or unweighted, each edge can have different weights, usually representing the cost of going from one vertex to the other.

We can define a graph like this:

$$G = (V, \ E)$$

$V$ is a set of vertices, and $E$ is a set of edges.

For example, if we have a directed graph like this:

Then, we have the vertices:

$$V = \{A, \ B, \ C, \ D\}$$

And, the edges are:

$$E = \{(A, \ B), \ (A, \ C), \ (C, \ B), \ (C, \ D)\, \ (D, \ C)\}$$

If we have an undirected graph such as this one:

We have the same vertices:

$$V = \{A, \ B, \ C, \ D\}$$

But our edges can look like this:

$$E = \{\{B, \ A\}, \{A, \ C\}, \{C, \ B\}, \{D, \ C\}\}$$

Note: We use parentheses when it comes to directed edges, but curly braces with undirected edges as there is no direction from one vertex to the other.

When two vertices share an edge, they are adjacent to each other. The degree of a vertex is the number of adjacent vertices to it. We can also define the degree as the number of edges coming out of the vertex. For example, in the above image, the vertex A has a degree of 2.

A simple path is the one that we don't repeat any vertices while traversing the graph.

An example might look like this:

A cycle is a simple path, except that we end up at the vertex we started with:

Representing graphs

When it comes to representing graphs, there are several ways to do it, and we'll look at three of them: an edge list, an adjacency matrix, and an adjacency list.

Edge List

We can simply put all the edges in an array:

[ [A, B], [A, C], [B, C], [C, D] ]

But to find an edge in an edge list, we'll have to iterate through them, so it will have $O(E)$ time complexity, where in the worst case, we'll search the whole list to find an edge. Similarly, it needs $O(E)$ amount of space to represent all the edges.

Adjacency Matrix

The adjacency matrix for our example might look like this:

$$\left\lceil\begin{matrix}& A & B & C & D \\A & 0 & 1 & 1 & 0 \\B & 1 & 0 & 1 & 0 \\C & 1 & 1 & 0 & 1 \\D & 0 & 0 & 1 & 0\end{matrix}\right\rceil$$

Each row is for a vertex, and the matching column shows the relationship between those vertices. For example, the vertex A doesn't have an edge pointing to D, so the cell that matches A and D is 0. On the other hand, A is connected to B and C, so those cells have the value 1.

Note: If the graph is weighted, we can simply put the weight instead of 1, and when there is no edge, the value can stay 0.

An adjacency matrix will have 0s in the "main diagonal," showing that there are no self-loops.

Let's try implementing it in TypeScript.

We'll start with a minimal graph vertex:

class GraphVertex {
  value: string | number;

  constructor(value: string | number) {
    this.value = value;
  }
}

Now we can define our graph. We'll make it really simple with three properties to hold: matrix to represent the graph as an adjacency matrix, vertices to hold vertices, and isDirected to indicate whether our graph is directed:

class Graph {
  matrix: number[][];
  vertices: GraphVertex[];
  isDirected: boolean;

  constructor(vertices: GraphVertex[], isDirected = true) {
    this.vertices = vertices;
    this.isDirected = isDirected;
    // ...
  }

  // ...
}

Initializing our adjacency matrix might look like this:

this.matrix = Array.from({ length: vertices.length }, () => {
  return Array.from({ length: vertices.length }, () => 0)
});

We'll have an array with the length of vertices. Each item in the array is an array with the length of vertices as well, but filled with zeroes.

In our example with four vertices, the initial adjacency matrix looks like this:

[ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ]

Then, adding an edge is just marking the corresponding value as 1, so that we can represent a connection between two vertices:

this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] = 1;

Note: This implementation assumes that all vertices are distinct.

If we have an undirected graph, we can have it both ways:

if (!this.isDirected) {
  this.matrix[this.vertices.indexOf(v2)][this.vertices.indexOf(v1)] = 1;
}

Removing an edge, in this case, will be just resetting the value to 0:

this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] = 0;

And, checking for the existence of an edge is simply checking whether the corresponding value is 0 or not:

this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] !== 0;

And, here is the whole example with additional methods for adding and removing an edge, checking if there is an edge between two vertices, and checking if a specific vertex is in the graph:

class Graph {
  matrix: number[][];
  vertices: GraphVertex[];
  isDirected: boolean;

  constructor(vertices: GraphVertex[], isDirected = true) {
    this.vertices = vertices;
    this.matrix = Array.from({ length: vertices.length }, () => {
      return Array.from({ length: vertices.length }, () => 0)
    });
    this.isDirected = isDirected;
  }

  addEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] = 1;

    if (!this.isDirected) {
      this.matrix[this.vertices.indexOf(v2)][this.vertices.indexOf(v1)] = 1;
    }
  }

  /* 
  For a weighted graph:

  addEdge(v1: GraphVertex, v2: GraphVertex, weight: number) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] = weight;
    if (!this.isDirected) {
      this.matrix[this.vertices.indexOf(v2)][this.vertices.indexOf(v1)] = weight;
    }
  }
  */

  removeEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] = 0;

    if (!this.isDirected) {
      this.matrix[this.vertices.indexOf(v2)][this.vertices.indexOf(v1)] = 0;
    }
  }

  hasEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    return this.matrix[this.vertices.indexOf(v1)][this.vertices.indexOf(v2)] !== 0;
  }

  getAdjacencyMatrix() {
    return this.matrix;
  }

  _checkVertexIsInGraph(v: GraphVertex) {
    if (!this.vertices.includes(v)) {
      throw new Error('Vertex doesn\'t exist');
    }
  }
}


let a = new GraphVertex('A');
let b = new GraphVertex('B');
let c = new GraphVertex('C');
let d = new GraphVertex('D');

let graph = new Graph([a, b, c, d], false);

graph.addEdge(a, b);
graph.addEdge(a, c);
graph.addEdge(b, c);
graph.addEdge(c, d);

console.log(graph.getAdjacencyMatrix());
// -> [ [0, 1, 1, 0], [1, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0] ]

Operations on an adjacency matrix have $O(1)$ time complexity. But our storage needs will be $O(V^2)$ where $V$ is the number of vertices.

Adjacency List

In an adjacency list, usually a hashmap or an array of linked lists is used. For example:

let graph = {
  'A': ['B', 'C'],
  'B': ['A', 'C'],
  'C': ['A', 'B', 'D'],
  'D': ['C']
}

Let's see how we can modify our code above to use an adjacency list instead.

Instead of having a matrix which is an array of arrays, we can have a Map that maps the vertices to an array of their neighbors.

We can initialize it as a map that has the vertices as keys, each of which has a value of an empty array for now:

this.list = new Map();
for (const v of vertices) {
  this.list.set(v, []);
}

Adding an edge will be just pushing to the array of corresponding vertex:

this.list.get(v1)!.push(v2);

If our graph is undirected, we can do it both ways here as well:

if (!this.isDirected) {
  this.list.get(v2)!.push(v1);
}

Removing an edge will be deleting that vertex from the array:

this.list.set(v1, this.list.get(v1)!.filter(v => v !== v2));

Checking if an edge exists is just checking the existence of that vertex in the array:

this.list.get(v1)!.includes(v2);

Note: We're using a non-null assertion operator as we’re using TypeScript in these examples. As we'll see below, we first check if the vertex is in the graph. And since we're adding all the vertices in the graph as keys to this.list, we're sure that getting that vertex from the list is not undefined. But TypeScript will warn us because if a key is not found in a Map object, it could potentially return undefined.

Here is our graph:

class Graph {
  list: Map;
  vertices: GraphVertex[];
  isDirected: boolean;

  constructor(vertices: GraphVertex[], isDirected = true) {
    this.vertices = vertices;
    this.list = new Map();
    for (const v of vertices) {
      this.list.set(v, []);
    }
    this.isDirected = isDirected;
  }

  addEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    this.list.get(v1)!.push(v2);

    if (!this.isDirected) {
      this.list.get(v2)!.push(v1);
    }
  }

  removeEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    this.list.set(v1, this.list.get(v1)!.filter(v => v !== v2));

    if (!this.isDirected) {
      this.list.set(v2, this.list.get(v2)!.filter(v => v !== v1));
    }
  }

  hasEdge(v1: GraphVertex, v2: GraphVertex) {
    this._checkVertexIsInGraph(v1);
    this._checkVertexIsInGraph(v2);

    return this.list.get(v1)!.includes(v2);
  }

  getAdjacencyList() {
    return this.list;
  }

  _checkVertexIsInGraph(v: GraphVertex) {
    if (!this.vertices.includes(v)) {
      throw new Error('Vertex doesn\'t exist');
    }
  }
}


let a = new GraphVertex('A');
let b = new GraphVertex('B');
let c = new GraphVertex('C');
let d = new GraphVertex('D');

let graph = new Graph([a, b, c, d], false);

graph.addEdge(a, b);
graph.addEdge(a, c);
graph.addEdge(b, c);
graph.addEdge(c, d);

console.log(graph.getAdjacencyList());

/* Output:

Map (4) {
  GraphVertex: { "value": "A" } => [
    GraphVertex: { "value": "B" }, 
    GraphVertex: { "value": "C" }
  ], 
  GraphVertex: { "value": "B" } => [
    GraphVertex: { "value": "A" }, 
    GraphVertex: { "value": "C" }
  ], 
  GraphVertex: { "value": "C" } => [
    GraphVertex: { "value": "A" }, 
    GraphVertex: { "value": "B" }, 
    GraphVertex: { "value": "D" }
  ], 
  GraphVertex: { "value": "D" } => [
    GraphVertex: { "value": "C" }
  ]
} 

*/

Getting the neighbors of a vertex is $O(1)$ because we're just looking up a key in a map. But finding a particular edge can be $O(d)$ where $d$ is the number of degrees of the vertex, because we might need to traverse all the neighbors to find it. And, it could be $V - 1$ where $V$ is the number of vertices in the graph. It's the case when that vertex has all the other vertices as its neighbors.

The space complexity can be $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges.

Traversals

Continuing with the adjacency list representation, let's now take a look at two (very familiar) ways to traverse a graph: breadth-first search and depth-first search.

But first, we'll modify our graph a little bit. We'll add a new vertex 'E' and update some edges:

let a = new GraphVertex('A');
let b = new GraphVertex('B');
let c = new GraphVertex('C');
let d = new GraphVertex('D');
let e = new GraphVertex('E');


let graph = new Graph([a, b, c, d, e], false);

graph.addEdge(a, b);
graph.addEdge(a, c);
graph.addEdge(b, d);
graph.addEdge(c, e);

The important idea to remember is that there is no hierarchy of vertices, so we don't have a root node.

For a breadth-first or depth-first search, we can use an arbitrary node as a starting point.

Breadth-First Search

With our new graph, a breadth-first search traversal looks like this:

When it comes to breadth-first search, usually a queue is used, and the idea is simple: given a current node, we'll add the adjacent nodes first, marking them as visited as we go.

Inside the Graph class, we can implement a bfs method that does just that:

bfs(startNode: GraphVertex) {
  const visited = new Set();
  const queue = [startNode];
  visited.add(startNode);

  while (queue.length > 0) {
    const currentNode = queue.shift();
    // console.log(currentNode);
    this.list.get(currentNode as GraphVertex)!.forEach((node) => {
      if (!visited.has(node)) {
        visited.add(node);
        queue.push(node);
      }
    });
  }
}

If we call the bfs method with a as the starting vertex (graph.bfs(a)), and log currentNode to console each time we go, it's as we expected:

GraphVertex { value: 'A' }
GraphVertex { value: 'B' }
GraphVertex { value: 'C' }
GraphVertex { value: 'D' }
GraphVertex { value: 'E' }

With the adjacency list, using a BFS has $O(V + E)$ time complexity (sum of the vertices and edges) as we're traversing the whole graph.

Depth-First Search

With the same modified graph, a depth-first search looks like this:

With depth-first search there is usually recursion involved as we're traversing through a path until we have visited all the nodes in that path. Once we hit a dead end, we'll backtrack and continue exploring until we have visited all the vertices in the graph.

Again, inside the Graph class, we can add a dfs method:

dfs(startNode: GraphVertex, visited = new Set()) {
  visited.add(startNode);
  // console.log(startNode);
  this.list.get(startNode)!.forEach((node) => {
    if (!visited.has(node)) {
      this.dfs(node, visited);
    }
  });
}

Starting with a node, we check how deep we can go from there. Once we reach a dead end (when the dfs inside forEach returns), we continue checking other neighbors (with forEach) until none is left. We essentially do the same thing until all the vertices are visited.

Logging the output matches our expectation:

GraphVertex { value: 'A' }
GraphVertex { value: 'B' }
GraphVertex { value: 'D' }
GraphVertex { value: 'C' }
GraphVertex { value: 'E' }

The time complexity for a depth-first search traversal of a graph is the similar to BFS, $O(V + E)$.

Chapter Twelve: Dynamic Programming

Dynamic programming (DP) is one of those concepts that is a bit intimidating when you hear it for the first time. But the crux of it is simply breaking problems down into smaller parts and solving them. It’s also about storing those solutions so that we don't have to compute them again.

Breaking problems down into subproblems is nothing new – that's pretty much what problem-solving is all about. What dynamic programming is also specifically concerned with are overlapping subproblems that are repeating – we want to calculate solutions to those subproblems so that we won't be calculating them again each time. Put another way, we want to remember the past so that we won't be condemned to repeat it.

For example, calculating 1 + 1 + 1 + 1 + 1 is very easy if we have already calculated 1 + 1 + 1 + 1. We can just remember the previous solution, and use it:

Calculating the Fibonacci sequence is one of the well-known examples when it comes to dynamic programming. Because we have to calculate the same functions each time for a new number, it lends itself to DP very well.

For example, to calculate fib(4) we need to calculate fib(3) and fib(2). But calculating fib(3) also involves calculating fib(2), so we'll be doing the same calculation, again.

A classic, good old recursive Fibonacci function might look like this:

function fib(n: number): number {
  if (n === 0 || n === 1) {
    return n;
  }

  return fib(n - 1) + fib(n - 2);
}

Though the issue we have just mentioned remains: we'll keep calculating the same values:

But, we want to do better.

Memoization is remembering the problems we have solved before so that we don't have to solve them again and waste our time. We can reuse the solution to the subproblem we've already memoized. So, we can keep a cache to store those solutions and use them:

function fib(n: number, cache: Map<number, number>): number {
  if (cache.has(n)) {
    return cache.get(n)!;
  }

  if (n === 0 || n === 1) {
    return n;
  }

  const result = fib(n - 1, cache) + fib(n - 2, cache);
  cache.set(n, result);

  return result;
}

For example, we can initially pass an empty Map as the argument for cache, and print the first 15 Fibonacci numbers:

let m = new Map<number, number>();

for (let i = 0; i < 15; i++) {
  console.log(fib(i, m));
}

/*
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55 
  89
  144
  233
  377 
 */

There are two different approaches with dynamic programming: top-down and bottom-up.

Top-down is like what it sounds: starting with a large problem, breaking it down to smaller components, memoizing them. It's what we just did with the fib example.

Bottom-up is also like what it sounds: starting with the smallest subproblem, finding out a solution, and working our way up to the larger problem itself. It also has an advantage: with the bottom-up approach, we don't need to store every previous value – we can only keep the two elements at the bottom so that we can use them to build up to our target.

With the bottom-up approach, our fib function can look like this:

function fib(n: number) {
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

Just note that we are keeping an array whose size will grow linearly as the input increases. So, we can do better with constant space complexity, not using an array at all:

function fib(n: number) {
  if (n === 0 || n === 1) {
    return n;
  }

  let a = 0;
  let b = 1;

  for (let i = 2; i <= n; i++) {
    let tmp = a + b;
    a = b;
    b = tmp;
  }

  return b;
}

Time and space complexity

The time complexities for both the top-down and bottom-up approaches in the Fibonacci example are $O(n)$ as we solve each subproblem, each of which is of constant time.

Note: The time complexity of the recursive Fibonacci function that doesn't use DP is exponential (in fact, $O(\phi^{n})$ – yes the golden ratio as its base).

But when it comes to space complexity, the bottom-up approach (the second version) is $O(1)$.

Note: The first version we've used for the bottom-up approach has $O(n)$ time complexity as we store the values in an array.

The top-down approach has $O(n)$ space complexity because we store a Map whose size will grow linearly as n increases.

Chapter Thirteen: Intervals

An interval simply has a start and an end. The easiest way to think about intervals is as time frames.

With intervals, the usual concern is whether they overlap or not.

For example, if we have an interval [1, 3] and another [2, 5], they are clearly overlapping, so they can be merged together to create a new interval [1, 5]:

In order for two intervals not to overlap:

the start of one should be strictly larger than the end of the other

newInterval[0] > interval[1]

Or:

the end of the one should be strictly smaller than the start of the other

newInterval[1] < interval[0]

If both of these are false, they are overlapping.

If they are overlapping, the new (merged) interval will have the minimum value from both intervals as its start, and the maximum as its end:

[
  min(newInterval[0], interval[0]),
  max(newInterval[1], interval[1])
]

Chapter Fourteen: Bit Manipulation

A bitwise operation operates on a bit string, a bit array, or a binary numeral (considered as a bit string) at the level of its individual bits.

Let's first represent a number in binary (base 2). We can use toString method on a number, and specify the radix:

const n = 17;

console.log(n.toString(2)); // 10001

We can also parse an integer giving it a base:

console.log(parseInt(10001, 2)); // 17

Note: We can also represent a binary number with the prefix 0b:

console.log(0b10001); // 17
console.log(0b101); // 5

For example, these are the same number:

0b1 === 0b00000001 // true

All bitwise operations are performed on 32-bit binary numbers in JavaScript. That is, before a bitwise operation is performed, JavaScript converts numbers to 32-bit signed integers.

So, for example, 17 won't be simply 10001 but 00000000 00000000 00000000 00010001.

After the bitwise operation is performed, the result is converted back to 64-bit JavaScript numbers.

Bitwise operators

AND (`&`)

If two bits are 1, the result is 1, otherwise 0.

The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

OR (`|`)

If either of the bits is 1, the result is 1, otherwise 0.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

XOR (`^`)

If the bits are different (one is 1 and the other is 0), the result is 1, otherwise 0.

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

NOT (`~`)

Flips the bits (1 becomes 0, 0 becomes 1).

const n = 17;

const result = ~n; // -18

Note: Bitwise NOTing any 32-bit integer x yields -(x + 1).

If we use a helper function to see the binary representations, it is as we expected:

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

The leftmost bit indicates the signal – whether the number is negative or positive.

Remember that we said JavaScript uses 32-bit signed integers for bitwise operations. The leftmost bit is 1 for negative numbers and 0 for positive numbers. Also, the operator operates on the operands' bit representations in two's complement. The operator is applied to each bit, and the result is constructed bitwise.

Note: Two's complement allows us to get a number with an inverse signal. One way to do it is to invert the bits of the number in the positive representation and add 1 to it:

function twosComplement(n) {
  return ~n + 0b1;
}

Left shift (zero fill) (`<<`)

Shifts the given number of bits to the left, adding zero bits shifted in from the right.

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

Note that the 32nd bit (the leftmost one) is discarded.

Right shift (sign preserving) (`>>`)

Shifts the given number of bits to the right, preserving the sign when adding bits from the left.

const n = 17;
const result = n >> 1; // 8


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >> 1; // -9

console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createBinaryString(-9));
// -> 11111111 11111111 11111111 11110111

Right shift (unsigned) (`>>>`)

Shifts the given number of bits to the right, adding 0s when adding bits in from the left, no matter what the sign is.

const n = 17;
const result = n >>> 1; // 8


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000

const n = -17;
const result = n >>> 1; // 2147483639

console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111

console.log(createBinaryString(2147483639));
// -> 01111111 11111111 11111111 11110111

Getting a bit

To get a specific bit, we first need to create a bitmask. We can do this by shifting 1 to the left by the index of the bit we want to get. The result is the AND of the binary number and the bitmask.

But using JavaScript, we can also do an unsigned right shift by the index to put the bit in the first place (so that we don't get the actual value that is in that position, but whether it is a 1 or a 0):

function getBit(number, idx) {
  const bitMask = 1 << idx;
  const result = number & bitMask;

  return result >>> idx;
}

For example, let's try 13, which is 1101 in binary:

const binaryNumber = 0b1101;

console.log('Bit at position 0:', getBit(binaryNumber, 0));
console.log('Bit at position 1:', getBit(binaryNumber, 1));
console.log('Bit at position 2:', getBit(binaryNumber, 2));
console.log('Bit at position 3:', getBit(binaryNumber, 3));

/*
Output:

Bit at position 0: 1
Bit at position 1: 0
Bit at position 2: 1
Bit at position 3: 1
*/

Setting a bit

If we want to turn a bit to 1 (in other words, to "set a bit"), we can do a similar thing.

First, we can create a bitmask again by shifting 1 to the left by the index of the bit we want to set to 1. The result is the OR of the number and the bitmask:

function setBit(number, idx) {
  const bitMask = 1 << idx;
  return number | bitMask;    
}

Remember that in our example 13 was 1101 in binary, let's say we want to set the 0 at index 1:

const binaryNumber = 0b1101;
const newBinaryNumber = setBit(binaryNumber, 1);

console.log(createBinaryString(newBinaryNumber));
// -> 00000000 00000000 00000000 00001111

console.log('Bit at position 1:', getBit(newBinaryNumber, 1));
// -> Bit at position 1: 1

Conclusion

With some detours here and there, we took a look at fourteen (or fifteen, if you count our interlude) different concepts, from arrays and hashing to bit manipulation.

Although I have to say that eventually, with time, it’s easy to forget all that we learned. But, that's not a problem in itself, because as you might have realized, if there is one idea that should stick with you with this handbook, it’s that problems are best solved when they are broken into smaller parts. And, as with anything else, writing or talking to yourself (see duck debugging) works miracles.

Now, it's time to take a deep breath.

It was a delightful adventure to explore data structures and algorithms, and hopefully you found some value in it.

Have a beautiful journey ahead, and until then, happy coding.

Resources & Credits

This handbook was mainly inspired by the amazing BaseCS series by Vaidehi Joshi, which is an incredible resource for learning basic computer science concepts.

The visualization idea was inspired by Lydia Hallie's JavaScript Visualized series.

Of course, you can also check out NeetCode's courses which can be incredibly helpful for a serious study.

There are many other resources to check out if you want to go further, here are some of the ones I used in our exploration:

How to Build a Visualization for Leetcode's Two Sum Problem – HTML, CSS, & JavaScript Project

Jessica Wilkins — Tue, 21 Nov 2023 21:08:22 +0000

With the current state of the job market, there are a lot of people grinding out LeetCode as a way to prepare for technical interviews.

But sometimes it would be nice if there were a visualization showing the algorithms behind these problems.

In this tutorial, we will build out a visualization showing a couple of approaches to a popular LeetCode problem called Two Sum. We will use vanilla HTML, CSS, and JavaScript to build this project out.

Prerequisites
Project Setup
How to Solve LeetCode's Two Sum Problem
Overview for the Two Sum Visualization
Adding the Brute Force Visualization
How to Disable the bruteForceSolutionBtn When the Animation is in Progress
Adding the Map Solution Visualization
- Creating the const Variables
- Creating the optimalApproach Async Function
How to Reset the Table Output for the Map Solution
Final Solution Code and Live Example
Conclusion

Prerequisites

This tutorial assumes that you have basic knowledge of HTML, CSS and JavaScript. If you haven't gone through a beginner course in any of those languages, then I would suggest starting with these resources:

This tutorial also assumes that you have some basic knowledge of how to work with a code editor or IDE. If not, then I would suggest looking into these resources:

Project Setup

You are free to build out this project in either your local code editor of choice, or through an online IDE or editor like CodePen, CodeSandbox, or Replit.

This project will consist of three files: index.html, index.js, and styles.css. Since this project is going to mainly focus on JavaScript, I have supplied all of the HTML and CSS in this GitHub repo here.

You are free to fork and clone the repository, or you can copy the code found in the HTML and CSS files and add it to your project.

Once you get your project environment setup, then you should start the local server and see this result on the screen:

Visualization styles for Leetcode's Two Sum problem

How to Solve LeetCode's Two Sum problem

Before we can build out the visualization for this problem, we need to first understand and solve the problem.

Description

For this problem, you will be given a list of numbers in any order and a target number. The goal is to find the pair of numbers that adds up to the target and return an array of indices for that pair of numbers.

In this example, we have the following list and target number:

[2,7,11,15]
target: 9

The numbers 2 and 7 equal 9 so we would return [0,1] because that represents the indices for where the pair of numbers can be found in the array.

For this problem, you can assume there will be at least two numbers or more in the array and there will only be one possible solution.

So for example you can not have this input here which produces no solution because there are no two numbers in that list that add up to the target.

[1,2,3,4,5]
target: 55

You will also not get an input with multiple solutions. The following input has two answers of [0,1] and [1,2] which goes against the rules of this problem.

[3,3,3]
target: 6

Brute Force Approach

The more intuitive approach would be to start at the beginning of the list of numbers and compare each possible pair of numbers until we find the pair that adds up to the target.

Let's take a look at this example here:

[11, 15, 2, 7]
target:9

We can start with the first number in the list (11) and check each possible pair and see if it adds up to the target number (9).

11 + 15 = 9? NO
11 + 2 = 9? NO
11 + 7 = 9? NO

Since none of those pairs equal the target (9), then we move to the second number in the list (15) and check all possible pairs. There is no need to check 11+15 because we already checked that earlier.

15 + 2 = 9? NO
15 + 7 = 9? NO

Since none of those pairs equal the target (9), then we move to the third number in the list (2) and check all possible pairs.

2 + 7 = 9? YES!!!

Now, we have found the pair that adds up to the target we would return [2,3] because that represents the indices for where the pair of numbers can be found in the array.

Brute Force JavaScript Solution and Time Complexity

This solution uses a nested for loop which would be an O(n²) time complexity. The outer loop is used to get the current number in the list and the inner loop is used to check if the sum of the current number and other numbers in the list add up to the target.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var twoSum = function (nums, target) {
  if (nums.length === 2) return [0, 1];

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      if (currentNum + nums[j] === target) return [i, j];
    }
  }
};

Note: I have added an additional check in my solution to check if the input array has only two numbers. In that case, we immediately return [0,1] because those are the only possible indices for that test case.

 if (nums.length === 2) return [0, 1];

So far, our input arrays have been very small. But if we had an input array of 100, 500, or 1000+ numbers, then it could take a while to find the pair that adds up to the target.

In the next section, we are going to take a look at a solution that utilizes JavaScript's Map object and runs in linear time O(n).

Map Approach and Solution

In the brute force approach, we started at the beginning of the array and compared all possible pairs of numbers until we found the pair that added up to the target. But in this approach we can use JavaScript's Map object and one for loop to find that pair.

JavaScript's Map object is a collection of key-value pairs that allows for quick lookups and has built in methods like set(), get() and has().

Let's work with the same example from earlier:

[11, 15, 2, 7]
target:9

We can start looping through the array and look at the current number in the list which would be nums[i]. We also want to create a new map object which will be empty to start.

const map = new Map();

for(let i=0; i


Inside our loop, we need to calculate the difference which will be the target minus the current number.
    const map = new Map();

    for(let i=0; iconst difference = target - nums[i]
    }

Since we know there can only be two numbers that add up to the target, we can check if the difference is in the map. If so, we have found the pair and can return the indices. Otherwise, we can add that current number to the map along with its index.
    const map = new Map();

    for(let i=0; i < nums.length; i++) {
        const difference = target - nums[i]

        if(map.has(difference)) {
            return [map.get(difference), i]
        } else {
            map.set(nums[i], i)
        }
    }

In the following code, the has() method is used to check if the following key is in the map object. This method will return a boolean of true or false. 
map.has(difference)

The get() method is used to return that element from the map. 
 if(map.has(difference)) {
   return [map.get(difference), i]
 }

The set() method will add or update an entry in the map with a key and value.
else {
  map.set(nums[i], i)
}

Here is the complete code for this approach:
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    if(nums.length === 2) return [0,1]

    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const difference = target - nums[i]

        if (map.has(difference)) {
            return [map.get(difference), i]
        } else {
            map.set(nums[i], i)
        }
    }

};

Time Complexity for the Map Solution
This solution would be a linear time complexity O(n). Since we are only using one loop instead of two, we have improved on the time complexity and no longer running in quadratic time O(n²) like we were earlier.
In the next few sections, we are going to start to build out the visualizations for each of these approaches. 
Overview for the Two Sum Visualization
The goal of this project is to create visualizations for both the map and brute force solutions. 
For the brute force solution, we will show what is it like to walk through each pair of numbers until we find the pair that adds up to the target.

Brute Force approach visualization
For the map solution, we will show the map being built out and checking for the pair that adds up to the target. 

Map solution visualization
Adding the Brute Force Visualization
Creating the const and let Variables
We first need to create const variables and assign them the result of accessing the HTML elements responsible for displaying the brute force solution button and output.
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");
const bruteForceNumbersOutput = document.querySelector(
  "#brute-force-output > .numbers-array"
);
const bruteForceTextOutput = document.querySelector(
  "#brute-force-output > .result-text"
);

The next step is to create const variables for the test case array and target that will be used for both visualizations. 
const testCaseArray = [11, 15, 2, 7];
const target = 9;

Then, we need to create the let variables that will represent the current number we are looking at in the outer loop and the compliment number we are looking at in the inner loop. 
let currentNum;
let currentCompliment;

Creating the getClassName Function
In our visualization we want to show the user the current pair of numbers we are checking by applying different colored borders around them. The current number will have a green border around it and the current compliment number will have a blue border around it.

In order to dynamically update these styles over time, we need to create a function that will be responsible for adding the appropriate classes to the current number and it compliment. 
First, start by creating a new getClassName function that takes in a num parameter.
const getClassName = (num) => {

};

Inside that function, create a switch statement that has the num for the expression we are checking for. 
const getClassName = (num) => {
  switch (num) {

  }
};

The first case should check for currentNum and return a string for the current-num class.
const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
  }
};

The second case should check for the currentCompliment and return a string for the compliment-num class. 
const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
    case currentCompliment:
      return "class='compliment-num'";
  }
};

For the default case, it should return an empty string because we are not going to apply any classes for that element. 
const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
    case currentCompliment:
      return "class='compliment-num'";
    default:
      return "";
  }
};

Creating the bruteForceApproach Function
This function will be responsible for executing the brute force solution and displaying the visualization on the page. 
We first need to create the bruteForceApproach function which will be an async function. 
const bruteForceApproach = async () => {

};

Then, we need to add the outer loop for our test case array.
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {

  }
};

Inside the for loop, update the currentNum to assign it the value of the current number we are looking at in the test case array.
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
  }
};

Next, create the inner for loop.
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {

    }
  }
};

Inside the inner for loop, update the currentCompliment number and assign it the value of testCaseArray[j]. This is meant to represent each number to the right of the current number. 
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
    }
  }
};

Next, we need to add a setTimeout which will delay the visual changes made to the markup by one second. This is what is going to help create the animated effect of showing the different pairs of numbers. 
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));
    }
  }
};

Then we need to update the HTML for the output. Start by assigning the test case array to bruteForceNumbersOutput.innerHTML.
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray;
    }
  }
};

Then, we want to use the map method on the array, to create a new array of span elements which represents each number in the array along with the styles. We also need to chain the join method on that to remove the commas that the map method adds when the new array is created.
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray
        .map(
          (num, index) =>
            `
            ${getClassName(num)}>
            ${testCaseArray[index]}
            
          `
        )
        .join("");
    }
  }
};

If we don't find a pair that adds up to the target, then we want to display a message to the user. Update the text content for the bruteForceTextOutput and assign it the following message:
const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray
        .map(
          (num, index) =>
            `
            ${getClassName(num)}>
            ${testCaseArray[index]}
            
          `
        )
        .join("");

      bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`;
    }
  }
};

The last piece is to add a condition that checks if we found the pair of numbers that adds up to the target. If so, then we can display that final indices array and return from the function. 
  if (currentNum + currentCompliment === target) {
      bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`;
      return;
  }

To test out the brute force visualization, we will need to add an event listener to the bruteForceSolutionBtn. The event listener should listen for a "click" event and should reference the bruteForceApproach function.
bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);

This should be your complete code so far:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");
const bruteForceNumbersOutput = document.querySelector(
  "#brute-force-output > .numbers-array"
);
const bruteForceTextOutput = document.querySelector(
  "#brute-force-output > .result-text"
);
const testCaseArray = [11, 15, 2, 7];
const target = 9;
let currentNum;
let currentCompliment;

const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
    case currentCompliment:
      return "class='compliment-num'";
    default:
      return "";
  }
};

const bruteForceApproach = async () => {
  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray
        .map(
          (num, index) =>
            `
            ${getClassName(num)}>
            ${testCaseArray[index]}
            
          `
        )
        .join("");

      bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`;

      if (currentNum + currentCompliment === target) {
        bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`;
        return;
      }
    }
  }
};

bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);

Try out your visualization by clicking on the "Show Visualization" button for the Brute force approach. 

Result of clicking the "show visualization" button for brute force approach
How to Disable the bruteForceSolutionBtn When the Animation is in Progress
If you try to click on the bruteForceSolutionBtn multiple times in a row, you will see glitches in the animation. To fix that, we should disable the button when the animation is running and then re-enable it when the animation is complete. 
Inside the bruteForceApproach function, set the disabled attribute for the bruteForceSolutionBtn. 
const bruteForceApproach = async () => {
  bruteForceSolutionBtn.setAttribute("disabled", "");

Inside the if statement, remove the disabled attribute for the bruteForceSolutionBtn.
   if (currentNum + currentCompliment === target) {
        bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`;
        bruteForceSolutionBtn.removeAttribute("disabled");
        return;
   }

Here is the complete code with the fix:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");
const bruteForceNumbersOutput = document.querySelector(
  "#brute-force-output > .numbers-array"
);
const bruteForceTextOutput = document.querySelector(
  "#brute-force-output > .result-text"
);
const testCaseArray = [11, 15, 2, 7];
const target = 9;
let currentNum;
let currentCompliment;

const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
    case currentCompliment:
      return "class='compliment-num'";
    default:
      return "";
  }
};

const bruteForceApproach = async () => {
  bruteForceSolutionBtn.setAttribute("disabled", "");

  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray
        .map(
          (num, index) =>
            `
            ${getClassName(num)}>
            ${testCaseArray[index]}
            
          `
        )
        .join("");

      bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`;

      if (currentNum + currentCompliment === target) {
        bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`;
        bruteForceSolutionBtn.removeAttribute("disabled");
        return;
      }
    }
  }
};

bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);

Try out the visualization again, and now you should see that the button is disabled when the animation is running.

Image showing how button is disabled when animation is showing
Adding the Map Solution Visualization
Creating the const Variables
We are going to create some new const variables which represent the optimal solution button element, output, and table elements for the animation.
const optimalSolutionBtn = document.getElementById("optimal-visual-btn");
const currentValueOutput = document.getElementById("current-value-output");
const finalOptimalSolutionResult = document.getElementById(
  "final-optimal-result"
);
const table = document.getElementById("table-output");
const tableBodyOutput = document.getElementById("map-table-body");

Here is the complete list of variable declarations for both visualizations:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");
const bruteForceNumbersOutput = document.querySelector(
  "#brute-force-output > .numbers-array"
);
const bruteForceTextOutput = document.querySelector(
  "#brute-force-output > .result-text"
);
const optimalSolutionBtn = document.getElementById("optimal-visual-btn");
const currentValueOutput = document.getElementById("current-value-output");
const finalOptimalSolutionResult = document.getElementById(
  "final-optimal-result"
);
const table = document.getElementById("table-output");
const tableBodyOutput = document.getElementById("map-table-body");

const testCaseArray = [11, 15, 2, 7];
const target = 9;
let currentNum;
let currentCompliment;

Creating the optimalApproach Async Function
The first step is to create the new optimalApproach function which will be an async function. You can add this below your bruteForceApproach function.
const optimalApproach = async () => {

};

Just like the bruteForceApproach function, we want to disable the button when the animation starts to prevent users from clicking it multiple times and breaking the animation.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
};

When the page first loads, the table is hidden by default. We want to show the table element when the animation starts.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
};

Each time we run this animation, we want to display messages to the user on if we have found the correct pair or not. At the beginning of the animation, we want to clear the previous output. 
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
};

Then, we need to create an empty map object which will eventually be updated over time in the for loop.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();
};

Next, we need to create a for loop which will be responsible for looping through each number in the array and updating the animation overtime. 
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {

  }
};

Inside the loop, we need to add the expression for calculating the difference.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {
    const difference = target - testCaseArray[i];
  }
};

Then, we need to add a setTimeout which will delay the changes by 2 seconds in the HTML markup and help with the animation effect.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {
    const difference = target - testCaseArray[i];

    await new Promise((resolve) => setTimeout(resolve, 2000));
  }
};

We then need to add an if statement to check if the map has the difference value.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {
    const difference = target - testCaseArray[i];

    await new Promise((resolve) => setTimeout(resolve, 2000));

    if (map.has(difference)) {

    }
  }
};

Inside the if statement, we need to update the text content to show the final indices array result on the screen. We will use the get method to get the index value from the map. 
 if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
 }

We also need to update the output for displaying a message that shows we have found the pair of numbers that adds up to the target. 
  if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
      currentValueOutput.innerHTML = `
      Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
      Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.
    `;
  }

We also need to remove the disabled attribute from the optimalSolutionBtn and return from the function. 
  if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
      currentValueOutput.innerHTML = `
      Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
      Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.
    `;
      optimalSolutionBtn.removeAttribute("disabled");
      return;
  }

If the pair has not been found, then we need to add an else clause.
  if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
      currentValueOutput.innerHTML = `
      Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
      Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.
    `;
      optimalSolutionBtn.removeAttribute("disabled");
      return;
  } else {

  }

Inside the else clause, we need to update the message to show that we have not found the pair and that the current number testCaseArray[i] is going to be added to the map along with its index value.
else {
      currentValueOutput.innerHTML = `
        Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
        Is the difference(${difference}) in our map? No.
        Add the current number ${testCaseArray[i]} to our map.
      `;
}

We then need to update the table output with the current number and its index value.
else {
      currentValueOutput.innerHTML = `
        Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
        Is the difference(${difference}) in our map? No.
        Add the current number ${testCaseArray[i]} to our map.
      `;
      tableBodyOutput.innerHTML += `
      
        ${testCaseArray[i]}
        ${i}
      
    `;
}

Lastly, use the set method to set the current number and index value in the map.
else {
      currentValueOutput.innerHTML = `
        Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
        Is the difference(${difference}) in our map? No.
        Add the current number ${testCaseArray[i]} to our map.
      `;
      tableBodyOutput.innerHTML += `
      
        ${testCaseArray[i]}
        ${i}
      
    `;
      map.set(testCaseArray[i], i);
}

Here is the complete code for your optimalApproach function.
const optimalApproach = async () => {
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {
    const difference = target - testCaseArray[i];

    await new Promise((resolve) => setTimeout(resolve, 2000));

    if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
      currentValueOutput.innerHTML = `
      Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
      Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.
    `;
      optimalSolutionBtn.removeAttribute("disabled");
      return;
    } else {
      currentValueOutput.innerHTML = `
        Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
        Is the difference(${difference}) in our map? No.
        Add the current number ${testCaseArray[i]} to our map.
      `;
      tableBodyOutput.innerHTML += `
      
        ${testCaseArray[i]}
        ${i}
      
    `;
      map.set(testCaseArray[i], i);
    }
  }
};

To test out this visualization, add an event listener to the optimalSolutionBtn and pass in the "click" event and optimalApproach function reference. 
optimalSolutionBtn.addEventListener("click", optimalApproach);

When you click on the "Show Visualization" button for the map solution, you should see the animation, as shown below:

Visualization for map solution
How to Reset the Table Output for the Map Solution
If you try to run the animation multiple times, then you will see that the table shows the results from the previous run.

Table showing results from the previous run
To fix this, we can reset the table before each run of the animation. Start by creating a resetTable function above your optimalApproach function.
const resetTable = () => {

};

const optimalApproach = async () => {
    .........

Inside that function, clear out the table and final text results. 
const resetTable = () => {
  tableBodyOutput.innerHTML = "";
  finalOptimalSolutionResult.textContent = "";
};

Call the resetTable function inside your optimalApproach function in order to see the results of resetting the table.
const optimalApproach = async () => {
  resetTable();
  optimalSolutionBtn.setAttribute("disabled", "");
    ...........

Test out your animation again, and now you should see that the table results reset before each new animation run. 
Final Solution Code and Live Example
Here is the complete JavaScript solution code for both visualizations:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");
const bruteForceNumbersOutput = document.querySelector(
  "#brute-force-output > .numbers-array"
);
const bruteForceTextOutput = document.querySelector(
  "#brute-force-output > .result-text"
);
const optimalSolutionBtn = document.getElementById("optimal-visual-btn");
const currentValueOutput = document.getElementById("current-value-output");
const finalOptimalSolutionResult = document.getElementById(
  "final-optimal-result"
);
const table = document.getElementById("table-output");
const tableBodyOutput = document.getElementById("map-table-body");

const testCaseArray = [11, 15, 2, 7];
const target = 9;
let currentNum;
let currentCompliment;

const getClassName = (num) => {
  switch (num) {
    case currentNum:
      return "class='current-num'";
    case currentCompliment:
      return "class='compliment-num'";
    default:
      return "";
  }
};

const bruteForceApproach = async () => {
  bruteForceSolutionBtn.setAttribute("disabled", "");

  for (let i = 0; i < testCaseArray.length; ++i) {
    currentNum = testCaseArray[i];
    for (let j = i + 1; j < testCaseArray.length; ++j) {
      currentCompliment = testCaseArray[j];
      await new Promise((resolve) => setTimeout(resolve, 1000));

      bruteForceNumbersOutput.innerHTML = testCaseArray
        .map(
          (num, index) =>
            `
              ${getClassName(num)}>
              ${testCaseArray[index]}
              
            `
        )
        .join("");

      bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`;

      if (currentNum + currentCompliment === target) {
        bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`;
        bruteForceSolutionBtn.removeAttribute("disabled");
        return;
      }
    }
  }
};

const resetTable = () => {
  tableBodyOutput.innerHTML = "";
  finalOptimalSolutionResult.textContent = "";
};

const optimalApproach = async () => {
  resetTable();
  optimalSolutionBtn.setAttribute("disabled", "");
  table.style.display = "block";
  currentValueOutput.innerHTML = "";
  const map = new Map();

  for (let i = 0; i < testCaseArray.length; ++i) {
    const difference = target - testCaseArray[i];

    await new Promise((resolve) => setTimeout(resolve, 2000));

    if (map.has(difference)) {
      finalOptimalSolutionResult.textContent = `Final indices: [${map.get(
        difference
      )}, ${i}]`;
      currentValueOutput.innerHTML = `
      Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
      Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.
    `;
      optimalSolutionBtn.removeAttribute("disabled");
      return;
    } else {
      currentValueOutput.innerHTML = `
        Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})
        Is the difference(${difference}) in our map? No.
        Add the current number ${testCaseArray[i]} to our map.
      `;
      tableBodyOutput.innerHTML += `
        
          ${testCaseArray[i]}
          ${i}
        
      `;
      map.set(testCaseArray[i], i);
    }
  }
};

bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);
optimalSolutionBtn.addEventListener("click", optimalApproach);

Here is a link again to the final live result on CodePen.
Conclusion
I hope you enjoyed that project and learned a little bit more about how the Two Sum problem works. 
I encourage you to play around with the project and maybe add some new features on your own like testing out different numbers or asking for user inputs for the numbers array and targets. 👍🏾



 Coding Interview Prep – Free Resources to Help You Ace Your Interviews 
freeCodeCamp — Tue, 16 Nov 2021 23:50:43 +0000
 By Evan SooHoo
In the words of RealToughCandy, everyone wants a "one-stop shop" when it comes to learning.
She uses this term to describe Educative.io, but Educative.io costs $60 a month unless you choose to commit to its annual plan. So it's not a free resource, which means it's not available to everyone.
If money were not a factor, you might buy a copy of Cracking the Coding Interview, get a LeetCode Premium subscription, and sign up for access to Grokking the Coding Interview before scheduling some mock interviews. 
Now, websites like LeetCode are interesting because they provide an excellent resource for free. A large percentage of LeetCode questions are free, the discussions section provides free solutions where the best code/explanations are voted to the top, and the platform itself can run hundreds of test cases in seconds.
Many people argue that LeetCode premium is not worth it, though writers like Yangshun Tay beg to differ. What interests me about LeetCode is not their premium option, but that they make so much of their service available without it. 
All that being said, there are a number of quality free resources you can use to prepare for your coding interviews. Let's go through my favorites now.
Best Free Resources for Coding Interview Prep
Without further ado, here are the best free resources I have found for coding interview preparation:
freeCodeCamp articles
The 30-minute guide to rocking your next coding interview is a free article available on FreeCodeCamp. Half the value here is in curated lists of LeetCode questions to match every major topic
Here's another great (and extensive) guide that focuses on JavaScript interviews and goes through all the JS basics you'll need to know. It includes tons of code samples, and moves through the material in an approachable way.
Cracking the Coding Interview
Cracking the Coding Interview is still one of the best resources out there for interview prep, even in 2021. I have heard some people say that it is no longer sufficient, but I have had two coding interviews that were taken out of the book almost verbatim. 
Unfortunately, this is not a free resource...but here is a LeetCode forum that maps every CTCI question to a LeetCode one. 
The reason this is acceptable is that they are not perfect mappings. For example, the LeetCode String Compression problem is not exactly the same as its CTCI equivalent because it has an added constraint. It is actually harder than the CTCI version
If you do choose to purchase Cracking the Coding Interview, the solutions are all freely available on GitHub. They are in multiple programming languages, in case you are not a Java developer. 
McDowell herself built the repository and committed the Java portion to it, so it is very unlikely the repository will removed due to copyright infringement.
BaseCS
BaseCS is a great collection of articles that explain computer science fundamentals, from hash tables to sorting algorithms, with custom illustrations, well-written analogies, and light-hearted explanations. 
Best of all, every single article is free from the Medium paywall. Had they not been, Joshi probably could have pocketed hundreds, if not thousands of dollars from all her readers.
Educative.io
The Educative.io course on 14 coding patterns is not free, but a summary is available on HackerNoon and written by an Educative.io cofounder...presumably as either a gesture of goodwill, or a "free sample".
LeetCode questions sorted by programming pattern
Here is a public LeetCode post that maps all 14 coding patterns to respective lists of LeetCode problems.
InterviewNoodle – still in development
Arslan Ahmad is building a consolidated collection of interview preparation articles on Medium called InterviewNoodle. Just weeks ago, I would have written that this resource is very incomplete, but he has added so much content that I actually think he may now want to divide it into sections.  
This, like Educative.io, is meant to be a “one-stop shop.” That Arslan Ahmad is the founder of Design Gurus increased my respect for him exponentially, since this means he is attempting to build a free version of an Educative course that makes him money.  
Currently the Medium pages on this publication are not paywall blocked. This could be a coincidence, but for now it's a great resource.
The rest of this article will cover additional resources, though the ones above are my favorites.
Additional Coding Interview Prep Resources
An Interview Primer
If you don't know what to expect in a coding interview, the "30-minute guide" from freeCodeCamp linked above is a great "primer". Still, it is rather lengthy – even though it takes 30 minutes to just read through it, it would take much longer to actually review and go through its "General tips" section.
This might be just what you're looking for if you want to be really thorough. But what other options do you have?
"Confessions from a Big Tech Hiring Manager" is my single favorite video. It's by "Pragmatic Engineer," and is all about the interview process. 
This video has useful and practical advice, but it also conveys the perfect attitude. He argues that you should think of every failed interview as a learning opportunity.

        
Other Interview Prep articles
"If software engineering is in demand, why is it so hard to get a software engineering job?" This is a tongue-in-cheek overview of the coding interview process. 
If you read it, you should probably ignore the "string compression" story, which does not add much to the article.
The other side of the software engineer interview is a kind of sequel to the article above, summarizing and responding to Pragmatic Engineer's thoughts.
The Responses I Got From A Software Developer Candidate That Made Me Hire Him is an article that provides more insight on the interviewer's perspective, but unlike the two above it is behind Medium's paywall.
What's the Interview Process Like, In a Nutshell?
If I were asked to summarize all the resources above to you, here's what I would share:

I would say that you typically get between 30 minutes to an hour to solve a coding question. 
You typically get a choice of programming language like C++, Python, Java, or JavaScript, but not always...in some instances you do not have a choice.
Outside of the coding portion, they are free to ask you pretty much anything, from language-specific questions to favorite projects, but any interview with a coding portion tends to be dominated by it.

And here's some general advice to consider: you are going to be dealing with people who may be pretty tired of interviews. Smile if you can. Try to show enthusiasm. Have a conversation, and try to talk to the interviewer the way you might communicate if the two of you were pair programming, but they were more senior.
How to Start Your Interview Prep
I think that for most people starting out in this interview prep process, LeetCode is pretty hard. Here are two possible starting problems, though the best point of entry is admittedly Cracking the Coding Interview.

FizzBuzz on LeetCode. I recommend it because it should not require any additional interview preparation, and will help you familiarize yourself with the LeetCode platform.
Here's an article about FizzBuzz on InterviewNoodle so you can learn more what that's about.
Jewels and Stones on LeetCode. If you are not able to solve this on your first try, then you will have to learn a technique that is useful in many coding interview problems.

Learn about hashmaps

        
There are many more data structures than just hashmaps, but I see these come up in coding interviews so often that I think they deserve their own section.

Valid Anagram is another good LeetCode "starting point." It does not necessarily require a hashmap, but something that acts like a hashmap
Here is Nick White solving Valid Anagram
This is Alex Lee using hashmaps in Java. He does not explain the internals of how they actually work, but he provides practical advice on how to actually use them.

What to do after you cover the basics
After you get started preparing and are comfortable with the basics, I would refer back to the resources above. 
The 30-Minute Guide and Cracking the Coding Interview (again, there are free LeetCode problem mappings if you do not own Cracking the Coding Interview) both cover computer science fundamentals. And 14 coding patterns goes a little bit further.
Closing Thoughts
There is a lot more work to be done when it comes to coding interview preparation resources. It is relatively easy for me to simply point to good resources in an aggregate post, but actually providing comprehensive reviews or my own resource would require an order of magnitude more effort. I haven't gotten there yet.
So for now, there is certainly a gap. The most comprehensive content, in my opinion, can be found in Cracking the Coding Interview and this Educative.io course. And that's not to mention the plethora of resources someone with a lot of money could afford, from coaches, to coding interview bootcamps, to expensive mock interviews in which the interviewers provide detailed feedback. 
That the people behind Educative.io and its "coding interview patterns" course have made efforts to provide free resources, like InterviewNoodle and a HackerNoon article, count for a lot to me.
I personally don't really use sites like GeeksforGeeks or interview resources on Github that are written exclusively in markdown. It would be very useful to build a platform with detailed blog-style explanations and embedded coding platforms, but at that point you would essentially be recreating Educative.io.
Medium provides an interesting case: Some of the best writers can be found here, but they are incentivized to put things behind a paywall. Anyone, in theory, can put up articles without a paywall on Medium the way BaseCS has. But few Medium writers seem to do this anymore.
We need more high-quality articles. We need practice problem lists that are continually updated. We need great YouTube content creators, like Nick White, to continue to provide clear problem explanations. 
Efforts by BaseCS were largely successful, and my one wish is that it had continued to produce content...but this was all produced by a single person with a full-time job, a podcast, a YouTube channel, and apparently no compensation from Medium.
Not everyone has the same level of access to educational coding interview resources, so I admire the people who have done everything in their power to create free alternatives.
Yangshun Tay, author of "The 30-minute guide to rocking your next coding interview", sent me a personal email a few months after this article was published and shared some more helpful resources.

Here's a link to the main Tech Interview Handbook Website, which contains in-depth and structured guides that can really help you prep for interviews. 
Additionally, he's published Grind75 which generates study plans based on time left, which could also be of interest to your readers.

The Tech Interview Handbook currently has about 69,000 stars on GitHub, and the website is the closest thing I have seen to a free, "one-stop-shop" software engineer interview resource.  
Grind75 is designed to be a better version of Blind75, a popular list Yangshun also made that received 3200 upvotes on a LeetCode discussion.
I hope these help you out! Happy prepping.
 


 Coding Interview Backtracking Problems Crash Course – The Only One You'll Ever Need 
Lynn Zheng — Tue, 29 Jun 2021 20:00:32 +0000
 Whether you are new to coding interviews or are already familiar with the concept of backtracking algorithms, this is the crash course for you.
In it, we will learn about an all-purpose coding template for solving backtracking problems and apply it to two LeetCode hard problems. Ready to crunch your next coding interview? Let's go!
If you just want to dive right in, you can find the course here (and linked at the bottom of this article). If you want a little more info, read on. :)
Who is the Course for and What is the Backtracking Algorithm?
This course is suitable for anyone who is preparing for coding interviews, especially those who are looking to hone their skills in solving backtracking problems.
Backtracking is a common category for questions in coding interviews. The algorithm for solving those problems usually involves recursion and building incrementally on previous states to arrive at the ultimate valid solution.
Backtracking is a favorite topic among top tech companies like Google, Microsoft, and Facebook, precisely because it requires robust reasoning and coding competence to nail those questions.
However, because of its recursive nature and complex problem definition, backtracking problems are usually a major source of confusion among devs who are preparing for coding interviews.
To address this confusion, this crash course aims to arm with you a concise, 20-line template that you can apply to the majority of backtracking problems.
Course Outline
This course runs for a total of 40 minutes and the structure is as follows:

An 8-minute introduction to the template

A 15-minute hands-on code-along session for LeetCode Question 51. N-Queens

A 15-minute hands-on code-along session for LeetCode Question 37. Sudoku Solver


The All-Purpose Template
For your convenience, I've copied the template over. This is exactly the same template that I use for my coding interviews, or when I'm developing algorithms for my indie games. I even used it once in my research on a non-convex optimization problem.
def is_valid_state(state):
    # check if it is a valid solution
    return True

def get_candidates(state):
    return []

def search(state, solutions):
    if is_valid_state(state):
        solutions.append(state.copy())
        # return

    for candidate in get_candidates(state):
        state.add(candidate)
        search(state, solutions)
        state.remove(candidate)

def solve():
    solutions = []
    state = set()
    search(state, solutions)
    return solutions

The first three are all helper functions, and the last and most important one, solve, is essentially the one that a LeetCode problem is asking you to write.
Solving LeetCode Problems Hands-On
We will next apply this template to solving two LeetCode hard problems: LeetCode Question 51. N-Queens and LeetCode Question 37. Sudoku Solver.
To illustrate the flexibility of the template, see below for how we solve the N-Queens problem by doing nothing fancy other than adapting the four functions (renaming solve to solveNQueens). The complete code for either problem is available in my GitHub gist.
Watch the video course to follow along my analysis and adaptation of the template.
class Solution:
    # solveNQueens is essentially the solve function
    def solveNQueens(self, n: int) -> List[List[str]]:
        solutions = []
        state = []
        self.search(state, solutions, n)
        return solutions

    def is_valid_state(self, state, n):
        # check if it is a valid solution
        return len(state) == n

    def get_candidates(self, state, n):
        if not state:
            return range(n)

        # find the next position in the state to populate
        position = len(state)
        candidates = set(range(n))
        # prune down candidates that place the queen into attacks
        for row, col in enumerate(state):
            # discard the column index if it's occupied by a queen
            candidates.discard(col)
            dist = position - row
            # discard diagonals
            candidates.discard(col + dist)
            candidates.discard(col - dist)
        return candidates

    def search(self, state, solutions, n):
        if self.is_valid_state(state, n):
            state_string = self.state_to_string(state, n)
            solutions.append(state_string)
            return

        for candidate in self.get_candidates(state, n):
            # recurse
            state.append(candidate)
            self.search(state, solutions, n)
            state.pop()

Check out the video course here:

        
 
You can access the template as well as the solutions to the two LeetCode problems (N-Queens and Sudoku Solver) in my GitHub gist:

        
 
Final Thoughts
Remember that practice makes perfect, so do try applying this template to more backtracking problems on LeetCode. Best of luck crunching your next coding interview!
For more content like this, check out my YouTube channel:

        
 


 How to Solve Leetcode Problems With Python One-Liners 
freeCodeCamp — Fri, 02 Apr 2021 15:13:35 +0000
 By Ganesh Kumar Marimuthu
Python is one of the most powerful programming languages. It gives us various unique features and functionalities that make it easy for us to write code. 
In this article we'll solve Leetcode array problems in one line using one of Python's most interesting features – List Comprehension.
What is List Comprehension?
Before going into the problems, let's make sure we understand what list comprehension is all about.

A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists  

Wikipedia


Let's see how list comprehension works with an example.
Consider an array of numbers. Our task is to add 1 to the numbers at odd indices and to add 2 to the number at even indices.
Now we'll see how to solve the above problem using both a for-loop and list comprehension.
How to solve the problem with a for-loop
def addOneAndTwo(nums, n):
    for i in range(n):
        if i % 2 == 1:
            nums[i] += 1 
        else:
            nums[i] += 2 
    return nums

How to solve it with list comprehension
def addOneAndTwo(nums, n):
    return [nums[i] + 1 if i % 2 == 1 else nums[i] + 2 for i in range(n)]

You can see how the solution using list comprehension is simplified from 6 lines to 1 line. This is the power of list comprehension.
How to Solve Leetcode Problems with List Comprehension
Now let us solve the below Leetcode problems in 1 line using list comprehension.
1. Shuffle The Array
Here's the problem from Leetcode:
Given the array nums consisting of 2n elements in the form [x₁,x₂,...,x_n,y₁,y₂,...,y_n]. Return the array in the form [x₁,y₁,x₂,y₂,...,x_n,y_n].
Example
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Solution
def shuffle(self, nums, n):
    return reduce(lambda a, b: a + b, [[nums[i], nums[j]] for i, j in zip(range(0, n), range(n, 2 * n))])

2. Number of Good Pairs
Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i < j.Return the number of good pairs.
Example
Input: nums = [1,2,3,1,1,3]
Output: 4 
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Solution
def numIdenticalPairs(self, nums):
    return sum([int(i != j and nums[i] == nums[j]) for i in range(0, len(nums)) for j in range(i + 1, len(nums))])

3. Kids With the Greatest Number of Candies
Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has.
For each kid check if there is a way to distribute extraCandies among the kids such that they can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.
Example
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: Kid 1 has 2 candies, and if they receive all extra candies (3) they will have 5 candies – the greatest number of candies among the kids. 
Kid 2 has 3 candies, and if they receive at least 2 extra candies then they will have the greatest number of candies among the kids. 
Kid 3 has 5 candies, and this is already the greatest number of candies among the kids. 
Kid 4 has 1 candy, and even if they receive all extra candies they will only have 4 candies. 
Kid 5 has 3 candies, and if they receive at least 2 extra candies then they will have the greatest number of candies among the kids.
Solution
def kidsWithCandies(self, candies, extraCandies):
    return [candy + extraCandies >= max(candies) for candy in candies]

4. Decompress Run-Length Encoded List
We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2*i], nums[2*i+1]] (with i >= 0).  For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.
Example
Input: nums = [1,2,3,4]
Output: [2,4,4,4] 
Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2]. 
The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4]. At the end the concatenation [2] + [4,4,4] is [2,4,4,4].
Solution
def decompressRLElist(self, nums):
    return reduce(lambda a, b: a + b, [[nums[i + 1]] * nums[i] for i in range(0, len(nums), 2)])

5. Richest Customer's Wealth
You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i^th customer has in the j^th bank. Return the wealth that the richest customer has.
A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.
Example
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6 
Explanation: 1st customer has wealth = 1 + 2 + 3 = 6 2nd customer has wealth = 3 + 2 + 1 = 6  Both customers are considered the richest with a wealth of 6 each, so return 6.
Solution
def maximumWealth(self, accounts):
    return max([sum(row) for row in accounts])

Conclusion
I hope the above solutions were useful. You can combine list comprehension with other functions like map, filter and reduce to make the solutions more simple and effective.
Thank You 🤘
Linkedin | Github
 


 Unmasking Bitmasked Dynamic Programming 
freeCodeCamp — Thu, 03 Jan 2019 16:38:18 +0000
 By Sachin Malhotra
How to go from Fearing it to Conquering it!


There are no coincidences in this world.
— Grand Master Oogway

Well, Master Oogway, no disrespect, coincidences do occur and I think they are just God’s way of remaining anonymous. Not just me, Albert Einstein believes this too ?.
111, that’s not really my lucky number, so to say.
However, this number filled me with joy and ecstasy when I saw it as my rank on the rankings page of the LeetCode contest number 111.
What a coincidence!

That’s the highest ranking in a weekly contest that I’ve achieved so far on the platform. The contest number and the ranking were obviously pure coincidence.
The contest usually consists of an Easy problem, 2 Medium level problems, and a Hard problem.
More often than not, the hard problem is something that requires a lot of algorithmic knowledge and prior practice to be able to pull off during the contest. This contest’s final problem was no exception to this.
Why do I say it was very hard? Have a look at the number of people who were able to solve it during the contest.

As the title of the article suggests, this problem was to be solved using Bit Masking based Dynamic Programming.
Dynamic Programming is one of the most dreaded algorithmic domains out there. It requires a lot of practice to develop intuition about a dynamic programming-based solution to a problem. I’ve always considered it to be an enhancement to a recursive solution to a problem. The main idea behind dynamic programming in layperson’s terms is:

Avoid repeated computations by caching the results.

Bitmasking as a topic in computer programming is something that I have (and I’m sure countless of other developers out there have as well) feared for a long time. This is one of those topics that will surely take you off balance in an interview and get you a rejection.
Programmers out there generally tend to avoid practicing problems related to this topic simply because it is difficult to build an intuition about it.
Optimizations related to bit manipulations occur in the most unexpected of places. With some practice, I have been able to overcome the fear, so to say, of working on bitmasking-based programming problems.
In this article, apart from describing the solution to the problem I’ve mentioned above, in detail, I will also go over some basics of bitmasking and some programming problems where it can come in handy.
As with any new thing you learn, it’s very difficult to retain theoretical concepts related to bitmasking. Retention is the best when it comes via practice. That is the main aim of this article. Let’s quickly look at the table of contents before we kick off the main article.
Get a bit of Hot Chocolate and be ready for …

0️⃣ 1️⃣ What is Bit Manipulation? 0️⃣ 1️⃣
The Basics ✍️
Counting the Number of set bits
Masking and Unmasking a specific bit
? Missing Number ?
☝️?✌️? Counting Bits ?? ??
⛩ Maximum Product of Word Lengths ⛩
Set Representation using Bitmasking
??Partition Array to K Equal Sum Subsets ??
? Find the Shortest Superstring ?
Conclusion ??
References ?

0️⃣ 1️⃣ What is Bit Manipulation? 0️⃣ 1️⃣

A bit is to the computing world what an atom is to human life.

A bit is essentially the smallest unit of storage in a computer. It’s the only unit that a computer understands.
The only information that a bit can store is formed from two different states: 0️⃣ and 1️⃣. Any sort of computation that a computer performs is basically some form of bit manipulation.

Let’s look at a Wikipedia definition for bit manipulation:

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions.

Implementation-wise, one of the most useful and effective low-level optimizations to an algorithm is bit manipulation.
In some cases, bit manipulation can bypass looping over a data structure and give manifolds speed improvement. The only downfall to such optimizations is the code readability and maintenance.

Who wrote this piece of shitty (read lightning fast) code?
That is one scary piece of ☠code ☠
The Basics ✍️
At the heart of bit manipulation are the bit-wise operators:

And (&)
Or (|)
Not (~)
XOR (^)

These are the fundamental operators using which we can perform some complicated bit manipulation operations. Hence, it’s very important to brush up on these operators and their truth tables before moving onto some more interesting stuff.

_Source: [https://www.topcoder.com](https://www.topcoder.com" rel="noopener" target="blank" title=")
The truth tables show the results for these operators when they operate on 2 bits represented by A and B. The computer has to deal with much more than just one bit of data.
The data processed by the system is generally in bytes or kilobytes or more. How do these operators work on operands represented by for e.g. 8-bits or 16-bits? In such a scenario, the operations are the same, except that they operate on each bit of the arguments. Let’s consider a simple example to clarify this.
A = 11101010B = 00110101
+-+-+-+-  AND  -+-+-+-+A & B = 00100000
+-+-+-+-  OR   -+-+-+-+A | B = 11111111
+-+-+-+-  NOT  -+-+-+-+~A    = 00010101
+-+-+-+-  XOR  -+-+-+-+A ^ B = 11011111
In addition to these 4 basic operators, there are two other set of bitwise operators that do come in very handy. Almost all the problems that we will look at in this article will be making use of them to give a huge boost in computational speed. These are the left shift &lt;< and the right shift >> operators.
Simply speaking, the left shift operator means multiplying a number by 2 and the right shift operator means dividing a number by 2.
Let’s look at a simple animation to show why these operators are called left shift and right shift respectively.

Left Shift Operation in Action.
For demonstrating the left shift operation, we start off with the decimal number 1 and then repeatedly multiply it with 2. As you can see in the binary representation of the resulting numbers, the only 1 in the representation keeps on shifting left one step at a time. That’s why it’s called the left shift operation.

Right Shift Operation in Action.
Along the same lines, for demonstrating the right shift operation, we start off with the decimal number 128and then repeatedly divide it by 2. As you can see in the binary representation of the resulting numbers, the only 1 in the representation keeps on shifting right one step at a time. That’s why it’s called the right shift operation.
Now that we are all versed with the basic binary operators, let’s move on to some simple use cases for these operators. We will look at a few examples below. These are not programming problems by themselves, however, they are used a lot as building blocks in a lot of algorithms.
Basic Use Cases ?
Counting the Number of set bits
One of the basic utilities for the operators we looked at above is to count the number of bits, set in a given binary representation.
This might not seem an important use case right now, but we will be getting into more details later on and then it will start to seem more meaningful. For now, let’s just count the number of set bits as efficiently as possible.

_Source: [giphy](https://giphy.com/gifs/cRMgB2wjHhVN2tDD2z" rel="noopener" target="blank" title=")
The first method that we will look at for this, is a bit intuitive. It makes use of the bitwise AND operator. Starting from the least significant bit, we simply check if the bit at each position is set or not and increment a counter accordingly.
The AND operator returns True iff both the bits are True. Let’s look at the code for this.
Yet another way of doing this is by ANDing the number with itself-1 until the number becomes zero. The number of steps taken to reach 0 will be the number of set bits in the original number.
The reason this works is that every time we AND the number with itself-1, one bit gets removed from the number. This goes on until the number becomes zero.
Masking and Unmasking a specific bit
Suppose we want to mask a specific bit in a binary representation. This simply means turning off the bit or transforming a 1 → 0 . On similar lines, unmasking simply means the reverse operation on a specific bit.
You might be wondering why this is useful at all. One of the most important use cases for masking (or unmasking) a bit is in set related operations.
We can represent a set of items as an X-bit integer, Xis the number of items in the set. Masking a bit would mean the removal of that item from the set. For a practical application of this, be patient and read on ?.

_Source: [giphy](https://giphy.com/gifs/k-kindergarten-behTrfrYhb3iw" rel="noopener" target="blank" title=")
XOR is a very versatile operator and it is perfect for the task of masking and unmasking operations.
1 ^ ? → 00 ^ ? → 1

XOR outputs 1 when both the bits are opposite and a 0 when both the bits are the same.

Essentially, we can make use of the same masking variable for achieving the set / un-set operation corresponding to a particular bit (the integer in the ? is being called the masking variable).
A ^ (1 << i)
The above operation will lead to masking the bit at index i if originally that bit was set in A and the same operation will lead to unmasking the bit at index i if originally it was unset in A.
We have already seen how to detect if a bit is set or not when we looked at ways to count the number of set bits in a given binary representation.
An important thing to note here is the index. Usually, for data structures in high-level programming languages, whenever we refer to a specific index, we mean the index of a particular element in that data-structure starting from the left end.
What we are referring to an index above is from the right end (the least significant bit in the binary representation has the index 0).
That’s more than enough of the basics for now. Let’s get to some actual programming problems. This will help solidify what we’ve learned so far in the article and also help build up an intuition for solving problems using bit manipulation in general.
? Missing Number ?

_Source: [LeetCode](https://leetcode.com/problems/missing-number/description/" rel="noopener" target="blank" title=")
There are multiple ways of solving this problem. We can sort the given list of numbers and then iterate from 0..n and easily find the missing number. This will give us a O(NlogN) solution.
Another way of solving this problem is by making use of a dictionary. We simply add all the elements in our list to a dictionary and then we can simply search for the missing number. This is a linear time solution but it makes use of additional space.
Let’s look at how we can achieve a O(1) space, O(N) time solution like a boss ? by using bit manipulation.
We will make use the XOR property here to solve this problem. As mentioned before, XOR evaluates to True when the input bits are different and it evaluates to False when presented with the same bits. We are interested in the later scenario. What do you think the following evaluates to?
A ^ A

_Source: [tenor](https://tenor.com/view/bottaro-zero-nothing-trani-ok-gif-12693830" rel="noopener" target="blank" title=")
XORing a number with itself gives us 0. That’s the main idea behind our approach here.
So, what we will do is, we will XOR all the numbers in our list. Let’s call the value we get after this as A .
We will XOR all the numbers from 0..n together. Let’s call this value, B.
By doing this, all the numbers present in the original array will get XORed to their counterparts and will evaluate to 0. The only number left in the end will be the missing number.
A ^ B = missing number
☝️?✌️? Counting Bits ?? ??

_Source: [LeetCode](https://leetcode.com/problems/counting-bits/description/" rel="noopener" target="blank" title=")
This is one of those problems where writing down the answer for various test cases and observing the results for patterns really helps. So, we will do exactly that and use the pattern we find to directly arrive at the final algorithm.
Let’s look at the number of 1’s in the binary representation of the first 16 numbers.
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  160  1  1  2  1  2  2  3  1  2   2   3   2   3   3   4   1
The pattern being formed above is the following:

An even number, E, has the same number of bits as that of E / 2
An odd number, O, has one more bit than that of O / 2

That’s all there is to see in the results above. This is the algorithm in its entirety. All we have to do is to iterate on numbers from 0..n and use the two rules above and we solved the problem like a boss ?.
If you paid attention to the core idea of dynamic programming discussed during the beginning of the article, you’d know that this here, in essence, is a dynamic programming problem.
We make use of the result for a previous subproblem (smaller number) to calculate the answer (number of set bits) for the current subproblem.
On the face of it, we don’t need any bit manipulation as such to solve this problem. It can be solved by simple if-else clauses and a for loop.
So, this is not really a bitmasking + dynamic programming kind of problem.
Let’s look at a simple solution based on the ideas above.
This is a perfectly good way to solve this problem. For every index, i, we check the number of bits in the number i / 2 and also add 1 if the current number is odd.
We can, however, solve it in a geekier way, so to say using bit manipulation. The two operations being performed are:

division by 2 and
checking if the number is even or not.

We have already seen the use of the right shift operator, &gt;>, for division by 2.
As for the second operation, we can simply check if the least significant is set or not. If you notice, all the odd numbers have their least significant bit set. While the even numbers don’t.
We have already seen how to check if a particular bit is set or not using the AND operator. Let’s see a geekier ? version of the above code.
If you look at the runtimes for both the programs, they’re almost the same. A major chunk of the time is consumed by the construction of the output array.
Bitwise operations are always optimized and are faster than other higher level programming constructs.
⛩ Maximum Product of Word Lengths ⛩

_Source: [LeetCode](https://leetcode.com/problems/maximum-product-of-word-lengths/description/" rel="noopener" target="blank" title=")
There’s good news and bad news. The good news is that a slightly optimized version of the brute force algorithm will get your code accepted on the platform.
The brute force way is to check all the pairs of words and for each pair, check if there are any common characters between them. For all such pairs that don’t have any common characters, record the maximum value of len(word1) * len(word2).
The bad news is that this algorithm is extremely slow. Let’s look at the percentage of solutions on LeetCode which this brute force algorithm is able to beat.


_Source: [giphy](http://giphy.com" rel="noopener" target="blank" title=")
Shame on you, Sachin!
That’s not the kind of stats you want to see for your submission. If you’re someone who simply wants to solve a problem, then your job here is done. Nothing more to do. But, if you’re like me and if you want to make this dog stop ?, then read on!
Let’s look at the time complexity for this brute force algorithm before moving onto a much more optimized solution using bit manipulation.
We consider all possible pairs of words from the given array. Considering there are N words in the given array, we will get O(N²) complexity right off the bat.
Other than that, we have a dictionary containing sets of characters for each of the words in the dictionary. Considering the size of the alphabet to be 26 (lowercase alphabets only), each set can potentially be of size 26.
For each pair of words, we perform a set intersection to check whether the two words have any common characters or not. Set intersection takes linear time and hence, the overall complexity for this algorithm would come out to be O(26N²) which is essentially O(N²).
It turns out that we can’t get rid of the part where we have to consider each pair of words from the given array. So, we can’t get rid of the O(N²) part of the algorithm.
The portion that we can get rid of, however, is the part where we compare two words and see if they have any common characters. That constant 26 slows down the algorithm a lot.
An important thing to note here is that the question simply cares about common characters and not their frequency or their order.

What if we simply use a bitmask to represent the characters in a word?

What we can do here is to have a bitmask consisting of 26 bits to represents the characters belonging to a particular word. Let’s look at such a representation for a few words to make things clearer.

Bitmaps for the three words: hello, algorithm, and tweet.
Hope the above figure makes it clear what we mean by a bitmask representing a corresponding word. Once we have these bitmasks for all the words, all that remains now is to check if two words have any common characters or not.
If two words would have any common characters, then the corresponding bits for those characters would be set in the bitmasks for both the words.
Hence, all we have to do is to do a bitwise AND of the bitmasks representing two words and check if we get a 0 or not. If we do end up getting a 0, that would imply no intersection and that is precisely what we are looking for.
For e.g. Let's consider two words "hello" and "jack"
The bitmask corresponding to "hello" will have the bits for 'h', 'e', 'l', and 'o' set.
The bitmask corresponding to "jack" will have the bits for 'j', 'a', 'c', and 'k' set.
Since these words don't have any character in common, the bitwise AND of their bitmasks will give a 0.
Had there been any common characters between them, then both their bitmasks would have set bits at the same indexes (corresponding to the common letters) and hence we would get a non-zero bitwise AND.
Let’s look at the code for this modification in the algorithm we just discussed.
Bitwise operations are super quick. Let’s look at the performance of this algorithm on the LeetCode platform to corroborate the quickness of bit manipulation.

Not bad, right? We improved the runtime for our program from 1820 ms earlier to 712 ms now. That’s a huge improvement, isn’t it? It turns out, we can improve this algorithm even further.

The improvement can be made because of the fact that two different words can have the same bitmask.

For e.g. hello and llohhel both would have the same bitmask. We can store the longest word for a given bitmask since all we care about is maximizing the product of word lengths.
Let’s look at the code after incorporating this improvement.
By doing this very optimization, the runtime comes down to 208ms ???

_Source: [giphy](https://giphy.com/gifs/3o6ZtiLpjhjv9HVUti" rel="noopener" target="blank" title=")
Set Representation using Bitmasking
We introduced an idea in the previous problem which will be crucial in the next two problems that we will discuss. Essentially, we used the idea of bitmasking to represent elements belonging to a set.
In the previous article, we considered a set of 26 alphabets and we resented that by using a bitmask containing 26 bits. A 0 at a particular index in the mask would represent set exclusion whereas a 1 would represent set inclusion.
This idea is very crucial for dynamic programming problems that deal with subproblems involving a subset of numbers. We can’t really cache a subset of numbers. A set is not a hashable data structure.
For e.g. suppose we have an array of numbers [4, 3, 6]
Let's look at all possible subsets of this array.[]
[4]
[3]
[6]
[4, 3]
[4, 6]
[3, 6]
[4, 3, 6]For dynamic programming problems where intermediate states are defined by these subsets, we need a memory efficient way of performing caching.
What do we do in such a scenario?
This is where we have bitmasks come in. They are memory-efficient ways of representing subsets of elements. Let’s have a look at how we can represent the subsets above using bitmasks.
Since we have 3 elements in our given array, [4, 3, 6] we can make use a a 3-bit number for representing each of these elements. An empty subset would be represented by 000. Let's look at each of the subsets along with their bit representations.000 -->> []
001 -->> [6]
010 -->> [3]
011 -->> [3, 6]
100 -->> [4]
101 -->> [4, 6]
110 -->> [4, 3]
111 -->> [4, 3, 6]
Depending upon the problem’s constraints, we can make use of a bitmask. For e.g. in the previous problem, the alphabet set was limited to the size 26. A lot of programming problems that have small array sizes and involve dynamic programming that require you to hash subsets, usually are an indication of bitmasking-based approach.
A 26-bit mask, e.g. in the previous problem, is essentially an integer and we can simply cache that integer in a dictionary. This saves on the memory footprint of the algorithm and greatly cuts down on the time complexity for the algorithm since bit manipulation is very efficient. We can easily include and exclude elements from the subset by masking and unmasking corresponding bits from the mask.
Let’s look at another problem based on this idea before we finally discuss the star problem of this article.
??Partition Array to K Equal Sum Subsets ??

_Source: [LeetCode](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/" rel="noopener" target="blank" title=")
This is just one of those questions that begs you to use bitmasking. Notice the size of the array. It’s just 16 elements. If we consider a bitmask to represent the elements in an array, we’d have a 16-bit integer at our hands.
That means, to represent all the possible subsets of a given array, we’d have 2¹⁶ possible integers. We don’t really need actual subsets. All we need is a bitmask telling us the elements belonging to that subset. Based on this idea, let’s look at dynamic programming-based approach to solve the above problem.
The problem statement only asks us if a k-equal-sum partitioning is possible or not. It doesn’t ask us to return the actual partitioning. That makes the problem a whole lot simpler.
We don’t care which partition an element belongs to as long as the overall sum of a partition is what total_sum / k.
As we’ve mentioned in the above paragraphs, we will be using a bitmask to represent the elements of the array.
We will use the individual bit states of the mask to identify which numbers have already been assigned a partition and which ones still remain to be assigned one. We can only assign a number to a partition if after adding it to that partition, the total sum remains <= total_sum / k .
If the sum, S, of all the elements of the array is divisible by k, we have to complete k — 1 partitions since the last partition will automatically fall into place. In case the total sum is not divisible by k , then such an equal sum partitioning is not possible.
Why dynamic programming?
Before looking at the code for this problem based on the ideas we’ve discussed above, it’s important to understand how dynamic programming fits into the picture. We’ve already seen why bitmasking would come in handy. But where exactly does dynamic programming fit in?
Recursion is a natural fit for the problem since we have got a set of N elements and we need to partition them into k different subsets all of which have an equal sum.
Since we don’t really know what partition a number should belong to, we have to try out all the options. That means, for a given partition, we try adding all available numbers recursively (within the constraints of the partition sum) and see which choice leads us to an answer.
The recursion would be based on the following three variables:

the number of partitions remaining.
the mask representing what elements in the original array are unassigned.
and the current partition sum.

As we all know, for any problem to be classified as a dynamic programming problem, it should have the following two properties:

Optimal sub-structure ~ which simply means that the original problem must be breakable into subproblems and optimal solutions to the subproblems should be usable in a way to find the optimal solution to the main problem.
Overlapping subproblems ~ which mean there are multiple recursive calls to the same subproblems and to avoid repeated computations, we can cache the results for our subproblems.

Let’s look at the recursion tree for this problem to understand if we have any overlapping subproblems. We already have the first property satisfied.

The tuple (K, 12, 3) is the recursion state that gets repeated. K is the number of remaining partitions which in our example is 2. 12 is the current partition’s sum. 3 is the bitmask. If you consider the bitwise representation of 3, you will get 0011. That implies the two elements 5 and 7 from the set [8, 16, 5, 7] and hence the sum 12.
In the above recursion tree, we consider K = 2. That means we need 2 partitions each of sum 18. Since we never reach 18 in the tree above, the K never gets reduced. This is just a part of the recursion tree and the complete version.
We can clearly see two recursion states getting repeated. We get the same mask 0011 twice. We can simply store the result once and then re-use it later on.
Now let’s look at the code for based on bitmasking + dynamic programming.
Now we are finally ready to look at the main problem of this article. The problem that is not as straightforward in its bitmasking application as the current one and the previous one.
? Find the Shortest Superstring ?

_Source: [LeetCode](https://leetcode.com/problems/find-the-shortest-superstring/description/" rel="noopener" target="blank" title=")
What do you think the simplest way of forming a superstring is?
You simply take any permutation of the given words and all of these permutations will be valid superstrings.
However, the question doesn’t ask us to form any superstring. It asks us to form the shortest superstring covering all the words.**
For this problem, we will explore the idea of chaining words together. Intuitively, you can consider the idea of chaining as set union.
Let’s consider two different set of elements and then look at the combined set containing all their elements together i.e. the union set.

The repeated elements are only considered once in the union.
As we can see above, whenever we do a union over two sets, the common elements only appear once. We will adopt a similar idea with chaining two words together.
Essentially, when chaining words A and B together, we will only consider the common portion between the suffix of A and prefix of B exactly once.** Let’s look at the diagrammatic representation for chaining of two words.

This is an important concept that will come in handy for solving this problem. So as to avoid repeated computations of finding out the common portion between two words which are being chained together, we will do some preprocessing.
We will find out the length of the suffix of A that overlaps with the prefix of B where A and B are being chained together. We will do this for all the pairs of words in our given list. In Python, given a string S, we can make use of S[i:] to obtain all the suffixes and S[:i] to obtain all the prefixes. We make use of this for our preprocessing below.
Now that the idea of chaining is clear, we can move onto the next part of the problem where we explain why this problem can be solved recursively.
Why Recursion?
Now that we are familiar with the concept of chaining, we know that whenever we chain two words together, the new word formed can be shorter than the combined lengths of the two original words.
Extending this idea to all the words in the given list, we have to form a superstring that will be formed by chaining one word after the other until we are done with all the words.
The important question here is, in what order should the words be chained together?
For the three words aabc , hjaa, and chuj the chaining order hjaa → aabc → chuj = hjaabchuj is better than aabc → hjaa → chuj = aabchjaachuj since the former gives a superstring of length 9 as opposed to 12 in the latter order.
So, the chaining order determines the overall length of the formed superstring.

We will be trying out all possible arrangements for the superstrings using the given list of words and choosing the shortest one.

That seems legit, but why dynamic programming? ?
Instead of relying on a recursion tree for explaining the need for dynamic programming, we will look at an example that will explain the same idea.
Suppose we are given a set of 5 words [A, B, C, D, E] and we are to form the shortest superstring that contains all the words.
We already know that we are solving this problem recursively. Suppose in the middle of our recursion, we are already done deciding the chaining order of the first 3 words. Let’s say this ordering was B → A → C . Now, we need to find out the best way to chain D and E after C so that the overall superstring length is minimized.**
Let’s say that in our recursion we found that C → E → D was the best chaining order. We don’t know yet if the superstring formed via B → A → C → E → D is the shortest one. However, we know that C → E → D is the best chaining order for the three words C, D, and E .

I know it’s gotten tiring, but keep reading ?
Suppose now we arranged the first three words a little differently in our recursion (a separate recursion path) and now we have A → B → C and we have to recurse again to find out the best possible arrangement for E and D . However, we already know from above the best possible arrangement is C → E → D . Why calculate this again? This is where dynamic programming comes into the picture.
That’s it? Go on. Explain some more.
Nah, let’s now look at the the Python code bringing all these ideas together.
Uh oh! Where the heck is bitmasking in all this?

Ok ok, let’s get to bitmasking ?
Let’s rephrase the problem in a slightly different manner that will make the requirement for bitmasking very clear.
Given a set of N elements, we need to find a suitable arrangement for them that will minimize a certain metric. Since we are relying on dynamic programming, we will be caching results for subproblems.
Our subproblems will be represented by the subset of these N items. As we’ve seen in this article and especially in the previous two problems, it’s difficult to cache subsets as it is.
In case the problem constraints are small, we can represent the elements of the list using a bitmask and use that for caching purposes.

After all, a bitmask is just a number.

Let’s finally get to the code for finding the shortest superstring given a set of N words.

Line 3 ~ The initial mask is composed of all 1s. That implies all the words are available for chaining. If the mask becomes 0, that means no word is left for chaining. So, the length of the superstring would be 0. This is the base case.
Line 7 ~ If you’ve paid attention to the example involving 5 words [A, B, C, D, E] from before, you know that the opportunity of caching arises when we have the two words D and E to be chained together following C.
_Thus, we need to know the previous word in the superstring so far so as to attach the rest of the words. Hence, prev_i, which represents the index in the original array of the previous word in the superstring is also used for caching purposes apart from the mask._
Line 12, 15 ~ We always check all the given set of words and only consider those as options for the current step in our recursion which have not been previously used. We make use of bitmasking for this. To see if a word has been used or not, we simply check if the bit at the corresponding index in the mask is unset or not.
Line 18 ~ Makes use of the preprocessing we did earlier. For the word to be chained / attached to the word at index prev_i , we know the amount of overlap between the two. Thus, if we decide on considering the word at index i as the next word in our recursion, the amount of length it will add to our superstring would be len(A[i]) — overlap between the words A[prev_i] and A[i]

All this is fine and dandy, but wasn’t the original question asking for the superstring itself and not just the length of the shortest superstring?
Am I shying away from solving the entire problem? Of course not!

_Source: [giphy](https://giphy.com/gifs/no-smh-scooby-doo-EriPNV1whwKac" rel="noopener" target="blank" title=")
The function recurse simply returns the length of the shortest superstring and not the superstring itself. The problem statement, however, asks us to find out the shortest superstring.
If you look at the code carefully, you’ll notice a parent dictionary. At every step in our recursion, we have multiple options of words which can be chained to the current superstring (thus extending it). We use the parent dictionary to store the word at each step that gave the best answer (shortest length).
For a given mask — which tells us which words have already been chained together — and a given previous word (prev_i), the parent dictionary stores the next word that in the superstring that gives the optimal answer.
We will use this dictionary to backtrack and form the shortest superstring.

In the end, that’s one of the best sights for a competitive programmer, especially if it’s for a hard problem in a timed competition.
Conclusion ??

Operations on bits are highly efficient and they are generally performed in parallel via optimized system level instructions.
It’s difficult, but not impossible, to write clean, understandable code involving bit manipulations.
AND , OR , and NOT are the three fundamental bitwise operators.
The left-shift &lt;< and the right-shift >> operators are used for multiplication or division by 2.
The XOR operator is a versatile operator that can be used in many different programming problems. It returns True only when both the bits are opposites and False otherwise.
Dynamic Programming-based solutions involve some sort of caching for the results of subproblems. The subproblems are represented by a set of variables. These variables are not necessarily primitive data types.
Bitmasking comes in very handy in dynamic programming problems when we have to deal with subsets and the list/array size is small. A mask (having all 0s or all 1s) can represent the elements of the set and setting or unsetting a bit can mean inclusion and exclusion from the set.
If the array/list/set size is, say, around 20, then you’d have 2²⁰ possible bitmasks which comes out to be almost a million of them. It’s not always the case you will encounter all of these bitmasks in a test case. However, that’s the maximum possible number.
We have to be careful about when to use bitmasking. We can’t have a 100-bit mask as that would be computationally intractable.
For a solution to be eligible for dynamic programming, it should satisfy the optimal substructure and the overlapping subproblems properties. Usually, through some practice, you can start to identify if the problem at hand will have a DP based solution or not.

References ?

https://www.hackerearth.com/practice/notes/bit-manipulation/
https://blog.bitsrc.io/bitmask-there-is-space-at-the-bottom-5a741d18c4e3
https://bit.ly/2QRTIpj
https://bit.ly/2CCUCxn
https://www.geeksforgeeks.org/bitmasking-and-dynamic-programming-set-1-count-ways-to-assign-unique-cap-to-every-person/
https://www.geeksforgeeks.org/bitmasking-dynamic-programming-set-2-tsp/
https://codeforces.com/blog/entry/17973

It’s been a long article and one that I’ve absolutely loved writing. If you’ve read this far, then you’ve probably found this article really helpful. Do spread some love by sharing it as much as possible and destroy that clap button! ?
Oh, if you’d like to read more such awesome articles all lit up with animations and beautiful, explanatory images, do checkout our newly opened [kitchen](https://github.com/DivyaGodayal/CoderChef-Kitchen/).
Believe me, we’ve got some lip smacking recipes for you and with the holiday season upon us, I’m sure you’ll love them.
Wishing you all a Merry Christmas and a Happy New Year!

leetcode - freeCodeCamp.org

LeetCode Meditations: A Visual Handbook of Data Structures and Algorithms Concepts

Table of Contents

Prerequisites

Chapter One: Arrays & Hashing

Dynamic Arrays

Time and space complexity

Hash Tables

Time and space complexity

Prefix Sums

Time and space complexity

Chapter Two: Two Pointers

Palindrome example

Squares of a sorted array example

Chapter Three: Sliding Window

Fixed window size

Dynamic window size

Time and space complexity

Chapter Four: Stack

Time and space complexity

Chapter Five: Binary Search

Time and space complexity

Chapter Six: Linked Lists

Singly linked lists

Doubly linked lists

Circular linked lists

Time and space complexity

Interlude: Fast & Slow Pointers

Finding the middle node of a linked list

Chapter Seven: Trees

Binary trees, binary search trees (BSTs)

Inserting into a binary search tree

Recursive solution:

Time and space complexity

Iterative solution:

Time and space complexity

Deleting from a binary search tree

Time and space complexity

Traversals

1. Depth-First Search (DFS)

Preorder traversal:

Inorder traversal:

Postorder traversal:

2. Breadth-First Search (BFS)

Chapter Eight: Heap / Priority Queue

Heap properties

Heaps with arrays

Inserting/removing elements

Heapsort

Time and space complexity

Chapter Nine: Backtracking

Subsets

Time and space complexity

Chapter Ten: Tries

Time and space complexity

Chapter Eleven: Graphs

Representing graphs

Edge List

Adjacency Matrix

Adjacency List

Traversals

Breadth-First Search

Depth-First Search

Chapter Twelve: Dynamic Programming

Time and space complexity

Chapter Thirteen: Intervals

Chapter Fourteen: Bit Manipulation

Bitwise operators

AND (&)

OR (|)

XOR (^)

NOT (~)

Left shift (zero fill) (<<)

Right shift (sign preserving) (>>)

Right shift (unsigned) (>>>)

Getting a bit

Setting a bit

Conclusion

Resources & Credits

How to Build a Visualization for Leetcode's Two Sum Problem – HTML, CSS, & JavaScript Project

AND (`&`)

OR (`|`)

XOR (`^`)

NOT (`~`)

Left shift (zero fill) (`<<`)

Right shift (sign preserving) (`>>`)

Right shift (unsigned) (`>>>`)

Creating the `const` and `let` Variables

Creating the `getClassName` Function

Creating the `bruteForceApproach` Function

How to Disable the `bruteForceSolutionBtn` When the Animation is in Progress

Creating the `const` Variables

Creating the `optimalApproach` Async Function