Kyle Edwards

LeetCode Strategies and Solutions

#programming #dsa

Like it or not, using Leetcode-style challenges for technical interviews is a standard practice in our industry. In the best of cases, recruiters and interviewers hopefully see them as ways to gauge a candidate’s potential or how they work through a complicated problem, rather than test for rote memorization of solutions.

It doesn’t hurt to have some knowledge of algorithms and data structures in your toolbelt, at least enough to identify a problem enough to know which strategies are usable, and which ones are most time- and space-efficient. At the very least, you may find yourself reaching for one in your real-world projects.

Important Strategies

Knapsack

table[row][col]=table[row-1][col]+table[row][col-n[row-1]]
0 1 2 3 4 5
[] 1 0 0 0 0 0
[1] 1 1 1 1 1 1
[1, 2] 1 1 2 2 3 3
[1, 2, 5] 1 1 2 2 3 4

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Hashset

var containsDuplicate = function(nums) {
    const s = new Set();
    for (const n of nums) {
        if (s.has(n)) return true;
        s.add(n);
    }
    return false;
};

Hashset length comparison

var containsDuplicate = function(nums) {
    const s = new Set(nums); return s.size !== nums.length;
};

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Terse

var isAnagram = function(s, t) {
	if (s.length !== t.length) return false;
    return Array.from(s).sort().join('') === Array.from(t).sort().join('');
};

Using hashmap

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    const counts = {};
    for (const c of s) {
        counts[c] = counts[c] ? counts[c] + 1 : 1;
    }
    for (const c of t) {
        if (!counts[c]) return false;
        counts[c]--;
    }
    return true;
};

Prime Product Encoding

*Note: This is definitely not a good algorithm for long strings, but for shorter word lists, these hashes can fit into unsigned integer values rather then bigints, which can be very memory efficient.

const PRIMES = [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n, 41n, 43n, 47n, 53n, 59n, 61n, 67n, 71n, 73n, 79n, 83n, 89n, 97n, 101n];

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;
    let sumS = 1n;
    let sumT = 1n;
    for (let i = 0; i < s.length; i++) {
        const sCode = s.charCodeAt(i) - 97;
        const tCode = t.charCodeAt(i) - 97;
        sumS *= PRIMES[sCode];
        sumT *= PRIMES[tCode];
    }
    return sumS === sumT;
};

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Brute force

var twoSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) return [i, j];
        }
    }
};

Complement lookup

var twoSum = function(nums, target) {
    var hash = {};
    var complement;
    for (var i = 0; i < nums.length; i++) {
        complement = target - nums[i];
        if (undefined !== hash[nums[i]]) {
            return [hash[nums[i]], i];
        }
        hash[complement] = i;
    }
};

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

var isPalindrome = function(s) {
    s = s.replace(/[^A-Za-z0-9]/gi, '').toLowerCase();
    let start = 0;
    let end = s.length - 1;
    while (start <= end) {
        if (s[start++] !== s[end--]) {
            return false;
        }
    }
    return true;
};

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.
var isValid = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(')');
        } else if (s[i] === '[') {
            stack.push(']');
        } else if (s[i] === '{') {
            stack.push('}');
        } else if (s[i] !== stack.pop()) {
            return false;
        }
    }
    return stack.length === 0;
};

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

You must implement a solution with O(1) time complexity for each function.

var MinStack = function() {
    this.min = Infinity;
    this.stack = [];
};

MinStack.prototype.push = function(val) {
    this.stack.push([val, this.min]);
    if (val < this.min) {
        this.min = val;
    }
};

MinStack.prototype.pop = function() {
    const [val, min] = this.stack.pop();
    this.min = min;
    return val;
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1][0];
};

MinStack.prototype.getMin = function() {
    return this.min;
};

Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

var evalRPN = function(tokens) {
    const stack = [];
    for (let token of tokens) {
        let x;
        if (token === '+') {
            stack.push(stack.pop() + stack.pop())
        } else if (token === '-') {
            x = stack.pop()
            stack.push(stack.pop() - x)
        } else if (token === '*') {
            stack.push(stack.pop() * stack.pop())
        } else if (token === '/') {
            x = stack.pop()
            stack.push(Math.trunc(stack.pop() / x))
        } else {
            stack.push(+token)
        }
    }
    return stack[stack.length - 1];
};

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Recursive

var reverseList = function(head) {
    if (!head) return null;
    let newHead = head;
    if (head.next) {
        newHead = reverseList(head.next);
        head.next.next = head;
    }
    head.next = null;
    return newHead;
};

Iterative

var reverseList = function(head) {
	let prev = null;
	let curr = head;
    while (curr !== null) {
	    const next = curr.next;
	    curr.next = prev;
	    prev = curr;
	    curr = next;
    }
    return prev;
};

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

var mergeTwoLists = function(list1, list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    let head;
    let left = list1;
    let right = list2;

    if (left.val <= right.val) {
        head = left;
        left = left.next;
    } else {
        head = right;
        right = right.next;
    }

    let curr = head;
    while (left || right) {
        if (left && (!right || left.val <= right.val)) {
            curr.next = left;
            curr = curr.next;
            left = left.next;
        } else {
            curr.next = right;
            curr = curr.next;
            right = right.next;
        }
    }
    return head;
};

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* head = NULL;
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    if (list1->val <= list2->val) {
        head = list1;
        list1 = list1->next;
    } else {
        head = list2;
        list2 = list2->next;
    }
    
    struct ListNode* curr = head;
    while (list1 != NULL || list2 != NULL) {
        if (list1 == NULL) {
            curr->next = list2;
            list2 = list2->next;
        } else if (list2 == NULL || list1->val <= list2->val) {
            curr->next = list1;
            list1 = list1->next;
        } else {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    return head;
}

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Iterative

var hasCycle = function(head) {
    const set = new Set();
    let curr = head;
    while (curr) {
        if (set.has(curr)) {
            return true;
        }
        set.add(curr);
        curr = curr.next;
    }
    return false;
};

Floyd’s tortoise and hare

var hasCycle = function(head) {
    if (!head) return false;
    let fast = head;
    let slow = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) {
            return true;
        }
    }
    return false;
};

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Bitwise XOR

var singleNumber = function(nums) {
    let n = 0
    for (let num of nums) {
        n ^= num
    }
    return n
};

Number of 1 Bits

Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Log2

var hammingWeight = function(n) {
    let weight = 0;
    while (n > 0) {
        weight++;
        n -= 1 << Math.floor(Math.log2(n)) >>> 0;
    }
    return weight
};

Bitwise Shift

var hammingWeight = function(n) {
    return n <= 0 ? 0 : ((n & 1) + hammingWeight(n >>> 1));
};

String Manipulation

var hammingWeight = function(n) {
    return n.toString(2).replaceAll('0', '').length;
};

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Dynamic programming with log2

var countBits = function(n) {
    const output = [0]
    for (let i = 1; i <= n; i++) {
        let msb = 1 << Math.floor(Math.log2(i));
	    output[i] = 1 + output[i - msb];
    }
    return output;
};

Dynamic programming with offset

var countBits = function(n) {
    const output = [0]
    let offset = 1
    for (let i = 1; i <= n; i++) {
        if (offset * 2 === i) {
            offset = i
        }
        output[i] = 1 + output[i - offset]
    }
    return output;
};

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Note:

Bitwise shift

var reverseBits = function(n) {
    let x = 0
    for (let i = 0; i < 32; i++) {
        x |= ((n >>> i) & 1) << (31 - i)
    }
    return x >>> 0
};

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Sum difference

var missingNumber = function(nums) {
    let sum = 0
    let max = 0
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]
        max += i + 1
    }
    return max - sum
};

Bitwise XOR

Note: Like Single Number above, bitwise XOR is used to negate duplicate values.

var missingNumber = function(nums) {
    let out = 0
    for (let i = 0; i < nums.length; i++) {
        out ^= nums[i]
        out ^= i + 1
    }
    return out
};

Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Return true if n is a happy number, and false if not.

var isHappy = function(n) {
    let x = n
    const set = new Set()
    while (x !== 1) {
        x = x.toString()
	        .split('')
	        .reduce((acc, y) => acc + (+y * +y), 0)
        if (set.has(x)) {
            return false
        }
        set.add(x)
    }
    return true
};

Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s.

Increment the large integer by one and return the resulting array of digits.

Array iteration

var plusOne = function(digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
        digits[i] += 1
        if (i !== 0 && digits[i] === 10) {
            digits[i] = 0
        } else {
            break
        }
    }
    if (digits[0] === 10) {
        digits[0] = 0
        digits.unshift(1)
    }
    return digits
};

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: If you draw this out, you’ll notice at each step x, you can either reach step x-1 or x-2 (…think the Fibonacci sequence). If those two values are pre-calculated, then it’s trivial to calculate this in O(n) time with constant space.

Fibonacci with dynamic programming

var climbStairs = function(n) {
    const steps = [0, 1, 2];
    if (n <= 2) {
        return n
    }
    for (let i = 3; i < n + 1; i++) {
        steps[i] = steps[i - 1] + steps[i - 2]
    }
    return steps[n]
};

Fibonacci with swap

var climbStairs = function(n) {
    if (n <= 2) return n;
    let a = 1;
    let b = 2;
    for (let i = 3; i < n + 1; i++) {
        const c = a + b;
        a = b;
        b = c;
    }
    return b;
};

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Note: The trick with this one is that

var minCostClimbingStairs = function(cost) {
    const acc = [];
    for (let i = cost.length - 1; i >= 0; i--) {
        const cur = cost[i];
        if (i + 2 >= cost.length) {
            acc[i] = cur;
        } else {
            acc[i] = Math.min(acc[i + 1], acc[i + 2]) + cur;
        }
    }
    return Math.min(acc[0], acc[1]);
};

Best Time to Buy and Sell Stocks

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

var maxProfit = function(prices) {
    let buy = 0;
    let sell = 1;
    let maxProfit = 0;

    while (sell < prices.length) {
        const buyPrice = prices[buy];
        const sellPrice = prices[sell];
        if (sellPrice < buyPrice) {
            buy = sell;
        }
        maxProfit = Math.max(sellPrice - buyPrice, maxProfit);
        sell++;
    }

    return maxProfit;
};

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

var search = function(nums, target) {
    let start = 0;
    let end = nums.length;

    while (start + 1 < end) {
        const cursor = start + Math.floor((end - start) / 2);
        const num = nums[cursor]
        if (num === target) {
            return cursor;
        } else if (num < target) {
            start = cursor;
        } else {
            end = cursor;
        }
    }

    return nums[start] === target ? start : -1;
};

Kth Largest Element in a Stream

Design a class to find the $k$th largest element in a stream. Note that it is the $k$th largest element in the sorted order, not the $k$th distinct element.

Implement KthLargest class:

Note: The trick of this challenge is that the KthLargest class never needs to remove elements. This makes it possible to only ever store k elements and create a min-heap of size k.

Sorted array with binary search insert

Note: Much better to use a heap for this.

var KthLargest = function(k, nums) {
    this.nums = nums.sort((a, b) => +a - b);
    this.k = k;
};

KthLargest.prototype.add = function(val) {
    let start = 0;
    let end = this.nums.length;
    let lastCursor = null;
    while (true) {
        const cursor = start + Math.floor((end - start) / 2);
        const curr = this.nums[cursor];
        if (curr !== undefined && val > curr) {
            start = cursor;
        } else if (curr !== undefined && val <= curr) {
            end = cursor;
        }
        if (start + 1 >= end) {
            const newArray = this.nums.slice(0, end)
                .concat([val])
                .concat(this.nums.slice(end));
            this.nums = newArray;
            break;
        }
    }
    return this.nums[this.nums.length-this.k];
};

Min-heap

Question: Why is it necessary to push, sift up, pop, then sift down?

var KthLargest = function(k, nums) {
    this.k = k;
    this.minHeap = [];
    for (const num of nums) {
        this.add(num);
    }
};

KthLargest.prototype.siftDown = function(val) {
    let idx = 0;
    while (true) {
        const leftIdx = idx * 2 + 1;
        const rightIdx = idx * 2 + 2;
        const curr = this.minHeap[idx];
        let leftChild = this.minHeap[leftIdx] ?? Infinity;
        let rightChild = this.minHeap[rightIdx] ?? Infinity;
        let swapIdx = null;
        if (leftIdx < this.minHeap.length && leftChild < curr) {
            swapIdx = leftIdx;
        }
        if (rightIdx < this.minHeap.length) {
            if (swapIdx === null && rightChild < curr) {
                swapIdx = rightIdx;
            } else if (swapIdx !== null && rightChild < leftChild) {
                swapIdx = rightIdx;
            }
        }
        if (swapIdx === null) {
            break;
        }
        this.minHeap[idx] = this.minHeap[swapIdx];
        this.minHeap[swapIdx] = curr;
        idx = swapIdx;
    }
};

KthLargest.prototype.siftUp = function() {
    let idx = this.minHeap.length - 1;
    while (idx > 0) {
        const curr = this.minHeap[idx];
        const parentIdx = Math.floor((idx - 1) / 2);
        const parent = this.minHeap[parentIdx];
        if (curr < parent) {
            this.minHeap[idx] = parent;
            this.minHeap[parentIdx] = curr;
            idx = parentIdx;
        } else {
            break;
        }
    }
};

KthLargest.prototype.add = function(val) {
    this.minHeap.push(+val);
    this.siftUp();

    if (this.minHeap.length > this.k) {
        this.minHeap[0] = this.minHeap.pop();
        this.siftDown();
    }

    return this.minHeap[0];
};

Kth Largest Element in Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

function findKthLargest(nums: number[], k: number): number {
    const store: number[] = new Array(20001).fill(0);
    for (const num of nums) {
        store[num + 10000]++;
    }
    let sum = 0;
    for (let i = 20000; i >= 0; i--) {
        sum += store[i];
        if (sum >= k) {
            return i - 10000;
        }
    }
    return 0;
};

Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the $i$th stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

var lastStoneWeight = function(stones) {
  const heap = []
  for (const stone of stones) {
    heap.push(stone);
    maxHeapifyUp(heap);
  }
  while (heap.length > 1) {
      let x = heapifyPop(heap);
      let y = heapifyPop(heap);
      if (x != y) {
        heap.push(Math.abs(y - x));
        maxHeapifyUp(heap);
      }
  }
  return heap.length ? heap[0] : 0;
};

function heapifyPop(arr) {
  const top = arr[0];
  const lastNode = arr[arr.length - 1];
  arr[0] = lastNode;
  arr.length = arr.length - 1;
  maxHeapifyDown(arr);
  return top;
}

function maxHeapifyDown(arr) {
  let idx = 0;
  const len = arr.length;
  while (true) {
      const parent = arr[idx];
      const leftChildIdx = idx * 2 + 1;
      const rightChildIdx = idx * 2 + 2;
      const leftChild = arr[leftChildIdx];
      const rightChild = arr[rightChildIdx];
      let swap = null;
      if (leftChildIdx < len && leftChild > parent) {
          swap = leftChildIdx;
      }
      if (rightChildIdx < len &&
          (swap === null && rightChild > parent) ||
          (swap !== null && rightChild > leftChild)
      ) {
          swap = rightChildIdx;
      }
      if (swap === null) break;
      arr[idx] = arr[swap];
      arr[swap] = parent;
      idx = swap;
  }
}

function maxHeapifyUp(arr) {
  let idx = arr.length - 1;
  while (idx > 0) {
      const child = arr[idx];
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = arr[parentIdx];
      if (child > parent) {
          arr[parentIdx] = child;
          arr[idx] = parent;
          idx = parentIdx;
      } else {
          break;
      }
  }
}

Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Recursive

var invertTree = function(root) {
    if (root) {
        const tmp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = tmp;
    }
    return root
};

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

var maxDepth = function(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

var maxDepth = function(root) {
    if (!root) return 0;
    const stack = [];
    root.depth = 1;
    stack.push(root);
    let max = 1;

    while (stack.length) {
        const item = stack.pop();
        if (item.left) {
            item.left.depth = item.depth + 1;
            max = Math.max(max, item.left.depth);
            stack.push(item.left);
        }
        if (item.right) {
            item.right.depth = item.depth + 1;
            max = Math.max(max, item.right.depth);
            stack.push(item.right);
        }
    }
    return max
};

var maxDepth = function(root) {
    if (!root) return 0;
    const queue = [];
    root.depth = 1;
    queue.push(root);
    let max = 1;
    while (queue.length) {
        const item = queue.shift();
        if (item.left) {
            item.left.depth = item.depth + 1;
            max = Math.max(max, item.left.depth);
            queue.push(item.left);
        }
        if (item.right) {
            item.right.depth = item.depth + 1;
            max = Math.max(max, item.right.depth);
            queue.push(item.right);
        }
    }
    return max
};

Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Recursive depth-first search with additional fields

var diameterOfBinaryTree = function(root) {
    root.depth = 0
    let leftDepth = 0
    let rightDepth = 0
    let maxDiameter = 0
    if (root.left) {
        diameterOfBinaryTree(root.left)
        leftDepth = root.left.depth
        maxDiameter = Math.max(maxDiameter, root.left.maxDiameter)
    }
    if (root.right) {
        diameterOfBinaryTree(root.right)
        rightDepth = root.right.depth
        maxDiameter = Math.max(maxDiameter, root.right.maxDiameter)
    }
    root.depth = 1 + Math.max(leftDepth, rightDepth);
    root.maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth)
    return root.maxDiameter
};

Recursive depth-first search

var diameterOfBinaryTree = function(root) {
    let diameter = 0;
    const dfs = (node) => {
        if (!node) {
            return 0;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    };
    dfs(root);
    return diameter;
};

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

var isBalanced = function(root) {
    let balanced = true;
    const dfs = (node) => {
        if (!node) {
            return 0;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        balanced = balanced && (Math.abs(left - right) <= 1)
        return Math.max(left, right) + 1;
    };
    dfs(root);
    return balanced;
};

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

(In-order) Tree Traversal

var isSameTree = function(p, q) {
    if (!p && !q) return true;
    return Boolean(
        p &&
        q &&
        p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    );
};

Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

BFS + Tree Traversal

var isSameTree = (p, q) => {
    if (!p && !q) return true;
    return Boolean(
        p &&
        q &&
        p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    );
};
var isSubtree = function(root, subRoot) {
    if (!subRoot) return true;
    if (!root) return false;
    if (isSameTree(root, subRoot)) return true;
    return (
        isSubtree(root.left, subRoot) ||
        isSubtree(root.right, subRoot)
    );
};

Sum of Two Integers

XOR/AND adder

Note: Kind of brute forced this one, and I’m not totally sure what the theory is here, but it resembles a full-adder circuit, but it keeps looping until the carry bits ((a & b) << 1) no longer conflict with a ^ b, meaning that there will not be a carry in the next iteration.

var getSum = function(a, b) {
    const x = a ^ b;
    const y = (a & b) << 1;
    if (x & y) return getSum(x, y);
    return x ^ y;
};

Reverse Integer

Hacky string reverse method

var reverse = function(x) {
    const negative = x < 0;
    x = Math.abs(x);
    const z = +x.toString().split('').reverse().join('');
    if (isNaN(z) || z > 2147483648 || z < -2147483647) {
        return 0;
    }
    return negative ? -z : z;
};

Modulo 10

const MAX_INT = Math.pow(2, 31) - 1;
const MIN_INT = -Math.pow(2, 31);
var reverse = function(x) {
    if (!x) return 0;
    let output = 0;
    let n = x;
    while (n !== 0) {
        output *= 10;
        output += n % 10;
        n = Math.trunc(n / 10);
    }
    if (output > MAX_INT || output < MIN_INT) return 0;
    return output;
};

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Sorted key

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        map = {}
        for str in strs:
            key = list(str)
            key.sort()
            key = ''.join(key)
            if key not in map:
                map[key] = []
            map[key].append(str)
        return list(map.values())

Prime product encoding

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        arr = [None] * 100
        for i in range(100):
            arr[i] = {}
        for s in strs:
            strlen = len(s)
            key = 1
            for c in s:
                key *= PRIMES[ord(c) - 97]
            if key not in arr[strlen]:
                arr[strlen][key] = []
            arr[strlen][key].append(s)
        output = []
        for map in arr:
            output += list(map.values())
        return output

Counts as hashmap key

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        map = defaultdict(list)
        for s in strs:
            chars = [0] * 26
            for c in s:
                chars[ord(c) - 97] += 1
            map[str(chars)].append(s)
        return list(map.values()

Product of Array Except Self

Sum

var productExceptSelf = function(nums) {
    const leftProds = [];
    const rightProds = [];
    for (let i = 0; i < nums.length; i++) {
        const left = i;
        const right = nums.length - 1 - i;
        leftProds[left] = nums[left] * (i > 0 ? leftProds[left - 1] : 1);
        rightProds[right] = nums[right] * (i > 0 ? rightProds[right + 1] : 1);
    }
    return nums.map((_, i) => {
        if (i === 0) return rightProds[1] ?? 0;
        if (i === nums.length - 1) return leftProds[i - 1] ?? 0;
        return leftProds[i - 1] * rightProds[i + 1];
    })
};

Constant space

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        output = [1] * len(nums)
        # Left pass
        for i in range(len(nums) - 1):
            output[i+1] = output[i] * nums[i]
        # Right pass
        right = 1
        for i in range(len(nums) - 1, 0, -1):
            right *= nums[i]
            output[i - 1] *= right
        return output

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Queue

var generateParenthesis = function(n) {
    const queue = [{
        str: '(',
        open: n - 1,
        close: n
    }];
    const complete = [];
    while (queue.length) {
        const { str, open, close } = queue.shift();
        if (close && open < close) {
            queue.push({
                str: str + ')',
                open,
                close: close - 1
            });
        }
        if (open) {
            queue.push({
                str: str + '(',
                open: open - 1,
                close,
            });
        }
        if (!open && !close) {
            complete.push(str);
        }
    }
    return complete;
};

Recursive stack backtracking

var generateParenthesis = function(n) {
    let stack = '(';
    const complete = [];

    const recur = (open, close) => {
        if (!open && !close) {
            complete.push(stack);
            return;
        }

        if (open) {
            stack += '(';
            recur(open - 1, close);
            stack = stack.slice(0, -1);
        }

        if (close > open) {
            stack += ')';
            recur(open, close - 1);
            stack = stack.slice(0, -1);
        }
    }

    recur(n - 1, n);
    return complete;
};

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

class Solution:
    def trap(self, height: List[int]) -> int:
        left = [0] * len(height)
        right = [0] * len(height)
        top_left = 0
        top_right = 0
        for i in range(len(height)):
            if height[i] > top_left:
                top_left = height[i]
            left[i] = top_left
            r = len(height) - i - 1
            if height[r] > top_right:
                top_right = height[r]
            right[r] = top_right
        output = 0
        for i in range(len(height)):
            output += min(left[i], right[i]) - height[i]
        return output

Constant Memory

class Solution:
    def trap(self, height: List[int]) -> int:
        max_left = 0
        max_right = 0
        l = 0
        r = len(height) - 1
        output = 0
        while l <= r:
            if max_left <= max_right:
                if height[l] > max_left:
                    max_left = height[l]
                else:
                    output += max_left - height[l]
                l += 1
            else:
                if height[r] > max_right:
                    max_right = height[r]
                else:
                    output += max_right - height[r]
                r -= 1
        return output

Find Pivot Index

var pivotIndex = function(nums) {
    let l = [nums[0]]
    for (let i = 1; i < nums.length; i++) {
        l[i] = nums[i] + l[i - 1]
    }
    let r = 0;
    let res = -1;
    for (let i = 0; i < nums.length; i++) {
        const pos = nums.length - i - 1;
        r += nums[pos]
        if (r === l[pos]) res = pos
    }
    return res
};

Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Note: You can also perform a binary search using the min/max values of each row first, then use another binary search to find the column.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        start = 0
        end = rows * cols
        while start < end:
            mid = start + (end - start) // 2
            curr = matrix[mid // cols][mid % cols]
            if target == curr:
                return True
            if target > curr:
                start = mid + 1
            else:
                end = mid
        return False

Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Note: This is particularly tricky because it’s not a matter of finding a number of bananas Koko can eat per hour to finish all of the piles in h hours, but rather the minimum number.

The way this is accomplished in this solution is storing the min() of the stored result and the current k value, and then continuing the binary search past the match. This causes the extra steps of ensuring the left and right pointers cross, but it thorough enough to find the lowest k value.

from math import ceil

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        min_k = 1
        max_k = max(piles)
        res = max_k

        while min_k <= max_k:
            k = (min_k + max_k) // 2
            hours = 0
            for pile in piles:
                hours += ceil(pile / k)
            if hours <= h:
                res = min(res, k)
                max_k = k - 1
            else:
                min_k = k + 1

        return res

LRU Cache

Note: I thought this may be possible with a min-heap (and it may be, but not as efficient). I believe the way to go is with using a hashtable to store the key-value pairs, along with a pointer to a node in a linked list. When the list is at capacity, the next insert will add a node at the end of the list. The first node of the linked list is then removed and its value from the hashtable. On update or read, the node will be moved to the end of the list.

type LRUNode struct {
    Key int
    Value int
    Next *LRUNode
    Prev *LRUNode
}

type LRUCache struct {
    Directory map[int]*LRUNode
    Head *LRUNode
    End *LRUNode
}


func Constructor(capacity int) LRUCache {
    head := &LRUNode{
        Key: -1,
        Value: -1,
        Next: nil,
        Prev: nil,
    }
    end := head
    for i := 0; i < capacity - 1; i++ {
        end.Next = &LRUNode{
            Key: -1,
            Value: -1,
            Next: nil,
            Prev: end,
        }
        end = end.Next
    }
    return LRUCache{
        Directory: make(map[int]*LRUNode),
        Head: head,
        End: end,
    }
}


func (this *LRUCache) Get(key int) int {
    ptr, ok := this.Directory[key]
    if !ok || ptr == nil {
        return -1
    }
    if ptr != this.End {
        prev := ptr.Prev
        next := ptr.Next
        if prev != nil {
            prev.Next = next
        }
        if next != nil {
            next.Prev = prev
        }
        if ptr == this.Head {
            this.Head = next
        }
        ptr.Next = nil
        ptr.Prev = this.End
        this.End.Next = ptr
        this.End = ptr
    }
    return this.End.Value
}


func (this *LRUCache) Put(key int, value int)  {
    val := this.Get(key)
    var node *LRUNode = nil
    if val == -1 {
        next := this.Head.Next
        if next != nil {
            next.Prev = nil
            node = this.Head
            delete(this.Directory, node.Key)
            this.Head = next
            node.Prev = this.End
            this.End.Next = node
            this.End = node
        } else {
            node = this.Head
            delete(this.Directory, node.Key)
        }
    } else {
        node = this.End
    }
    this.Directory[key] = node
    node.Value = value
    node.Key = key
}

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Wrong: Bit manipulation

var findDuplicate = function(nums) {
    const size = nums.length
    const map = new Array(Math.ceil(size / 32))
    map.fill(0)

    for (let num of nums) {
        const row = Math.floor(num / 32)
        const col = num % 32
        if ((map[row] >> col) & 1) {
            return num
        }
        map[row] ^= 1 << col
    }
    return -1;
};

Floyd’s Tortoise and Hare

Note: Because the problem only contains an inclusive range, we can consider the integers themselves as pointers to other positions in the array. This becomes a linked-list cycle detection problem.

It’s pretty tricky as well, because it’s not a matter of doing a single cycle of the FTH algorithm, but instead requires a second loop from the first point of intersection and the start of the list.

var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;
    while (true) {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if (slow === fast) {
            break
        }
    }

    let restart = 0;
    while (true) {
        restart = nums[restart]
        slow = nums[slow]
        if (restart === slow) {
            break
        }
    }
    return slow
};

Two Sum II

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            n = numbers[left] + numbers[right]
            if n < target:
                left += 1
            elif n > target:
                right -= 1
            else:
                return [left + 1, right + 1]
        
        return []

Container with Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        right = len(height) - 1
        left = 0
        area = -1
        while left != right:
            h = min(height[left], height[right])
            curr = h * (right - left)
            if curr > area:
                area = curr
            if height[right] > height[left]:
                left += 1
            else:
                right -= 1
        return area

Find Minimum in Rotated Sorted Array

Crude Two-pointer

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        l = nums[left]
        r = nums[right]

        if l <= r:
            return l

        while l > r and left <= right:
            mid = left + (right - left) // 2
            m = nums[mid]
            if m > l:
                left = mid
            else:
                right = mid
            l = nums[left]
            r = nums[right]
        return nums[right + 1]

Partition Point

def partition_point(nums):
    start = 0
    end = len(nums) - 1
    while end >= start:
        i = start + (end - start) // 2
        if nums[i - 1] > nums[i]:
            return i
        if nums[i] < nums[0]:
            end = i - 1
        else:
            start = i + 1
    return start % len(nums)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        return nums[partition_point(nums)]

Reorder List

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    next, tail := splitTail(head.Next)
    reorderList(tail)
    head.Next = next
    if head.Next != nil {
        head.Next.Next = tail
    }
}

func splitTail(head *ListNode) (*ListNode, *ListNode) {
    var prev *ListNode
    var newHead *ListNode = head
    curr := head
    for curr.Next != nil {
        prev = curr
        curr = curr.Next
    }
    if prev != nil {
        prev.Next = nil
    }
    if (newHead == curr) {
        newHead = nil
    }
    return curr, newHead
}

Note: A better way to do this is with a combination of multiple techniques: a fast and slow pointer to detect a halfway point, reversing the second half of the list, merging the two lists.

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Find halfway point
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    // Reverse second half of list
    var prev *ListNode = nil
    curr := slow.Next
    slow.Next = nil
    for (curr != nil) {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    // Merge two lists
    rev := prev
    curr = head
    for curr != nil {
        nextCurr := curr.Next
        curr.Next = rev
        if (rev != nil) {
            nextRev := rev.Next
            rev.Next = nextCurr
            rev = nextRev
        }
        curr = nextCurr
    }
}

Subsets

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.

Brute Force

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subs = [[]]
        for num in nums:
            newSubs = []
            for subset in subs:
                newSubs.append(subset)
                copy = subset.copy()
                copy.append(num)
                newSubs.append(copy)
            subs = newSubs
        return subs

Slightly More Elegant

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in range(0, len(nums)):
            lo = 2 ** i
            num = nums[i]
            for j in range(lo, 2 ** (i + 1)):
                copy = res[j - lo].copy()
                copy.append(num)
                res.append(copy)
        return res

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

O(m+n) Space

var setZeroes = function(matrix) {
    let rows = []
    let cols = []
    for (const m in matrix) {
        rows[m] = rows[m] || false
        for (const n in matrix[m]) {
            cols[n] = cols[n] || false
            if (!matrix[m][n]) {
                rows[m] = true
                cols[n] = true
            }
        }
    }
    for (const m in matrix) {
        for (const n in matrix[m]) {
            if (rows[m] || cols[n]) {
                matrix[m][n] = 0
            }
        }
    }
};

O(1) Space

https://leetcode.com/problems/set-matrix-zeroes/editorial/

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Index juggling

var spiralOrder = function(matrix) {
   let top = 0
   let left = 0
   let bottom = matrix.length - 1
   let right = matrix[0].length - 1
   let row = 0
   let col = 0
   let output = []
   let y = 0
   let x = 1
   while (top <= bottom && left <= right) {
       output.push(matrix[row][col])
       if (x == 1 && row == top && col == right) {
           y = 1
           x = 0
           top++
       } else if (y == 1 && row == bottom && col == right) {
           x = -1
           y = 0
           right--
       } else if (x == -1 && row == bottom && col == left) {
           y = -1
           x = 0
           bottom--
       } else if (output.length && y == -1 && row == top && col == left) {
           x = 1
           y = 0
           left++
       }
       row += y
       col += x
   }
   return output
};

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

var insert = function(intervals, newInterval) {
    let cur = [...newInterval];
    let pos;
    const output = [];
    while (pos = intervals.shift()) {
        if (cur[1] < pos[0]) {
            output.push(cur);
            cur = pos;
        } else if (cur[0] > pos[1]) {
            output.push(pos);
        } else {
            cur[0] = Math.min(cur[0], pos[0]);
            cur[1] = Math.max(cur[1], pos[1]);
        }
    }
    output.push(cur)
    return output
};

Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Linear Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maximum = 0
        curr = 0
        for num in nums:
            curr = max(curr, curr + num)
            if curr > maximum:
                maximum = curr
        return maximum

Divide and Conquer

Better way…

Maximum Average Subarray

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Note: Avoid repetitively summing subarrays when you don’t need to. Each iteration holds the previous sum, so you simply need to subtract the preceding element and add the next.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        s = sum(nums[0:k])
        m = s
        for i in range(len(nums) - k):
            s += nums[i+k] - nums[i]
            m = max(m, s)
        return m / k