Coding Challenges Reference

Kip Landergren

(Updated: )

Contents

How to Solve Problems

General Strategy

Specific Strategies for Problem Types

Arrays

Remember:

Solution process:

Binary Search

Common criteria:

Solution process:

Be aware of progamming languages that can overflow. Prefer equivalent:

mid = left + Math.floor((r-l)/2)

over:

mid = (r+l)/2

Style recommendation:

Linked Lists

Common criteria:

Solution process:

Recursive Problems

Common criteria:

Solution process:

When implementing helper:

Dynamic Programming Problems

Common criteria:

Solution process:

Breadth First Search (BFS) / Depth First Search (DFS)

Graph Problems

Terminology:
node (vertex)
edge
graph
adjacency (adjacent, neighboring)
path
cycle path that starts and ends at same node
connected path exists between; connectivity is transitive
connected component maximal (node must be included if it can be) group of nodes all connected to each other
directed
undirected
reach (reachability)
strongly connected each node can reach each other
strongly connected component
weighted / unweighted
simple
connected graph only one connected component
complete graph
acyclic graph (forest)

Storing graphs:

Sorting

n log n

Specific Techniques

Two Pointers

In some cases you can adjust both pointers at once. See Problem 234.

Sliding Window

OK, the idea with a sliding window is that you keep track of the start and end indices and then data about what you have seen in a lookup (e.g. with a map or set). Sliding window can be used most often with strings and arrays.

Performance Considerations

Computer Science

Algorithms

Data Structures

Queue
Type Linear Data Structure
Access FIFO
space O(n) O(n)
search O(n) O(n)
insert O(1) O(1)
delete (dequeue) O(1) O(1)

Stack
Type Linear Data Structure
Access LIFO

Math

Programming Techniques

Time Complexity

Language Specific Techniques

Go (golang)

Binary Search

TypeScript

How to Improve

slow brain - develop ability to create insights, which are new solutions to problems.

fast brain - use your intuition for pattern matching against old solutions: given a problem, what has worked before? will it also work here? use your gut feeling:

To develop intuition:

Intuition test strategy:

General learning method:

Get better insights:

Convergent thinking strategy:

Divergent (creative) thinking strategy:

Frequently Asked Questions (FAQ)

What is the difference between recursion and dynamic programming?

(working answer) dynamic programming is recursion with memoization

There is not really a hard and fast difference. I think of it as the following:

I guess too I think of DP when there is a purely mathematical function for expressing the transition from one state to another. When the transition needs to iterate over a range, I think of it more as recursive.

Additional Research

Google Doc of topic explanation. Recommends searching “Topic [X] tutorial”.

Resources

leetcode

README.md

# leetcode

solutions to leetcode problems

## how to solve problems

- generate problem scaffold via `leet`
- fill out `README.md`:
  - include initial thoughts
  - sketch / diagram the problem, and possible solutions
- attempt to solve, stopping only when:
  - you have lost patience
  - 90 minutes have elapsed
- on completion, fill out `README.md`
  - note `comp.t` and `comp.s` and explain why
  - consider adding total time spent
  - add tags / search terms (e.g. “easy dynamic programming”
  - update whether `[OPEN]` or `[SOLVED]`

### generate problem scaffold

```
$ ./bin/leet --language typescript --number 234 --title 'Palindrome Linked List' --url 'https://leetcode.com/problems/palindrome-linked-list/'
```

## `leet` tool

build and install:
```
$ go build -o ./bin utilities/leet/leet.go
```

problems/00001-two-sum/README.md

# [SOLVED] 1 - Two Sum

[Two Sum](https://leetcode.com/problems/two-sum/)

## notes

### first thoughts

- worst case must check every element
- array is not sorted
- numbers may be duplicated
- guaranteed only one solution
- store complement index in lookup
- confusing at first what exactly to store: `complement` or `val`?

## summary

- comp.t: O(n). worst case we must check every element once
- comp.s: O(n). our lookup stores `n` values
- trick is to think: what information am I given? what information can I derive
  from that? how does that help me get the answer?

## tags

easy array

problems/00001-two-sum/golang/solution.go

package main

import "fmt"

// [2,7,11,15], target = 9
func twoSum(nums []int, target int) []int {
	// we want to find the indices of which numbers add up to the target
	lookup := make(map[int]int)

	ind1 := -1
	ind2 := -1

	for i, val := range nums {
		complement := target - val

		if complementIndex, ok := lookup[complement]; ok {
			// we have previously passed by our complement; grab it
			ind1 = complementIndex
			ind2 = i
			break
		} else {
			// haven't seen it yet, store the index
			lookup[val] = i
		}

	}

	return []int{ind1, ind2}
}

func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}

problems/00001-two-sum/typescript/explained-solution-01.ts

function twoSum(nums: number[], target: number): number[] {
  let indices = [-1, -1];

  outer: for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (i === j) {
        /* cannot use same element twice */
        continue;
      }

      /* we have a match */
      if (nums[i] + nums[j] === target) {
        indices = [i, j];
        break outer;
      }
    }
  }

  return indices;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));

export {};

problems/00001-two-sum/typescript/explained-solution-02-5.ts

/* uses insight from nums[j] === target - nums[i] */
/* which can be rewritten as: complement === target - nums[i] */
function twoSum(nums: number[], target: number): number[] {
  let indices = [-1, -1];

  outer: for (let i = 0; i < nums.length - 1; i++) {
    const complement = target - nums[i];

    /* search remaining for complement index */
    for (let j = i + 1; j < nums.length; j++) {
      /* we have a match */
      if (nums[j] === complement) {
        indices = [i, j];
        break outer;
      }
    }
  }

  return indices;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));

export {};

problems/00001-two-sum/typescript/explained-solution-02.ts

function twoSum(nums: number[], target: number): number[] {
  let indices = [-1, -1];

  outer: for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      /* we have a match */
      if (nums[i] + nums[j] === target) {
        indices = [i, j];
        break outer;
      }
    }
  }

  return indices;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));

export {};

problems/00001-two-sum/typescript/explained-solution-03.ts

/* to improve: we know necessarily that we have to read all values in worst
case, so this should clue you into using a for loop */

/* we want to know: */
/* 1) does complement exist in nums? (want O(1) check) */
/* 2) if it does, what is its index */

/* doing a second (or third) pass through `nums` is not a problem: O(2n) is still O(n) */
function twoSum(nums: number[], target: number): number[] {
  let indices = [-1, -1];

  /* build lookup */
  const lookup = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    lookup.set(nums[i], i);
  }

  /* note: could use reduce, but I encourage use of for loops for their
  flexibility should you need to break out / change logic quickly */

  /* find indices */
  for (let i = 0; i < nums.length - 1; i++) {
    const complement = target - nums[i];

    /* search lookup for complement index */
    const maybeComplementIndex = lookup.get(complement);

    if (maybeComplementIndex !== undefined && maybeComplementIndex !== i) {
      /* we found it! */
      indices = [i, maybeComplementIndex];
      break;
    }
  }

  return indices;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));

export {};

problems/00001-two-sum/typescript/explained-solution-04.ts

/* build as you go */
function twoSum(nums: number[], target: number): number[] {
  let indices = [-1, -1];

  const lookup = new Map<number, number>();

  /* note the change in i bounds here: we must iterate through all elements of nums */
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    const maybeComplementIndex = lookup.get(complement);

    if (maybeComplementIndex === undefined) {
      /* it could be some future value's complement */
      lookup.set(nums[i], i);
      continue;
    }

    /* we found it. no need to compare whether index is same because it is
    impossible to occur */
    indices = [maybeComplementIndex, i];
    break;
  }

  return indices;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));

export {};

problems/00001-two-sum/typescript/solution.ts

/* [2,7,11,15], target = 9 */
function twoSum(nums: number[], target: number): number[] {
  const lookup = new Map<number, number>();

  /* 0 start: val=2, c=7, lookup={} */
  /* 0 end: val=2, c=7, lookup={2: 0} */
  /* 1 start: val=7, c=2, lookup={2:0} */
  for (let i = 0; i < nums.length; i++) {
    const val = nums[i];

    const desiredComplement = target - val;
    const seenComplement = lookup.get(desiredComplement);

    /* have we seen the complement that would produce target before? */
    if (seenComplement === undefined) {
      /* we have not seen its complement, so store the value */
      lookup.set(val, i);
    } else {
      return [seenComplement, i];
    }
  }

  return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9));

export {};

problems/00002-add-two-numbers/README.md

# [SOLVED] 2 - Add Two Numbers

[Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)

## notes

### first thoughts

- no guarantee that `l1` and `l2` are the same length. no matter what though,
  the ones place, tens, place, etc will always be consistent
- add the values of each, have some carry forward, and advance both until both
  nil
- having trouble getting clean logic for iteration to create `sum`

## summary

- had a very hard time getting the order of operations correct for attaching the
  `Next` pointer correctly
- did not correctly handle the last digit (when `carryForward` is non-zero)
- looked at solutions after submission and cleaned up for loop condition to
  include `carryForward != 0`
- golang implementation at 44% cpu / 40% memory but not seeing major
  implementation differences in solutions
- comp.t: O(m + n): we need to walk both `l1` and `l2`
- comp.s: O(max(m, n)): our `sum` is the length of our longest input + 1

## tags

medium linked list

problems/00002-add-two-numbers/golang/solution.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

// l1 = [2,4,3], l2 = [5,6,4]
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	currDigit1 := l1
	currDigit2 := l2

	var sum *ListNode
	var prevSumDigit *ListNode

	carryForward := 0

	for currDigit1 != nil || currDigit2 != nil || carryForward != 0 {
		// calculate it
		curr1Val := 0
		curr2Val := 0

		if currDigit1 != nil {
			curr1Val = currDigit1.Val
			currDigit1 = currDigit1.Next
		}

		if currDigit2 != nil {
			curr2Val = currDigit2.Val
			currDigit2 = currDigit2.Next
		}

		total := curr1Val + curr2Val + carryForward

		val := total % 10
		carryForward = total / 10

		// we have the ability to add a new link. create it.
		next := &ListNode{Val: val}

		// add it
		if prevSumDigit == nil {
			// special case: we want to keep a pointer `sum` to the head of the list,
			// so point it to the first `next` we encounter
			sum = next
		} else {
			// otherwise update the previous digits pointer to the one we are working with
			prevSumDigit.Next = next
		}

		prevSumDigit = next
	}

	return sum
}

func main() {
	fmt.Println(addTwoNumbers(ListNodeFrom("[2,4,3]"), ListNodeFrom("[5,6,4]")))
	fmt.Println(addTwoNumbers(ListNodeFrom("[0]"), ListNodeFrom("[0]")))
	fmt.Println(addTwoNumbers(ListNodeFrom("[9,9,9,9,9,9,9]"), ListNodeFrom("[9,9,9,9]")))
}

problems/00002-add-two-numbers/typescript/solution.ts

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const sum = new ListNode();
  let prev = null;

  let currDigit1 = l1;
  let currDigit2 = l2;

  let carryForward = 0;

  while (currDigit1 || currDigit2 || carryForward != 0) {
    const curr1Val = currDigit1?.val ?? 0;
    const curr2Val = currDigit2?.val ?? 0;

    const total = curr1Val + curr2Val + carryForward;

    const val = total % 10;
    carryForward = Math.floor(total / 10);

    if (prev === null) {
      /* special case */
      sum.val = val;
      prev = sum;
    } else {
      const next = new ListNode(val);
      prev.next = next;
      prev = next;
    }

    currDigit1 = currDigit1?.next ?? null;
    currDigit2 = currDigit2?.next ?? null;
  }

  return sum;
}

export {};

problems/00003-longest-substring-without-repeating-characters/README.md

# [SOLVED] 3 - Longest Substring Without Repeating Characters

[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

## notes

## summary

## tags

medium string

problems/00003-longest-substring-without-repeating-characters/typescript/solution.ts

function lengthOfLongestSubstring(s: string): number {
  if (s.length === 0) {
    return 0;
  }

  if (s.length === 1) {
    return 1;
  }

  /* the length of our unique substring is the distance between our windowStart and windowEnd indices */

  const lookup = new Map<string, number>();

  let maxLength = 0;
  let windowStart = 0;

  for (let windowEnd = 0; windowEnd < s.length; windowEnd++) {
    const char = s[windowEnd];

    const maybeStart = lookup.get(char) ?? -1;
    if (windowStart <= maybeStart) {
      /* we have seen it. move window_start to it + 1 */
      windowStart = maybeStart + 1;
    }

    const subStringLength = windowEnd - windowStart + 1;

    if (maxLength < subStringLength) {
      maxLength = subStringLength;
    }

    lookup.set(char, windowEnd);
  }

  return maxLength;
}

export {};

problems/00004-median-of-two-sorted-arrays/README.md

# [SOLVED] 4 - Median of Two Sorted Arrays

[Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)

## notes

## summary

- comp.t: O(m+n)
- comp.s: O(m+n)

## tags

hard array

problems/00004-median-of-two-sorted-arrays/typescript/solution.ts

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  if (nums1.length === 0 && nums2.length === 0) {
    return 0;
  }

  let median = 0;

  let i = 0;
  let j = 0;

  const merged = [];

  while (i < nums1.length || j < nums2.length) {
    /* i = 0, 1, 1 */
    /* j = 0, 0, 1 */

    let n1 = nums1[i]; /* 1, 3, 3 */
    let n2 = nums2[j]; /* 2, 2, u */

    let added = 0;

    if (n1 === undefined) {
      added = n2;
      j++;
    } else if (n2 === undefined) {
      added = n1;
      i++;
    } else {
      added = n1 <= n2 ? n1 : n2; /* 1, 2, 3 */

      if (n1 <= n2) {
        i++;
      } else {
        j++;
      }
    }

    merged.push(added); /* [1, 2, 3] */
  }

  if (merged.length % 2 === 0) {
    const midIndex = merged.length / 2;
    median = (merged[midIndex - 1] + merged[midIndex]) / 2;
  } else {
    median = merged[Math.floor(merged.length / 2)];
  }

  return median;
}

export {};

problems/00005-longest-palindromic-substring/README.md

# [SOLVED] 5 - Longest Palindromic Substring

[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)

## notes

## summary

## tags

medium array

problems/00005-longest-palindromic-substring/typescript/solution.ts

function longestPalindrome(s: string): string {
  if (s.length === 1) {
    return s;
  }

  if (s.length === 2) {
    if (s[0] === s[1]) {
      return s;
    } else {
      return s[0];
    }
  }

  let longest = "";

  /* the idea here is that a palindrome starts from a "seed" of either two
  consecutive same letters (e.g. "aa") or three letters where the first and
  third are the same (e.g. "aba"). we want to find all of these seeds within
  the string and then, for each, "grow" the potential palindrome start and end
  indices by 1 until we have determined the maximum length */
  const seedIndices = [];

  for (let i = 0, j = 1, k = 2; k < s.length; i++) {
    j = i + 1;
    k = j + 1;

    const c_i = s[i];
    const c_j = s[j];
    const c_k = s[k];

    /* case: two consecutive same (e.g. "aa") */
    if (c_i === c_j) {
      seedIndices.push([i, j]);
    }

    /* case: three consecutive where first and third are same (e.g. "aba") */
    if (c_i === c_k) {
      seedIndices.push([i, k]);
    }
  }

  /* seed indices in hand, "grow" them by moving their start and end values
  until we have determined longest */
  for (let [start, end] of seedIndices) {
    let candidateStart = start - 1;
    let candidateEnd = end + 1;

    let c_s = s[candidateStart];
    let c_e = s[candidateEnd];

    while (0 <= candidateStart && candidateEnd < s.length && c_s === c_e) {
      start -= 1;
      end += 1;

      candidateStart = candidateStart - 1;
      candidateEnd = candidateEnd + 1;

      c_s = s[candidateStart];
      c_e = s[candidateEnd];
    }

    const maybeLongest = s.slice(start, end + 1);

    if (longest.length < maybeLongest.length) {
      longest = maybeLongest;
    }
  }

  /* case: we have found no palindromes, just choose the first letter */
  if (longest === "") {
    longest = s[0];
  }

  return longest;
}

export {};

problems/00007-reverse-integer/README.md

# [SOLVED] 7 - Reverse Integer

[Reverse Integer](https://leetcode.com/problems/reverse-integer/)

## notes

### first thoughts

- convert the number to a string, then try to convert to a 32 bit int and stop
  if that fails
- needs to handle a negative sign
- cast to string, split into list of chars, remove negative sign if
  present. this is now the value in ones, tens, etc that we need to check if
  outside bounds. create bounds that are the upper bound, converted to list of
  chars, with sign removed, and reversed. use this to verify that each place is
  less than the other.
- I guess the logic is simpler: only check if outside of bounds if length is
  equal to bound. if greater fail. if less succeed.
- need to remove leading zeros from any reversal

## summary

- annoying problem

## tags

problems/00007-reverse-integer/typescript/solution.ts

function reverse(x: number): number {
  /* cheeky: convert to string, split on chars, reverse, convert to number and
  check bounds */

  const isPositive = 0 <= x;

  const stringOriginalNum = String(Math.abs(x));
  const reversedDigits = stringOriginalNum.split("").reverse();

  /* remove leading zeros */
  while (reversedDigits[0] === "0") {
    reversedDigits.shift();
  }

  /* handle case where we were passed 0 */
  if (reversedDigits.length === 0) {
    return 0;
  }

  const min = String(Math.pow(2, 31)).split("");
  const max = String(Math.pow(2, 31) - 1).split("");

  /* want to check if transformedDigits is greater than min and less than max,
  but, important: the description states: "Assume the environment does not
  allow you to store 64-bit integers (signed or unsigned)." so we must compare
  digit by digit rather than using Number.parseInt for the whole value */
  let transformedDigits = reversedDigits;

  const bound = isPositive ? max : min;

  if (transformedDigits.length < bound.length) {
    /* we are OK */
  } else if (transformedDigits.length === bound.length) {
    /* we need to compare that each new digit is less */
    for (let i = 0; i < bound.length; i++) {
      const tDigit = Number(transformedDigits[i]);
      const mDigit = Number(bound[i]);

      if (tDigit < mDigit) {
        /* our transformation is less than the max, so we have no more
        comparisons left */
        break;
      } else if (tDigit === mDigit) {
        /* continue, we don't know yet if we are less */
      } else {
        /* our transformed is greater, so we must return 0 per instructions */
        return 0;
      }
    }
  }

  /* this Number.parseInt _is_ safe within problem description because we know
  it will fit within a 32-bit signed integer */
  const absVal = Number.parseInt(reversedDigits.join(""));

  return isPositive ? absVal : absVal * -1;
}

export {};

problems/00008-string-to-integer-atoi/README.md

# [SOLVED] 8 - String to Integer (atoi)

[String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/)

## notes

- I hated implementing this lol. the test cases were tedious and super annoying.
- a bunch of solutions use `Number(x)` or `parseInt` which is no bueno

## summary

- avoid doing this

## tags

medium string

problems/00008-string-to-integer-atoi/typescript/solution.ts

const min = Math.pow(2, 31);
const max = Math.pow(2, 31) - 1;

const minDigits = String(min).split("");
const maxDigits = String(max).split("");

function myAtoi(s: string): number {
  const maybeNegativeMatch = s.match(/^\s*-?\d+/);
  const maybePosMatch = s.match(/^\s*\+?\d+/);

  if (maybeNegativeMatch === null && maybePosMatch === null) {
    return 0;
  }

  const maybeMatch =
    maybeNegativeMatch === null ? maybePosMatch : maybeNegativeMatch;

  if (maybeMatch === null) {
    return 0;
  }

  const raw = maybeMatch[0].trim().split("");

  const isNegative = raw[0] === "-";

  /* clean the sign */
  if (raw[0] === "-" || raw[0] === "+") {
    raw.shift();
  }

  /* clean any leading 0s */
  let c = raw[0];
  while (c === "0") {
    raw.shift();
    c = raw[0];
  }

  const cleaned = raw;

  if (cleaned.length === 0) {
    return 0;
  }

  /* compare to our bounds: if less or more, clamp */
  const boundDigits = isNegative ? minDigits : maxDigits;

  let digit = 0;

  if (cleaned.length < boundDigits.length) {
    /* we good */
  } else if (cleaned.length === boundDigits.length) {
    /* compare */
    for (let i = 0; i < cleaned.length; i++) {
      const cleanedDigit = cleaned[i];
      const boundDigit = boundDigits[i];

      if (cleanedDigit < boundDigit) {
        /* cleaned is smaller than our bound, no need to keep checking */
        break;
      } else if (cleanedDigit === boundDigit) {
        /* continue checking */
      } else {
        /* clamp */
        return isNegative ? -1 * min : max;
      }
    }
  } else {
    /* clamp */
    return isNegative ? -1 * min : max;
  }

  digit = Number.parseInt(cleaned.join(""));

  digit = isNegative ? -1 * digit : digit;

  return digit;
}

export {};

problems/00011-container-with-most-water/README.md

# [SOLVED] 11 - Container With Most Water

[Container With Most Water](https://leetcode.com/problems/container-with-most-water/)

## notes

### first thoughts

- `n` will be at least 2, so don’t worry about weird edge cases
- naive solution: for each value, iterate all other values and calculate
  area. this would be O(n^2).
- we do not want to sort our input
- feels like two pointers
- always move the smaller height pointer because we could hold more water if we
  encounter a higher option.
- keep track of max area as you go
- stop when the pointers cross

## summary

- comp.t: O(n) as we look at each index exactly once
- comp.s: O(1) as we just store `max`
- problem solving trick was to realize that starting at the leftmost and
  rightmost indices necessarily gives us the maximum possible width for our
  potential rectangle, so we can safely move inward and not be concerned that we
  have overlooked some larger width possibility.

## tags

medium array
medium two pointers

problems/00011-container-with-most-water/golang/solution.go

package main

import "fmt"

func maxArea(height []int) int {
	leftIndex, rightIndex := 0, len(height)-1

	max := 0

	for leftIndex < rightIndex {
		left, right := height[leftIndex], height[rightIndex]

		width := rightIndex - leftIndex

		area := min(left, right) * width

		if max < area {
			max = area
		}

		if left < right {
			leftIndex++
		} else {
			rightIndex--
		}

	}

	return max
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	fmt.Println(maxArea([]int{1, 1}))
	fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
}

problems/00011-container-with-most-water/typescript/solution.ts

function maxArea(height: number[]): number {
  let max = 0;

  let start = 0;
  let end = height.length - 1;

  /* move start and end closer to middle, calculating height as we go */
  while (start < end) {
    const left = height[start];
    const right = height[end];

    const area = Math.min(left, right) * (end - start);

    if (max < area) {
      max = area;
    }

    if (left <= right) {
      start++;
    } else {
      end--;
    }
  }

  return max;
}

export {};

problems/00013-roman-to-integer/README.md

# [SOLVED] 13 - Roman to Integer

[Roman to Integer](https://leetcode.com/problems/roman-to-integer/)

## notes

### first thoughts

- store special cases in lookup
- store normal cases in other lookup
- loop through input string chars, looking ahead by one, if special case, look
  up and advance by 2. otherwise lookup normal and advance by 1
- sum the numbers

## summary

- comp.t: O(n) for a string of length n. we must read all characters
- comp.s: O(1) + k we just store the sum and have a fixed size map
- after successful submission I looked at other implementations that were faster
  and thought this code was clearer

## tags

easy string parsing
easy array

problems/00013-roman-to-integer/golang/solution.go

package main

import (
	"fmt"
	"strings"
)

func romanToInt(s string) int {
	lookup := map[string]int{
		// normal
		"I": 1,
		"V": 5,
		"X": 10,
		"L": 50,
		"C": 100,
		"D": 500,
		"M": 1000,
		// special cases
		"IV": 4,
		"IX": 9,
		"XL": 40,
		"XC": 90,
		"CD": 400,
		"CM": 900,
	}
	sum := 0

	chars := strings.Split(s, "")

	i := 0
	for i < len(chars) {
		j := i + 1

		if j < len(chars) {
			// do we have special case?
			key := fmt.Sprint(chars[i], chars[j])
			if val, ok := lookup[key]; ok {
				sum += val
				i += 2
				continue
			}
		}

		if val, ok := lookup[chars[i]]; ok {
			sum += val
			i++
		}

	}

	return sum
}

func main() {

	fmt.Println(romanToInt("III"))
	fmt.Println(romanToInt("LVIII"))
	fmt.Println(romanToInt("MCMXCIV"))

}

problems/00013-roman-to-integer/typescript/solution.ts

const lookup = new Map<string, number>();
/* normal */
lookup.set("I", 1);
lookup.set("V", 5);
lookup.set("X", 10);
lookup.set("L", 50);
lookup.set("C", 100);
lookup.set("D", 500);
lookup.set("M", 1000);
/* special cases */
lookup.set("IV", 4);
lookup.set("IX", 9);
lookup.set("XL", 40);
lookup.set("XC", 90);
lookup.set("CD", 400);
lookup.set("CM", 900);

function romanToInt(s: string): number {
  /* read by two characters, processing via special case lookup */
  let sum = 0;
  let i = 0;
  while (i < s.length) {
    const maybeSpecial = lookup.get(s.slice(i, i + 2));

    if (maybeSpecial !== undefined) {
      sum += maybeSpecial;
      i += 2;
      continue;
    }

    const maybeBase = lookup.get(s[i]);
    if (maybeBase !== undefined) {
      sum += maybeBase;
      i += 1;
      continue;
    }
    throw new Error("cannot handle");
  }

  return sum;
}

export {};

problems/00014-longest-common-prefix/README.md

# [SOLVED] 14 - Longest Common Prefix

[Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/)

## notes

## summary

## tags

easy array

problems/00014-longest-common-prefix/typescript/solution.ts

function longestCommonPrefix(strs: string[]): string {
  const lcp = [];

  let i = 0;
  let maybeNext = strs[0][i];

  while (maybeNext !== undefined) {
    for (const s of strs) {
      if (s[i] === maybeNext) {
        /* continue */
      } else {
        return lcp.join("");
      }
    }
    lcp.push(maybeNext);
    i++;
    maybeNext = strs[0][i];
  }

  return lcp.join("");
}

export {};

problems/00015-3sum/README.md

# [SOLVED] 15 - 3Sum

[3Sum](https://leetcode.com/problems/3sum/)

## notes

## summary

## tags

medium array
medium two pointers

problems/00015-3sum/typescript/solution.ts

function threeSum(nums: number[]): number[][] {
  const sortedNums = nums.sort((a, b) => a - b); /* ascending */

  const triplets = [];

  for (let i = 0; i < sortedNums.length; i++) {
    const numI = sortedNums[i];

    if (0 < i && numI === sortedNums[i - 1]) {
      continue;
    }

    let left = i + 1;
    let right = sortedNums.length - 1;

    while (left < right) {
      const numJ = sortedNums[left];
      const numK = sortedNums[right];

      const triplet = [numI, numJ, numK];

      const sum = triplet.reduce((memo, n) => {
        return memo + n;
      }, 0);

      if (sum === 0) {
        triplets.push(triplet);

        left++;
        while (left < right && sortedNums[left] === sortedNums[left - 1]) {
          left++;
        }
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return triplets;
}

export {};

problems/00017-letter-combinations-of-a-phone-number/README.md

# [SOLVED] 17 - Letter Combinations of a Phone Number

[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)

## notes

## summary

## tags

- medium dynamic programming
- medium backtrack
- medium recursive

problems/00017-letter-combinations-of-a-phone-number/typescript/solution.ts

const digitToChar = new Map<string, string[]>();

digitToChar.set("2", ["a", "b", "c"]);
digitToChar.set("3", ["d", "e", "f"]);
digitToChar.set("4", ["g", "h", "i"]);
digitToChar.set("5", ["j", "k", "l"]);
digitToChar.set("6", ["m", "n", "o"]);
digitToChar.set("7", ["p", "q", "r", "s"]);
digitToChar.set("8", ["t", "u", "v"]);
digitToChar.set("9", ["w", "y", "x", "z"]);

function letterCombinations(digits: string): string[] {
  const combinations: string[] = [];

  const backtrack = ({ i, s }: { i: number; s: string }) => {
    if (s.length === digits.length) {
      combinations.push(s);
      return;
    }

    const chars = digitToChar.get(digits[i]) ?? [];
    for (const c of chars) {
      backtrack({ i: i + 1, s: s + c });
    }
  };

  if (0 < digits.length) {
    backtrack({ i: 0, s: "" });
  }

  return combinations;
}

export {};

problems/00019-remove-nth-node-from-end-of-list/README.md

# [OPEN] 19 - Remove Nth Node From End of List

## notes

## first thoughts

get length of `head`, then loop through again , updating the (length - n)
ListNode's Next to (length - n + 1)

ahhh so the issue is that we do not know the length yet

## second thoughts

- operation will always be involving 3 ListNodes
- if `(length - n) == 0`, return `nil`
- store the modified ListNodes in a lookup using the current length as a
  key. once you reach the end, calculate `length - n`, and look up
- store the prev and next ListNodes in a lookup using the current length as a
  key
- confused about how to modify when n is equal to length

OK, so what I implemented

- walk the `ListNode`
- when the length is greater than 1, store in a lookup the current length and
  the `prev` and `next` pointers
- when you have reached the end, calculate the nthFromEnd value
- look up the nthFromEnd value in the lookup, getting `prev` and `next`
- update `prev.Next` to point to `next`
- comp.t: O(n). we walk the linked list once
- comp.s: O(n). we store 2 values for every n elements, which reduces to O(n)

## summary

## tags

medium linked list

problems/00019-remove-nth-node-from-end-of-list/golang/solution.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

// head = [1,2,3,4,5], n = 2
// [1,2,3,4,5]
//  0,1,2,3,4
// [1,2,3->5]
// updates the (length - n) Next to point to (length - n + 1)

// challenge: do it in one pass

// [1], n = 1
// 0: prev=nil, cur:1, next: nil

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return head
	}

	if head.Next == nil {
		return nil
	}

	lookup := make(map[int][]*ListNode)

	length := 0

	var prev *ListNode
	prev = nil

	cur := head
	next := cur.Next

	for cur != nil {
		length += 1

		fmt.Printf("before length=%d, prev=%v, cur=%v, next=%v\n", length, prev, cur, next)
		if prev != nil {
			lookup[length] = []*ListNode{prev, next}
		}
		fmt.Printf("%v\n", lookup)
		if _, ok := lookup[2]; ok {
			fmt.Printf("%v\n", lookup[2][0])
			fmt.Printf("%v\n", lookup[2][1])
		}

		prev = cur
		cur = next
		if cur == nil {
			next = nil
		} else {
			next = cur.Next
		}
		fmt.Printf("after length=%d, prev=%v, cur=%v, next=%v\n", length, prev, cur, next)
	}
	fmt.Printf("%v\n", lookup)

	nthFromEnd := length - n + 1
	fmt.Printf("%d\n", nthFromEnd)

	nodes, ok := lookup[nthFromEnd]
	if ok {
		first := nodes[0]
		second := nodes[1]

		fmt.Printf("%v\n", first)
		fmt.Printf("%v\n", second)

		first.Next = second
	}

	return head
}

func printable(head *ListNode) {
	var s []int

	for head != nil {
		s = append(s, head.Val)
		head = head.Next
	}

	fmt.Printf("%v\n", s)
}

func main() {
	output1 := removeNthFromEnd(ListNodeFrom("[1,2,3,4,5]"), 2)
	printable(output1)

	output2 := removeNthFromEnd(ListNodeFrom("[1]"), 1)
	printable(output2)

	output3 := removeNthFromEnd(ListNodeFrom("[1,2]"), 1)
	printable(output3)
}

problems/00020-valid-parentheses/README.md

# [SOLVED] 20 - Valid Parentheses

[Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

## notes

### first thoughts

- keep a stack for each paren type. push any open paren on. when encounter a
  closed, pop off. valid if all are empty.
- I don’t need a stack, just a count. break if it goes negative
- ugh I did not read problem fully. they need to be actually valid groupings.

## summary

- typescript implementation was done many days previous to golang
- `solution.go` comp.t: O(n) we must read every char
- `solution.go` comp.s: O(n) `record` could contain all `n` chars

## tags

easy stack

problems/00020-valid-parentheses/golang/solution.go

package main

import (
	"fmt"
	"strings"
)

func isValid(s string) bool {
	var record []string

	res := true
	for _, c := range strings.Split(s, "") {
		if c == "(" || c == "{" || c == "[" {
			// open paren always valid move
			record = append(record, c)
		} else {
			// closed paren has some caveats
			if len(record) == 0 {
				// we have not received an open, so invalid
				res = false
				break
			}

			// top must be the corresponding open paren
			top := record[len(record)-1]
			if top == "(" && c != ")" {
				res = false
				break
			} else if top == "{" && c != "}" {
				res = false
				break
			} else if top == "[" && c != "]" {
				res = false
				break
			}

			// we are good, remove the last
			record = record[:len(record)-1]
		}
	}

	return res && len(record) == 0
}

func main() {
	fmt.Println(isValid("()"))
	fmt.Println(isValid("()[]{}"))
	fmt.Println(isValid("(]"))
	fmt.Println(isValid("([)]"))
	fmt.Println(isValid("["))
}

problems/00020-valid-parentheses/typescript/solution.ts

const openParenLookup = new Map<string, string>();
openParenLookup.set("(", ")");
openParenLookup.set("{", "}");
openParenLookup.set("[", "]");

const closedParenLookup = new Map<string, string>();
closedParenLookup.set(")", "(");
closedParenLookup.set("}", "{");
closedParenLookup.set("]", "[");

function isValid(s: string): boolean {
  if (s.length % 2 !== 0) {
    return false;
  }

  /* idea: read characters from string, push val if open paren, pop if close
  paren, if popped value does not work we stop */

  const record: string[] = [];

  for (const paren of s.split("")) {
    if (openParenLookup.has(paren)) {
      /* we know it is an open */
      record.push(paren);
      continue;
    }

    /* it is a closed paren, lets 1) make sure we find it and 2) make sure it
    matches */
    const maybeMatchingOpenParen = closedParenLookup.get(paren);

    if (maybeMatchingOpenParen === undefined) {
      throw new Error(`unknown paren: ${paren}`);
    }

    const last = record.pop();
    if (last === undefined) {
      return false;
    }

    if (last === maybeMatchingOpenParen) {
      continue;
    }

    return false;
  }

  return record.length === 0;
}

console.log(isValid("()"));
console.log(isValid("()[]{}"));
console.log(isValid("(]"));
console.log(isValid("]"));
console.log(isValid("(()"));
console.log(isValid("(((("));

export {};

problems/00021-merge-two-sorted-lists/README.md

# [SOLVED] 21 - Merge Two Sorted Lists

[Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)

## notes

### first thoughts

- recursive
- check for which val is less. update that `.Next` to point to the result of
  `mergeTwoLists`
- handle base cases of either being `nil`
- comp.t: O(n + m). we must walk each `ListNode`.
- comp.s: O(n + m). we must create a new `ListNode` of length `n + m`.

## summary

accepted solution. 100% runtime. 59% memory.

Key here was the “recursive leap of faith” to think: assuming that we can
determine which `ListNode` goes first, a function `mergeToLists` exists that
will sort whatever is remaining.

I found it helpful to think of it like:

```
determine which of the following values is less:
     __
ln1: |1|->2->4
ln2: |2|->3->4

which then creates the start of our result:

res: 1

and then draw a box around the remainder of the problem:
        _____
ln1: ____|2->4|
ln2: |2 ->3->4|

which fits for the args to `mergeTwoLists`

```

## tags

easy linked list
easy recursive

problems/00021-merge-two-sorted-lists/golang/solution.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	var s []int

	for ln != nil {
		s = append(s, ln.Val)
		ln = ln.Next
	}

	return fmt.Sprintf("%v", s)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}

	if list2 == nil {
		return list1
	}

	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}

}

func printable(head *ListNode) {
	var s []int

	for head != nil {
		s = append(s, head.Val)
		head = head.Next
	}

	fmt.Printf("%v\n", s)
}

func main() {
	printable(mergeTwoLists(ListNodeFrom("[1,2,4]"), ListNodeFrom("[1,3,4]")))
	printable(mergeTwoLists(ListNodeFrom("[]"), ListNodeFrom("[]")))
	printable(mergeTwoLists(ListNodeFrom("[]"), ListNodeFrom("[0]")))

}

problems/00022-generate-parentheses/README.md

# [SOLVED] 22 - Generate Parentheses

[Generate Parentheses](https://leetcode.com/problems/generate-parentheses/)

## notes

### first thoughts

- dynamic programming
- maybe state being remaining open and closed parens
- a closed paren must have a corresponding open paren
- we only have one option on our first move. how to reflect this? I keep wanting
  to iterate through each of the `n` parens, but the case is handled by just
  including one

```
n=1 ()
n=2

0: (
1: (),  ((,
2: ()(, (((, ((),
3: ()((, ()(), (((), (()(, (())

```

### second thoughts

- recursion, not dynamic programming (we are not caching data)
- you have *two options* at each branch in the tree: either add an `(` or add an
  `)`
- the ability to do one or the other is determined by however many valid options
  remain
- therefore state is the current permutation `perm`, `remainingOpen`, and
  `remainingClosed`
- recursive leap of faith: assume `helper` will give you a list of possible
  strings

## summary

for `solution.go`:

- comp.t: O(2^n). at every character index we have 2 options (open or closed).
- comp.s: O(n). the height of the recursive tree is `2 * n`, which reduces to
  O(n). this space complexity refers to the height of the stack generated from
  the solution approach, not the amount of characters in each permutation or the
  number of permutations.
- I missed that the length of `perm` is necessarily `2 * n` because for every
  `n` open parens there must be `n` closed parens.
- key realization here was that at each index of the permutation string you have
  two options: either add an `(` or add an `)`.

for `solution-dynamic-programming.go`:

added a second approach using dynamic programming with memoization that caches
each set of permutations at n. comp.t is now O(n) because we memoize the result
of the computation. now 100% for runtime.

## tags

medium recursion
medium dynamic programming

problems/00022-generate-parentheses/golang/solution-dynamic-programming.go

package main

import "fmt"

func helper(remainingOpen int, remainingClosed int, lookup map[string][]string) []string {
	key := fmt.Sprintf("%d-%d", remainingOpen, remainingClosed)

	permutations, ok := lookup[key]
	if ok {
		return permutations
	}

	var result []string

	// add open
	if 1 <= remainingOpen {
		for _, perm := range helper(remainingOpen-1, remainingClosed+1, lookup) {
			result = append(result, "("+perm)
		}
	}

	// add closed
	if 1 <= remainingClosed {
		for _, perm := range helper(remainingOpen, remainingClosed-1, lookup) {
			result = append(result, ")"+perm)
		}
	}

	lookup[key] = result

	return lookup[key]
}

func generateParenthesis(n int) []string {
	lookup := make(map[string][]string)

	// base cases
	lookup["0-0"] = []string{}
	lookup["1-0"] = []string{"()"}
	lookup["0-1"] = []string{")"}

	return helper(n, 0, lookup)
}

func main() {
	fmt.Println(generateParenthesis(0))
	fmt.Println(generateParenthesis(1))
	fmt.Println(generateParenthesis(2))
	fmt.Println(generateParenthesis(3))
}

problems/00022-generate-parentheses/golang/solution.go

package main

import "fmt"

// we have two options: either add an open or add a closed
func helper(perm string, remainingOpen int, remainingClosed int) []string {
	var result []string

	if remainingOpen == 0 && remainingClosed == 0 {
		// we are done
		result = append(result, perm)
	} else if 0 < remainingOpen && remainingClosed == 0 {
		// can only add an open
		result = append(result, helper(fmt.Sprint(perm, "("), remainingOpen-1, remainingClosed+1)...)
	} else if remainingOpen == 0 && 0 < remainingClosed {
		// can only add a closed
		result = append(result, helper(fmt.Sprint(perm, ")"), remainingOpen, remainingClosed-1)...)
	} else {
		// can both add an open and add a closed
		result = append(result, helper(fmt.Sprint(perm, "("), remainingOpen-1, remainingClosed+1)...)
		result = append(result, helper(fmt.Sprint(perm, ")"), remainingOpen, remainingClosed-1)...)
	}

	return result
}

func generateParenthesis(n int) []string {
	return helper("", n, 0)
}

func main() {
	fmt.Println(generateParenthesis(0))
	fmt.Println(generateParenthesis(1))
	fmt.Println(generateParenthesis(2))
	fmt.Println(generateParenthesis(3))
}

problems/00022-generate-parentheses/typescript/solution.ts

function generateParenthesis(n: number): string[] {
  /* I want a function that will add all the possible strings to a combos I pass in */

  const helper = (
    numOpenAvail: number,
    numClosedAvail: number,
    currentCombo: string,
    combos: string[]
  ) => {
    if (numOpenAvail === 0 && numClosedAvail === 0) {
      /* we are done */
      combos.push(currentCombo);
    }

    /* two choices: either add an open or closed */
    if (0 < numOpenAvail) {
      helper(numOpenAvail - 1, numClosedAvail + 1, currentCombo + "(", combos);
    }

    if (0 < numClosedAvail) {
      helper(numOpenAvail, numClosedAvail - 1, currentCombo + ")", combos);
    }
  };

  const output: string[] = [];
  helper(n, 0, "", output);
  return output;
}

console.log(generateParenthesis(3));
console.log(generateParenthesis(1));

export {};

problems/00023-merge-k-sorted-lists/README.md

# [SOLVED] 23 - Merge k Sorted Lists

[Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)

## notes

### first thoughts

- naive solution would be to scan back and forth through the lists, building the
  ListNode
- thought that I wanted to read each list once, so I figured I could stuff each
  number into its own queue in a `record` slice (with the number corresponding
  to the index of `record`). I added an offset based on the contraints.
- the solution was accepted and 50th percentile fast but not in the spirit of
  the problem.
- I did think “each list is already sorted, so is there a way I can use that to
  my advantage?”. I think this is what the example hints were trying to show:
  that if list is length 1 you already have your answer. So a more in-spirit
  approach is to take the first list, merge it with i + 1, then merge that
  result with i+2. this walks nodes multiple times so I am surprised it is
  faster.
- an optimization I could do to my current approach is to use `[]*int` and just
  increment rather than append

### optimization via int pointers

- did this and got to 90th percentile. still not spirit of the problem

### recursive optimization

- got 36th percentile, which surprised me as I thought this would be more
  efficient. will try iterative approach.

### iterative optimization

- got 33rd percentile, which also surprised me because this is basically the
  approach that the top performing implementations did. maybe there is some
  difference I am missing.

## summary

- (int pointer impl) comp.t: O(n) for the number of nodes total in k lists
- (int pointer impl) comp.s: O(1) because of constraints

## tags

problems/00023-merge-k-sorted-lists/golang/solution-1-record-slice.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
	"math"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

// original first pass solution
func mergeKLists(lists []*ListNode) *ListNode {
	offset := int(math.Pow(10, 4))

	record := make([][]int, offset*2)

	for _, node := range lists {
		for node != nil {
			record[node.Val+offset] = append(record[node.Val+offset], node.Val)
			node = node.Next
		}
	}

	var tail *ListNode
	for i := len(record) - 1; 0 <= i; i-- {
		if len(record[i]) != 0 {
			for _, val := range record[i] {
				prev := &ListNode{Val: val, Next: tail}
				tail = prev
			}
		}
	}

	return tail
}

func main() {
	fmt.Println(mergeKLists(ListNodesFrom("[[1,4,5],[1,3,4],[2,6]]")))
	fmt.Println(mergeKLists(ListNodesFrom("[]")))
	fmt.Println(mergeKLists(ListNodesFrom("[[]]")))
}

problems/00023-merge-k-sorted-lists/golang/solution-2-int-ptr.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
	"math"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

// optimized *int solution
func mergeKLists(lists []*ListNode) *ListNode {
	offset := int(math.Pow(10, 4))

	record := make([]*int, offset*2)

	for _, node := range lists {
		for node != nil {
			var sum *int
			sum = new(int)
			if record[node.Val+offset] == nil {
				*sum = 1
			} else {
				*sum = 1 + *record[node.Val+offset]
			}
			record[node.Val+offset] = sum
			node = node.Next
		}
	}

	var tail *ListNode
	for i := len(record) - 1; 0 <= i; i-- {
		if record[i] != nil {
			amt := *record[i]

			for j := 0; j < amt; j++ {
				prev := &ListNode{Val: i - offset, Next: tail}
				tail = prev
			}

		}
	}

	return tail
}

func main() {
	fmt.Println(mergeKLists(ListNodesFrom("[[1,4,5],[1,3,4],[2,6]]")))
	fmt.Println(mergeKLists(ListNodesFrom("[]")))
	fmt.Println(mergeKLists(ListNodesFrom("[[]]")))
}

problems/00023-merge-k-sorted-lists/golang/solution-3-recursive.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

// idea: reduce problem to merging two lists, and then minimize the number of
// updates by walking the primary list until the alternate has a lower value
func mergeKLists(lists []*ListNode) *ListNode {
	var list1 *ListNode
	var list2 *ListNode

	// base cases
	if len(lists) == 0 {
		return nil
	} else if len(lists) == 1 {
		return lists[0]
	} else if len(lists) == 2 {
		list1 = lists[0]
		list2 = lists[1]
	} else {
		list1 = lists[0]
		list2 = mergeKLists(lists[1:])
	}

	if list1 == nil {
		return list2
	}

	if list2 == nil {
		return list1
	}

	// do the actual merging
	var primary *ListNode
	var alternate *ListNode

	// choose primary being the one with the lower starting value
	if list1.Val < list2.Val {
		primary = list1
		alternate = list2
	} else {
		primary = list2
		alternate = list1
	}

	head := &ListNode{}
	head.Next = primary

	for alternate != nil {
		if primary.Next == nil {
			// we are done. there are no more nodes on primary and we know that
			// alternate contains greater vals
			primary.Next = alternate
			break
		}

		// look ahead to our next value, should we instead insert alternate?
		if primary.Next.Val <= alternate.Val {
			// nope, we should just keep moving primary forward
			primary = primary.Next
		} else {
			// yes, we should insert alternate
			oldPrimaryNext := primary.Next
			primary.Next = alternate
			alternate = oldPrimaryNext
		}

	}

	return head.Next
}

func main() {
	fmt.Println(mergeKLists(ListNodesFrom("[[1,4,5],[1,3,4],[2,6]]")))
	fmt.Println(mergeKLists(ListNodesFrom("[]")))
	fmt.Println(mergeKLists(ListNodesFrom("[[]]")))
}

problems/00023-merge-k-sorted-lists/golang/solution-4-iterative.go

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

func (ln *ListNode) String() string {
	return fmt.Sprintf("%v, %v", ln.Val, ln.Next)
}

func ListNodeFromVals(vals []int) *ListNode {
	holder := &ListNode{}
	head := holder

	for _, val := range vals {
		head.Next = &ListNode{Val: val}
		head = head.Next
	}

	return holder.Next
}

func ListNodeFrom(s string) *ListNode {
	var vals []int
	err := json.Unmarshal([]byte(s), &vals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	return ListNodeFromVals(vals)
}

func ListNodesFrom(s string) []*ListNode {
	var nodeVals [][]int
	err := json.Unmarshal([]byte(s), &nodeVals)
	if err != nil {
		log.Fatalln("trying to build ListNode:", err)
	}

	var output []*ListNode
	for _, nodeVal := range nodeVals {
		output = append(output, ListNodeFromVals(nodeVal))
	}

	return output
}

func merge2Lists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}

	if list2 == nil {
		return list1
	}

	// do the actual merging
	var primary *ListNode
	var alternate *ListNode

	// choose primary being the one with the lower starting value
	if list1.Val < list2.Val {
		primary = list1
		alternate = list2
	} else {
		primary = list2
		alternate = list1
	}

	head := &ListNode{}
	head.Next = primary

	for alternate != nil {
		if primary.Next == nil {
			// we are done. there are no more nodes on primary and we know that
			// alternate contains greater vals
			primary.Next = alternate
			break
		}

		// look ahead to our next value, should we instead insert alternate?
		if primary.Next.Val <= alternate.Val {
			// nope, we should just keep moving primary forward
			primary = primary.Next
		} else {
			// yes, we should insert alternate
			oldPrimaryNext := primary.Next
			primary.Next = alternate
			alternate = oldPrimaryNext
		}

	}

	return head.Next
}

// idea: reduce problem to merging two lists, and then minimize the number of
// updates by walking the primary list until the alternate has a lower value
func mergeKLists(lists []*ListNode) *ListNode {
	// base cases
	if len(lists) == 0 {
		return nil
	}

	if len(lists) == 1 {
		return lists[0]
	}

	// find the first non-nil list
	primaryIndex := 0
	for primaryIndex < len(lists)-1 && lists[primaryIndex] == nil {
		primaryIndex += 1
	}

	head := lists[primaryIndex]
	for i := primaryIndex + 1; i < len(lists); i++ {
		head = merge2Lists(head, lists[i])
	}

	return head
}

func main() {
	fmt.Println(mergeKLists(ListNodesFrom("[[1,4,5],[1,3,4],[2,6]]")))
	fmt.Println(mergeKLists(ListNodesFrom("[]")))
	fmt.Println(mergeKLists(ListNodesFrom("[[]]")))
}

problems/00026-remove-duplicates-from-sorted-array/README.md

# [SOLVED] 26 - Remove Duplicates from Sorted Array

[Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

## notes

### first thoughts

- keep track of the current number’s index `i`
- advance `k` steps, where `k=1` and increments by 1
- if the `i + k` number is the same as `nums[i]`, advance
- if the `i + k` number is greater than `nums[i]`, increment `i`, insert the
  number into `nums[i]` and repeat

## summary

- comp.t: O(n) we must examine every element
- comp.s: O(1) we replace values in place
- I need to read the constraints better as `nums.length` will always be greater
  than or equal to 1.

## tags

easy array

problems/00026-remove-duplicates-from-sorted-array/golang/solution.go

package main

import "fmt"

func removeDuplicates(nums []int) int {
	k := 0

	for _, num := range nums {
		if nums[k] < num {
			k++
			nums[k] = num
		}
	}

	return k + 1
}

func main() {
	fmt.Println(removeDuplicates([]int{1}))
	fmt.Println(removeDuplicates([]int{1, 1}))
	fmt.Println(removeDuplicates([]int{1, 1, 2}))
	fmt.Println(removeDuplicates([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}))
}

problems/00033-search-in-rotated-sorted-array/README.md

# [SOLVED] 33 - Search in Rotated Sorted Array

[Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/)

## notes

### first thoughts

- ascending, distinct values
- alg must run in O(log n) (e.g. no sorting)
- smells like binary search. modified version of it.
- idea. find the pivot point, then modify search based on that.
- I think we can just implement a modified version of binary search that starts
  with bounds check? e.g. check 0 and check length - 1?, then choose the middle?
- I think finding the pivot, then searching within each makes more intuitive
  sense.

## summary

- comp.t: O(log n) in either implementation due to binary search
- comp.s: O(1) just storing the targetIndex
- OK, a couple things: getting the pivot search correct was difficult, not all
  test cases were actually rotated, and I think the logic ends up getting more
  convoluted because of all of these conditions. I submitted a working solution
  and looked at the other responses and saw that they essentially break the
  problem down into whether or not you are searching in the sorted left half or
  the sorted right half, and just ignore the discontinuity. I will try this
  implementation.
- I implemented the special-case logic and think it is both more complex and
  harder to reason about.

## tags

medium array
medium binary search
medium two pointers

problems/00033-search-in-rotated-sorted-array/golang/solution.go

package main

import "fmt"

func search(nums []int, target int) int {
	l, r := 0, len(nums)-1

	t := -1
	for l <= r {
		m := l + (r-l)/2

		if nums[m] == target {
			t = m
			break
		}

		if nums[l] <= nums[m] {
			if nums[m] < target {
				l = m + 1
			} else if target < nums[l] {
				l = m + 1
			} else {
				r = m - 1
			}
		} else {
			if target < nums[m] {
				r = m - 1
			} else if nums[r] < target {
				r = m - 1
			} else {
				l = m + 1
			}
		}

	}

	return t
}

func main() {
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 0))
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 3))
	fmt.Println(search([]int{1}, 0))
}

problems/00033-search-in-rotated-sorted-array/typescript/solution.ts

function searchViaPivotPoint(nums: number[], target: number): number {
  /* pivot happens when there is drop from large to small */

  /* find pivotIndex */
  let leftIndex = 0;
  let rightIndex = nums.length - 1;
  let pivotIndex = -1;
  while (leftIndex < rightIndex) {
    let midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);

    if (rightIndex - leftIndex === 1 && nums[rightIndex] < nums[leftIndex]) {
      pivotIndex = leftIndex;
      break;
    } else if (nums[leftIndex] < nums[midIndex]) {
      /* we overshot */
      leftIndex = midIndex;
    } else {
      rightIndex = midIndex;
    }
  }

  /*   console.log({ nums, target, pivotIndex, leftIndex, rightIndex }); */

  if (pivotIndex === -1) {
    leftIndex = 0;
    rightIndex = nums.length - 1;
  } else if (nums[0] <= target && target <= nums[pivotIndex]) {
    leftIndex = 0;
    rightIndex = pivotIndex;
  } else {
    leftIndex = pivotIndex + 1;
    rightIndex = nums.length - 1;
  }

  /* normal binary search */
  let targetIndex = -1;
  while (leftIndex <= rightIndex) {
    let midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);

    /*     console.log({ nums, target, leftIndex, rightIndex, midIndex }); */

    if (nums[midIndex] === target) {
      targetIndex = midIndex;
      break;
    } else if (nums[midIndex] < target) {
      leftIndex = midIndex + 1;
    } else {
      rightIndex = midIndex - 1;
    }
  }

  if (nums[leftIndex] === target) {
    targetIndex = leftIndex;
  }

  return targetIndex;
}

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

  let targetIndex = -1;
  while (leftIndex <= rightIndex) {
    let midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);

    if (nums[midIndex] === target) {
      targetIndex = midIndex;
      break;
    }

    if (nums[leftIndex] <= nums[midIndex]) {
      /* mid point is in the left sorted portion of the array */
      if (nums[midIndex] < target) {
        /* "somewhere" to the right of midpoint */
        leftIndex = midIndex + 1;
      } else if (target < nums[leftIndex]) {
        /* there is no way we missed it because we started left at 0, so this
        is also "somewhere" to the right of mid point */
        leftIndex = midIndex + 1;
      } else {
        /* it is in between our leftIndex and midIndex */
        rightIndex = midIndex - 1;
      }
    } else {
      /* mid point is in the right sorted portion of the array */
      if (target < nums[midIndex]) {
        /* target is "somewhere" to the left of the midpoint */
        rightIndex = midIndex - 1;
      } else if (nums[rightIndex] < target) {
        /* there is no way we missed it because we started right at nums.length
        - 1, so this is also "somwhere" to the left of mid point */
        rightIndex = midIndex - 1;
      } else {
        /* it is in between our midIndex and rightIndex */
        leftIndex = midIndex + 1;
      }
    }
  }

  return targetIndex;
}

console.log(search([1, 3], 1));
console.log(search([1, 3, 5], 1));
console.log(search([4, 5, 6, 7, 0, 1, 2], 3));
console.log(search([1, 3, 5, 6], 1));
console.log(search([4, 5, 6, 7, 0, 1, 2], 0));
console.log(search([1], 0));
export {};

problems/00036-valid-sudoku/README.md

# [SOLVED] 36 - Valid Suduko

[Valid Suduko](https://leetcode.com/problems/valid-sudoku/)

## notes

### first thoughts

- write a validation function that takes an `[]string` and confirms it only
  encounters a non `.` key once by storing in a map
- check each row, check each column, then build each ninth section and confirm

## summary

- I wrote the typescript solution before the golang, and I honestly think I like
  it better. the logic is pretty clear and we just do a single pass of all
  numbers, short circuiting when we enter invalid state.
- comp.t: O(1) as we have a fixed set of sets to check
- comp.s: O(1) we use a lookup but it is of fixed size

## tags

medium array

problems/00036-valid-sudoku/golang/solution.go

package main

func isValid(row []byte) bool {
	lookup := make(map[byte]bool, 9)

	for _, b := range row {
		if b == '.' {
			continue
		}
		if _, ok := lookup[b]; ok {
			return false
		} else {
			lookup[b] = true
		}
	}

	return true
}

func isValidSudoku(board [][]byte) bool {
	var setsToValidate [][]byte

	// add all actual rows
	setsToValidate = append(setsToValidate, board...)

	// add all columns
	for x := 0; x < len(board[0]); x++ {
		var col []byte
		for y := 0; y < len(board); y++ {
			col = append(col, board[y][x])
		}
		setsToValidate = append(setsToValidate, col)
	}

	// add all ninth sections
	positions := []int{0, 3, 6}

	for _, py := range positions {
		for _, px := range positions {
			var section []byte
			for x := px; x < px+3; x++ {
				for y := py; y < py+3; y++ {
					section = append(section, board[y][x])
				}
			}
			setsToValidate = append(setsToValidate, section)
		}
	}

	res := true
	for _, s := range setsToValidate {
		if !isValid(s) {
			res = false
			break
		}
	}

	return res
}

func main() {

}

problems/00036-valid-sudoku/typescript/solution.ts

/* y=0 through y=8 */
/* x=0 through x=8 */
/* box 0 through 8 */
function isValidSudoku(board: string[][]): boolean {
  const lookups = new Map<string, Set<string>>();

  for (let y = 0; y < board.length; y++) {
    for (let x = 0; x < board.length; x++) {
      const keys = [];
      keys.push(`y=${y}`);
      keys.push(`x=${x}`);

      if (x <= 2 && y <= 2) {
        keys.push("box=0");
      } else if (x <= 2 && y <= 5) {
        keys.push("box=1");
      } else if (x <= 2 && y <= 8) {
        keys.push("box=2");
      } else if (x <= 5 && y <= 2) {
        keys.push("box=3");
      } else if (x <= 5 && y <= 5) {
        keys.push("box=4");
      } else if (x <= 5 && y <= 8) {
        keys.push("box=5");
      } else if (x <= 8 && y <= 2) {
        keys.push("box=6");
      } else if (x <= 8 && y <= 5) {
        keys.push("box=7");
      } else if (x <= 8 && y <= 8) {
        keys.push("box=8");
      } else {
        console.log("huh", x, y);
        return false;
      }

      const num = board[y][x];

      if (num === ".") {
        continue;
      }

      for (const key of keys) {
        const lookup = lookups.get(key);
        if (lookup === undefined) {
          lookups.set(key, new Set([num]));
        } else {
          if (lookup.has(num)) {
            return false;
          }
          lookup.add(num);
          lookups.set(key, lookup);
        }
      }
      /*       console.log({ keys, num, lookups }); */
    }
  }

  return true;
}

console.log(
  isValidSudoku([
    ["5", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
  ])
);
console.log(
  isValidSudoku([
    ["8", "3", ".", ".", "7", ".", ".", ".", "."],
    ["6", ".", ".", "1", "9", "5", ".", ".", "."],
    [".", "9", "8", ".", ".", ".", ".", "6", "."],
    ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
    ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
    ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
    [".", "6", ".", ".", ".", ".", "2", "8", "."],
    [".", ".", ".", "4", "1", "9", ".", ".", "5"],
    [".", ".", ".", ".", "8", ".", ".", "7", "9"],
  ])
);

export {};

problems/00042-trapping-rain-water/README.md

# [OPEN] 42 - Trapping Rain Water

[Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)

## notes

- in progress

## summary

## tags

problems/00042-trapping-rain-water/typescript/solution.ts

function trap(height: number[]): number {
  /* first thought: break the heights into 2d grid, then run every y value
  (every row) to determine the volume of water */

  /* - this would be O(n) to create the grid, then O(k * n) k is the largest
  value to traverse it. */

  /* make grid */
  const grid: number[][] = [[]];

  for (let x = 0; x < height.length; x++) {
    const maxY = height[x];

    for (let y = 0; y <= maxY; y++) {
      /* check if row exists */
      if (grid[y] === undefined) {
        /* no: create */
        grid[y] = [];
      }

      grid[y][x] = 1;
    }
  }

  /* traverse grid by y collecting all rainwater */
  let trappedRainWater = 0;
  for (let y = 1; y < grid.length; y++) {
    const row = grid[y];
    let indexOfWall = -1;
    for (let x = 0; x < row.length; x++) {
      const val = grid[y][x];

      if (val === 1) {
        if (indexOfWall < 0) {
          /* first wall we have found */
          indexOfWall = x;
        } else {
          /* we have a previous wall */
          trappedRainWater += x - (indexOfWall + 1);
          indexOfWall = x;
        }
      }

      /*       console.log({ x, y, val, trappedRainWater }); */
    }
  }

  /*   console.log(grid); */

  /*   console.log("trapped rainwater:", trappedRainWater); */

  return trappedRainWater;
}

trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]);
trap([4, 2, 0, 3, 2, 5]);

export {};

problems/00049-group-anagrams/README.md

# [SOLVED] 49 - Group Anagrams

[Group Anagrams](https://leetcode.com/problems/group-anagrams/)

## notes

### first thoughts

- sort letters, look up key in map, store in slice
- assume repeated letters need to also be repeated (e.g. “aa” and “a” are not
  anagraps)
- solution will be comp.t O(n) to go through every item, then O(ni log ni) to
  sort `n[i]` and comp.s O(n) to store in map
- I need to go through every string, so I am at least O(n). is there any way I
  can look up character by character without having to sort the individual
  words? can’t think of one

## summary

- comp.t: O(n) for every word, then O(c log c) for the number of characters
  sorted.
- comp.s: O(n) storing each word in a map

## tags

medium hashing

problems/00049-group-anagrams/golang/solution.go

package main

import (
	"fmt"
	"sort"
	"strings"
)

func groupAnagrams(strs []string) [][]string {
	// build lookup of anagrams
	lookup := make(map[string][]string, len(strs))
	for _, word := range strs {
		// make key
		letters := strings.Split(word, "")
		sort.Strings(letters)
		key := strings.Join(letters, "")

		// find any existing anagrams
		anagrams, ok := lookup[key]
		if !ok {
			anagrams = []string{}
		}

		// add the new one and set
		anagrams = append(anagrams, word)
		lookup[key] = anagrams

	}

	// build output
	var output [][]string
	for _, anagrams := range lookup {
		output = append(output, anagrams)
	}

	return output
}

func main() {
	fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
	fmt.Println(groupAnagrams([]string{""}))
	fmt.Println(groupAnagrams([]string{"a"}))
}

problems/00049-group-anagrams/typescript/solution.ts

const createAnagramHashKey = (s: string): string => {
  return s.split("").sort().join("");
};

/* time: O(n) */
/* space: O(n) */
function groupAnagrams(strs: string[]): string[][] {
  const lookup = strs.reduce((memo, word) => {
    const key = createAnagramHashKey(word);

    const existingWords = memo.get(key);
    if (existingWords === undefined) {
      memo.set(key, [word]);
    } else {
      existingWords.push(word);
      memo.set(
        key,
        existingWords
      ); /* TODO: not sure if I need to actually set this because existingWords is ref? */
    }

    return memo;
  }, new Map<string, string[]>());

  const output = [];

  for (const [_key, value] of lookup) {
    output.push(value);
  }

  return output;
}

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
console.log(groupAnagrams([""]));
console.log(groupAnagrams(["a"]));

export {};

problems/00051-n-queens/README.md

# [OPEN] 51 - N-Queens

[N-Queens](https://leetcode.com/problems/n-queens/)

## notes

### first thoughts

- `n` can be 1
- `n=2` has no solutions
- I could have one or more queens in the same position in two distinct
  solutions, but not all of them.
- brute force would iterate all possible positions which would be I think
  `2^(n^2)`. i.e. for every `n` you have two options queen or no queen.
- can I find a sub problem? I do not see the solution to `n=1` in the solution
  to `n=2`.
- if I brute force I can restrict the problem space by reducing the valid
  squares. e.g. `place(queen_positions, available_coords, remaining_queens)`
  which would return `queen_positions` once `remaining_queens=0`. if it comes
  back empty I know it is not possible.

### second thoughts

- what is the subproblem?
- I want helper to take a board, and number of remaining queens, and return to
  me all the possible boards
- problem. I keep getting duplicate boards being inserted and I do not know
  why. my intuition is that the lookup should prevent this.
- problem. I loop over every possible x and y value

## summary

## tags

problems/00051-n-queens/typescript/solution-2.ts

function solveNQueens(n: number): string[][] {
  const printBoard = (board: string[][]) => {
    for (const row of board) {
      console.log(row.join(""));
    }
  };

  const generateBoard = (size: number) => {
    const board: string[][] = [];

    for (let y = 0; y < size; y++) {
      board.push(Array(size).fill("."));
    }

    return board;
  };

  const keyify = (board: string[][]): string => {
    return board.map((r) => r.join("")).join("");
  };

  const checkQueens = (x: number, y: number, board: string[][]) => {
    /* vertical */
    for (let y2 = 0; y2 < board.length; y2++) {
      if (board[y2][x] === "Q") {
        return false;
      }
    }

    /* north east */
    for (let x2 = x + 1, y2 = y - 1; x2 < n && 0 <= y2; x2++, y2--) {
      if (board[y2][x2] === "Q") {
        return false;
      }
    }

    /* south east */
    for (let x2 = x + 1, y2 = y + 1; x2 < n && y2 < n; x2++, y2++) {
      if (board[y2][x2] === "Q") {
        return false;
      }
    }

    /* south west */
    for (let x2 = x - 1, y2 = y + 1; 0 <= x2 && y2 < n; x2--, y2++) {
      if (board[y2][x2] === "Q") {
        return false;
      }
    }

    /* north west */
    for (let x2 = x - 1, y2 = y - 1; 0 <= x2 && 0 <= y2; x2--, y2--) {
      if (board[y2][x2] === "Q") {
        return false;
      }
    }

    return true;
  };

  const lookup = new Map<string, string[][]>();

  const helper = (board: string[][], remainingQueens: number): string[][] => {
    if (remainingQueens === 0) {
      return [board.map((row) => row.join(""))];
    }

    if (lookup.has(keyify(board))) {
      /* we have already found the solutions */
      return [];
    }

    const boards = [];

    for (let y = 0; y < board.length; y++) {
      /* horizontal */
      if (board[y].includes("Q")) {
        continue;
      }
      for (let x = 0; x < board[0].length; x++) {
        if (checkQueens(x, y, board)) {
          /* we can place! */
          const newBoard = JSON.parse(JSON.stringify(board));
          newBoard[y][x] = "Q";

          const newBoards = helper(newBoard, remainingQueens - 1);
          /*           lookup.set(keyify(newBoard), newBoards); */

          boards.push(...newBoards);
        }
      }
    }

    lookup.set(keyify(board), boards);
    console.log({ lookup });

    return boards;
  };

  const board = generateBoard(n);

  return helper(board, n);
}

console.log(solveNQueens(1));
console.log(solveNQueens(2));
console.log(solveNQueens(3));
console.log(solveNQueens(4));
/* console.log(solveNQueens(5));
 * console.log(solveNQueens(6));
 * console.log(solveNQueens(7));
 * console.log(solveNQueens(8));
 * console.log(solveNQueens(9)); */

export {};

problems/00051-n-queens/typescript/solution.ts

type Coord = {
  x: number;
  y: number;
  v: string;
};

function solveNQueens(n: number): string[][] {
  const generateBoard = (n: number) => {
    const board: string[][] = [];

    for (let y = 0; y < n; y++) {
      board.push(Array(n).fill("."));
    }

    return board;
  };

  const generateCoords = (n: number) => {
    const coords = new Set<string>();

    for (let y = 0; y < n; y++) {
      for (let x = 0; x < n; x++) {
        coords.add(
          JSON.stringify({
            x: x,
            y: y,
          })
        );
      }
    }

    return coords;
  };

  const determineDisallowed = (coord: Coord, size: number) => {
    const disallowedCoords = new Set<string>();

    disallowedCoords.add(JSON.stringify(coord));

    /* horizontal */
    for (let x = 0; x < size; x++) {
      disallowedCoords.add(JSON.stringify({ x: x, y: coord.y }));
    }

    /* vertical */
    for (let y = 0; y < size; y++) {
      disallowedCoords.add(JSON.stringify({ x: coord.x, y: y }));
    }

    /* north east */
    for (let x = coord.x + 1, y = coord.y - 1; x < size && 0 <= y; x++, y--) {
      disallowedCoords.add(JSON.stringify({ x: x, y: y }));
    }

    /* south east */
    for (let x = coord.x + 1, y = coord.y + 1; x < size && y < size; x++, y++) {
      disallowedCoords.add(JSON.stringify({ x: x, y: y }));
    }

    /* south west */
    for (let x = coord.x - 1, y = coord.y + 1; 0 <= x && y < size; x--, y++) {
      disallowedCoords.add(JSON.stringify({ x: x, y: y }));
    }

    /* north west */
    for (let x = coord.x - 1, y = coord.y - 1; 0 <= x && 0 <= y; x--, y--) {
      disallowedCoords.add(JSON.stringify({ x: x, y: y }));
    }

    return disallowedCoords;
  };

  const lookup = new Map<string, string[][]>();
  const helper = (
    queenCoords: Coord[],
    availableCoords: Set<string>,
    remainingQueens: number
  ) => {
    const b = generateBoard(n);

    for (const queenCoord of queenCoords) {
      b[queenCoord.y][queenCoord.x] = "Q";
    }

    const stringBoard = b.map((row) => row.join(""));

    const key = stringBoard.join(",");

    if (lookup.has(key)) {
      return;
    }

    if (remainingQueens === 0) {
      return stringBoard;
    }

    if (availableCoords.size === 0) {
      /* no more avail */
      return;
    }

    const boards: string[][] = [];
    for (const sCoord of availableCoords) {
      const coord: Coord = JSON.parse(sCoord);

      const newQueenCoords = [...queenCoords, coord];
      const disallowedCoords = determineDisallowed(coord, n);

      /* reduce the available coords by whatever was disallowed */
      const newAvailableCoords = new Set<string>();
      for (const availCoord of availableCoords) {
        if (disallowedCoords.has(availCoord)) {
          continue;
        }
        newAvailableCoords.add(availCoord);
      }

      const maybeBoard = helper(
        newQueenCoords,
        newAvailableCoords,
        remainingQueens - 1
      );

      if (maybeBoard === undefined) {
      } else {
        boards.push(maybeBoard);
      }
    }

    lookup.set(key, boards);
  };

  const coords = generateCoords(n);

  helper([], coords, n);

  const boards: string[][] = [];

  for (const [_key, val] of lookup) {
    for (const board of val) {
      boards.push(board);
    }
  }

  return boards;
}

console.log(solveNQueens(1));
console.log(solveNQueens(2));
console.log(solveNQueens(3));
console.log(solveNQueens(4));
console.log(solveNQueens(5));
console.log(solveNQueens(6));
console.log(solveNQueens(7));
console.log(solveNQueens(8));
console.log(solveNQueens(9));

export {};

problems/00055-jump-game/README.md

# [SOLVED] 55 - Jump Game

[Jump Game](https://leetcode.com/problems/jump-game/)

## notes

### first thoughts

- must reach the exact last index
- feels like dynamic programming: reaching the last index from `0` can be broken
  down into reaching the last index from a closer index. we accumulate all of
  these indices with paths to the end and if we can land on any from 0 we win.
- problem does not ask for the shortest path, so we can be happy and return true
  if we have any solution
- what is our state? `indicesToEnd`. starts with one value, which is the last
  index. can store in lookup for fast checking. need to check whether 0 to
  `nums[i]` is in lookup.
- is there way to avoid looking up those values one by one?
- I am concerned that we have scenario where we move the goal post closer but
  then can only reach the end by jumping directly to it. e.g. we cut off a
  solution by moving the goal post. OK, thinking some more: this is the maximum
  distance we can jump, not a fixed value. therefore if we can reach the end we
  could also reach the goal post. therefore it is safe to move the target index
  value.

algorithm:

- work backwards through `nums`
- check if `nums[i]` can reach. if it can, move the goal post to `i`. “can
  reach” is just a distance calculation.
- we necessarily have to check every value of `n`, so this will likely be O(n)
  time complexity.

## summary

- comp.t: O(n) as we necessarily have to check all values
- comp.s: O(1) as we just store `goalPost`
- not sure if this is actually dynamic programming as we are not doing any
  recursive breakdown of the problem.
- another solution approach is to realize that you want to be *able* to jump as
  far as possible. so you could instead iterate elements from index 0 and keep
  track of the maximum distance you could make. that implies that any other
  index prior to that maximum distance is also reachable. so as long as you keep
  track of the maximum distance you can make you just iterate through all
  elements until that maximum distance is greater than or equal to the final
  position.

## tags

medium array
medium dynamic programming?

problems/00055-jump-game/golang/solution.go

package main

import "fmt"

func canJump(nums []int) bool {
	goalPost := len(nums) - 1

	// work backwards from the goal post, updating it to be the closer value
	// every time we can make it
	for i := len(nums) - 2; 0 <= i; i-- {
		distanceToGoal := goalPost - i
		maxJumpDistance := nums[i]

		if distanceToGoal <= maxJumpDistance {
			goalPost = i
		}

	}

	return goalPost == 0
}

func main() {
	fmt.Println(canJump([]int{2, 3, 1, 1, 4}))
	fmt.Println(canJump([]int{3, 2, 1, 0, 4}))
}

problems/00055-jump-game/typescript/solution.ts

function canJump(nums: number[]): boolean {
  let goalPost = nums.length - 1;

  for (let i = nums.length - 2; 0 <= i; i--) {
    const maxJumpDistance = nums[i];
    const distanceToGoal = goalPost - i;

    if (distanceToGoal <= maxJumpDistance) {
      goalPost = i;
    }
  }

  return goalPost === 0;
}

console.log(canJump([2, 3, 1, 1, 4]));
console.log(canJump([3, 2, 1, 0, 4]));

export {};

problems/00056-merge-intervals/README.md

# [SOLVED] 56 - Merge Intervals

[Merge Intervals](https://leetcode.com/problems/merge-intervals/)

## notes

### first thoughts

- is order guaranteed?
- idea. populate an array with 0s, then fill with 1s for each interval. then
  loop the array recording when intervals start and end. this would involve a
  lot of redundant population if there is a lot of overlap
- how can I do it with just the interval bounds? I care about the condition
  where an interval’s start is less than or equal to another. then I take
  `max(int_i_end, int_j_end)`
- lets assume I can calculate overlap correctly regardless of which is the
  larger distance, what does this get me? I would still need to perform this for
  every combination.
- idea. create some function `merge` which takes `intervals1` and `intervals2`
  and returns the merged set. we then call this recursively starting with the
  intervals in `intervals[0]` and `intervals[1]`. this still has problem of
  having to loop over every interval.
- do I gain anything by having every start value? every end value?
- do I gain anything by sorting? ahhh if I sort by the start value, I know that
  I only have to do one pass comparing `intervals[i]` and `intervals[i+1]`
- when sorted, overlap is just when the start of the next is less than or equal
  to the end of the prev

## summary

- comp.t: O(n log n) for sort + O(n) for iteration. O(n log n)
- comp.s: O(n). sort happens in place. just need to store n elements in `merged`
- had trouble getting the logic right for creating `merged`. initially was just
  combining `intervals[i]` and `intervals[j]` and realized that I needed to
  “carry forward” my candidate merge, which led to the current approach.

## tags

medium array
medium sort

problems/00056-merge-intervals/golang/solution.go

package main

import (
	"sort"
)

// first working implementation. left as artifact of thought process
func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i int, j int) bool {
		return intervals[i][0] <= intervals[j][0]
	})

	var merged [][]int

	merged = append(merged, intervals[0])
	// i keeps track of our position in `merged`
	i := 0

	for j := 1; j < len(intervals); j++ {

		candidateMerge := intervals[i]
		candidateEnd := candidateMerge[1]

		intervalJ := intervals[j]
		jStart := intervalJ[0]
		jEnd := intervalJ[1]

		// we know cand.start <= j.start
		if jStart <= candidateEnd {
			// we can merge j with cand
			var mEnd int
			if candidateEnd <= jEnd {
				mEnd = jEnd
			} else {
				mEnd = candidateEnd
			}

			candidateMerge[1] = mEnd
		} else {
			// no merge,
			i = j
			merged = append(merged, intervalJ)
		}

	}

	return merged
}

// alternative implementation with clearer code (slice initialization, removing
// the need for `j` by just using the last value)
func merge2(intervals [][]int) [][]int {
	// sort intervals by their first values
	sort.Slice(intervals, func(i int, j int) bool {
		return intervals[i][0] <= intervals[j][0]
	})

	merged := [][]int{intervals[0]}

	for i := 1; i < len(intervals); i++ {
		cand := merged[len(merged)-1]
		candEnd := cand[1]

		start := intervals[i][0]
		end := intervals[i][1]

		if start <= candEnd {
			// merge it. note that we do not need to adjust start value because we
			// have previously set it to the minimum (base case of adding 0th element
			// and then below of adding it directly).
			if candEnd < end {
				merged[len(merged)-1][1] = end
			} else {
				merged[len(merged)-1][1] = candEnd
			}
		} else {
			// we cannot merge this interval, so add it directly
			merged = append(merged, []int{start, end})
		}

	}

	return merged
}

func main() {
	merge([][]int{{1, 3}})
	merge([][]int{{1, 3}, {2, 6}})
	merge([][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}})
	merge([][]int{{2, 6}, {8, 10}, {15, 18}, {1, 3}})
}

problems/00056-merge-intervals/typescript/solution.ts

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => {
    return a[0] - b[0];
  });

  const merged = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const mergeEnd = merged[merged.length - 1][1];

    const [start, end] = intervals[i];

    if (start <= mergeEnd) {
      /*  we can merge it */
      merged[merged.length - 1][1] = Math.max(mergeEnd, end);
    } else {
      merged.push([start, end]);
    }
  }

  return merged;
}

export {};

problems/00059-spiral-matrix-ii/README.md

# [OPEN] 59 - Spiral Matrix II

[Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/description/)

## notes

## summary

## tags

problems/00059-spiral-matrix-ii/typescript/solution.ts

const printMatrix = (m: number[][]) => {
  console.log("Matrix:");
  for (const row of m) {
    console.log(row);
  }
  console.log();
};

function generateMatrix(n: number): number[][] {
  let minX = 0;
  let maxX = n - 1;
  let minY = 0;
  let maxY = n - 1;

  /* generate array of arrays */
  const mat = new Array(n);
  for (let i = 0; i < n; i++) {
    mat[i] = Array(n).fill(-1);
  }

  console.log({ mat });

  let val = 1;

  /* TBD whether this is correct  */
  while (minX <= maxX) {
    /* move right */
    for (let y = minY, x = minX; x <= maxX; x++) {
      mat[y][x] = val;
      console.log("moving right");
      console.log({ x, y, mat });
      val++;
    }
    minY++;

    console.log({ minX, maxX, minY, maxY });

    /* move down */
    for (let y = minY, x = maxX; y <= maxY; y++) {
      mat[y][x] = val;
      console.log("moving down");
      console.log({ x, y, mat });
      val++;
    }
    maxX--;

    console.log({ minX, maxX, minY, maxY });
    /* move left */
    for (let y = maxY, x = maxX; minX <= x; x--) {
      mat[y][x] = val;
      console.log("moving left");
      console.log({ x, y, mat });
      val++;
    }
    maxY--;

    console.log({ minX, maxX, minY, maxY });
    /* move up */
    for (let y = maxY, x = minX; minY <= y; y--) {
      mat[y][x] = val;
      console.log("moving up");
      console.log({ x, y, mat });
      val++;
    }
    minX++;

    console.log({ minX, maxX, minY, maxY });
  }

  console.log({ n, mat });

  return mat;
}

printMatrix(generateMatrix(1));
printMatrix(generateMatrix(2));
printMatrix(generateMatrix(3));

export {};

problems/00061-rotate-list/README.md

# [OPEN] 61 - Rotate List

[Rotate List](https://leetcode.com/problems/rotate-list/)

## notes

### first thoughts

- we do not know the length of the list without walking it
- `k` is (potentially) much larger than the length of the list
- we need to determine the length, by walking the list, and if `k` is less than
  the length, cut, or if we get to the end and still have values of k, determine
  the cut index
- while we are walking we should record the index and reference to the
  node. could just stuff into an array.

### second thoughts

- ah, we need four things for non-zero `sliceIndex`:
  - the original head
  - the node previous to the slice index
  - the node at the slice index
  - the last node
- comp.t: O(n) because we must iterate all elements of the ListNode
- comp.s: O(1) because we only store four pieces of data

### solution 2

- this approach creates an array to begin with
- comp.t: O(n) because we must iterate all elements of the ListNode
- comp.s: O(n) because we store each ListNode in an array

## summary

## tags

problems/00061-rotate-list/typescript/solution-1.ts

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

const arrFromListNode = (ln: ListNode | null): number[] => {
  const arr: number[] = [];
  while (ln !== null) {
    arr.push(ln.val);
    ln = ln.next;
  }

  return arr;
};

const listNodeFrom = (arr: number[]): ListNode | null => {
  if (arr.length === 0) {
    return null;
  }

  let holder = new ListNode(arr[0]);
  const head = holder;

  for (let i = 1; i < arr.length; i++) {
    const next = new ListNode(arr[i]);
    holder.next = next;

    holder = next;
  }

  return head;
};

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  /* base cases */
  if (k === 0) {
    return head;
  }

  if (head === null) {
    return head;
  }

  const getLength = (head: ListNode | null) => {
    let length = 0;

    while (head !== null) {
      head = head.next;
      length++;
    }

    return length;
  };

  const length = getLength(head);

  if (length === 0 || length === 1) {
    return head;
  }

  const sliceIndex = k % length;

  console.log({ sliceIndex, k, length });

  const originalHead = head;

  let prev = originalHead;
  let newHead: ListNode | null = null;
  let last = originalHead;
  let curr: ListNode | null = originalHead;

  let count = sliceIndex - 1;
  while (curr !== null) {
    count--;
    if (count === 0) {
      prev = curr;
      newHead = curr.next;
    }

    last = curr;
    curr = curr.next;
  }

  console.log({ originalHead, prev, newHead, last });

  prev.next = null;
  last.next = originalHead;

  return newHead;
}

/* console.log(arrFromListNode(rotateRight(null, 0))); */
/* console.log(arrFromListNode(rotateRight(listNodeFrom([1]), 99))); */
console.log(arrFromListNode(rotateRight(listNodeFrom([1, 2]), 1)));
console.log(arrFromListNode(rotateRight(listNodeFrom([1, 2, 3, 4, 5]), 2)));
/* console.log(arrFromListNode(rotateRight(listNodeFrom([0, 1, 2]), 4))); */

export {};

problems/00061-rotate-list/typescript/solution-2.ts

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

const arrFromListNode = (ln: ListNode | null): number[] => {
  const arr: number[] = [];
  while (ln !== null) {
    arr.push(ln.val);
    ln = ln.next;
  }

  return arr;
};

const listNodeFrom = (arr: number[]): ListNode | null => {
  if (arr.length === 0) {
    return null;
  }

  let holder = new ListNode(arr[0]);
  const head = holder;

  for (let i = 1; i < arr.length; i++) {
    const next = new ListNode(arr[i]);
    holder.next = next;

    holder = next;
  }

  return head;
};

function rotateRight(head: ListNode | null, k: number): ListNode | null {
  /* base cases */
  if (k === 0) {
    return head;
  }

  if (head === null) {
    return head;
  }

  const arr: ListNode[] = [];
  while (head !== null) {
    arr.push(head);
    head = head.next;
  }

  if (arr.length === 1) {
    return arr[0];
  }

  const sliceIndex = k % arr.length;

  console.log({ k, sliceIndex });

  const originalHead = arr[0];
  let prev = arr[sliceIndex];
  let newHead = arr[sliceIndex + 1];
  let last = arr[arr.length - 1];

  console.log({ originalHead, prev, newHead, last });

  prev.next = null;
  last.next = originalHead;

  return newHead;
}

/* console.log(arrFromListNode(rotateRight(null, 0))); */
/* console.log(arrFromListNode(rotateRight(listNodeFrom([1]), 99))); */
console.log(arrFromListNode(rotateRight(listNodeFrom([1, 2]), 1)));
/* console.log(arrFromListNode(rotateRight(listNodeFrom([1, 2, 3, 4, 5]), 2))); */
/* console.log(arrFromListNode(rotateRight(listNodeFrom([0, 1, 2]), 4))); */

export {};

problems/00064-minimum-path-sum/README.md

# [SOLVED] 64 - Minimum Path Sum

[Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)

## notes

### first thoughts

- feels like dynamic programming
- I have to look at all values in case there is some really small value, so
  comp.t is going to be O(m + n)
- state: y, x, cost
- transition function: cost(x,y) = sum(x,y) + min(cost(x+1,y), cost(y+1, x))
- memo: `lookup[y][x]`
- base cases: `lookup[desty][destx] = sum[y][x]`
- going to work backward from end

## summary

- comp.t: O(n + m) because we need to look at all values
- comp.s: O(n * m) because we store in a lookup
- initially my notes were written assuming we’d start at the end and then work
  our way back to 0,0, but I ended up implementing starting at 0,0 and working
  toward the base case. I switched this on implementation because it seemed more
  clear to pass the starting position and have the base case be embedded in the
  lookup rather than the other way around.
- one interesting golang approach basically said “my initial condition is
  val(0,0), I know that the entire y column at x=0 are only accessible via
  downward movement, so I can calculate their costs, same goes for row y=0
  summing across, and so I can update the grid directly, and then walk from 1,1
  to the bottom right by taking the min() of either arrival from left or from
  above.” so it solved for the y=0 and x=0 edges of the grid, and then used
  those to walk downward. clever!
- interesting from the typescript: `Array.fill`, which I was not aware of.

## tags

problems/00064-minimum-path-sum/golang/solution.go

package main

import (
	"fmt"
	"math"
)

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

func helper(grid [][]int, lookup [][]int, x, y int) int {
	if x < 0 || len(grid[0]) <= x {
		return math.MaxInt
	}

	if y < 0 || len(grid) <= y {
		return math.MaxInt
	}

	if lookup[y][x] != -1 {
		return lookup[y][x]
	}

	minPath := grid[y][x] + min(helper(grid, lookup, x+1, y), helper(grid, lookup, x, y+1))

	lookup[y][x] = minPath

	return minPath
}

func minPathSum(grid [][]int) int {

	var lookup [][]int

	for range grid {
		row := make([]int, len(grid[0]))
		for i := range row {
			row[i] = -1
		}
		lookup = append(lookup, row)
	}

	destY := len(grid) - 1
	destX := len(grid[0]) - 1

	// initial condition
	lookup[destY][destX] = grid[destY][destX]

	return helper(grid, lookup, 0, 0)
}

func main() {
	fmt.Println(minPathSum([][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}))
	fmt.Println(minPathSum([][]int{{1, 2, 3}, {4, 5, 6}}))
}

problems/00064-minimum-path-sum/typescript/solution.ts

const helper = (
  grid: number[][],
  lookup: number[][],
  x: number,
  y: number
): number => {
  if (y < 0 || grid.length <= y) {
    return Number.MAX_SAFE_INTEGER;
  }

  if (x < 0 || grid[0].length <= x) {
    return Number.MAX_SAFE_INTEGER;
  }

  const maybeCached = lookup[y][x];
  if (maybeCached !== -1) {
    return maybeCached;
  }

  const val =
    grid[y][x] +
    Math.min(helper(grid, lookup, x + 1, y), helper(grid, lookup, x, y + 1));

  lookup[y][x] = val;

  return val;
};

function minPathSum(grid: number[][]): number {
  const lookup: number[][] = [];

  for (const row of grid) {
    lookup.push(row.map((_v) => -1));
  }

  const destY = grid.length - 1;
  const destX = grid[0].length - 1;

  lookup[destY][destX] = grid[destY][destX];

  return helper(grid, lookup, 0, 0);
}

console.log(
  minPathSum([
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1],
  ])
);

console.log(
  minPathSum([
    [1, 2, 3],
    [4, 5, 6],
  ])
);

export {};

problems/00074-search-a-2d-matrix/README.md

# [SOLVED] 74 - Search a 2D Matrix

[Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/)

## notes

### first thoughts

### golang implementation thoughts

- smells like binary search
- ordering allows for binary search of both columns and rows
- must run in O(log(m + n)), so very likely binary search
- solution approach: bs first column to find closest without going over, then bs
  row. bs’ing first column can be made easier by inspecting the first and last
  values of the array. if they are bounds, that is our condition for stopping.
- solution approach: append each row and just bs it all

## summary

- typescript solution written when I was first starting solving, golang more
  recently
- comp.t: O(m + n) in both due to size of search space + binary search
- comp.s: O(1) no extra storage used

## tags

medium binary search
medium array
medium matrix

problems/00074-search-a-2d-matrix/golang/solution.go

package main

// return index if found, -1 if not
func bs(nums []int, target int) int {
	for l, r, m := 0, len(nums)-1, -1; l <= r; {
		m = l + (r-l)/2

		if nums[m] == target {
			// we are done
			return m
		} else if target < nums[m] {
			// target is to left of mid
			r = m - 1
		} else if nums[m] < target {
			// target is to the right of mid
			l = m + 1
		} else {
			// can't happen
		}

	}

	return -1
}

func searchMatrix(matrix [][]int, target int) bool {
	// cheeky: append all values to a single []int that we can run bs on
	var all []int
	for _, row := range matrix {
		all = append(all, row...)
	}

	return bs(all, target) != -1
}

// alternative implementation demonstrating binary search using criteria
func searchMatrix2(matrix [][]int, target int) bool {
	// find the y index to search within
	y := -1
	for l, r, m := 0, len(matrix)-1, -1; l <= r; {
		m = l + (r-l)/2

		if matrix[m][0] <= target && target <= matrix[m][len(matrix[m])-1] {
			// our target could be within this row
			y = m
			break
		} else if target < matrix[m][0] {
			// target is lower than this row
			r = m - 1
		} else if matrix[m][0] < target {
			// target is higher than this row
			l = m + 1
		} else {
			// can't happen
		}
	}

	if y == -1 {
		// couldn't find a row that could contain target
		return false
	}

	return bs(matrix[y], target) != -1
}

func main() {

}

problems/00074-search-a-2d-matrix/typescript/solution.ts

/* non-decreasing: ca nhave same value sequentially (no guarantee of
uniqueness) */

/* a consequence of rows of non-decreasing rows and first number larger than
any of the previous is that both rows and columns can be searched using binary
search */

/* idea: find the possible column first, return false if not possible. if
possible found, search row */

/* matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 */

/* state: yLow, yHigh, yMid, xLow, xHigh, xMid  */

/* 0: yLow=0, yHigh=3-1 yMid=Math.floor((2-0)/2)=1 yVal=matrix[yMid][0]=10
target is less, move yHigh=yMid */
/* 1: yLow=0, yHigh=1 fails condition, check if matrix[yLow] is less than
target. if yes, x search else return false */
/* 2: xLow=0, xHigh=3 xMid=Math.floor((3-0)/2)=1 xVal[matrix[yLow][xMid]=3
target is found */

const binarySearch = (arr: number[], target: number): number => {
  let index = -1;

  let leftIndex = 0;
  let rightIndex = arr.length - 1;

  while (leftIndex <= rightIndex) {
    const midIndex = Math.floor(leftIndex + (rightIndex - leftIndex) / 2);

    const maybeVal = arr[midIndex];

    if (maybeVal === target) {
      /* found it */
      index = midIndex;
      break;
    } else if (maybeVal < target) {
      leftIndex = midIndex + 1;
    } else if (target < maybeVal) {
      rightIndex = midIndex - 1;
    } else {
      /* can't happen */
    }
  }

  return index;
};

function searchMatrix(matrix: number[][], target: number): boolean {
  let present = false;

  let yLow = 0;
  let yHigh = matrix.length - 1;

  let mid = yLow;
  while (yLow <= yHigh) {
    mid = Math.floor(yLow + (yHigh - yLow) / 2);

    const yValMin = matrix[mid][0];
    const yValMax = matrix[mid][matrix[mid].length - 1];

    if (target < yValMin) {
      yHigh = mid - 1;
    } else if (yValMax < target) {
      yLow = mid + 1;
    } else {
      break;
    }
  }

  if (yLow <= yHigh) {
    console.log({ mid });
    present = binarySearch(matrix[mid], target) !== -1;
  }

  return present;
}

console.log(
  searchMatrix(
    [
      [1, 3, 5, 7],
      [10, 11, 16, 20],
      [23, 30, 34, 60],
    ],
    3
  )
);

console.log(
  searchMatrix(
    [
      [1, 3, 5, 7],
      [10, 11, 16, 20],
      [23, 30, 34, 60],
    ],
    13
  )
);

console.log(searchMatrix([[1], [3]], 0));

export {};

problems/00078-subsets/README.md

# [SOLVED] 78 - Subsets

[Subsets](https://leetcode.com/problems/subsets/)

## notes

### first thoughts

- smells like dynamic programming
- likely need to sort to ensure that only unique sets are generated

```
nums=[1,2,3]

always add empty set:
sets = [[]]

do not need to sort nums because each element is unique

start at i = 0 to i < nums.length
iterate sets, adding nums[i] to each member, adding result to local_set
append all of local_set to sets

```

- do not need dynamic programming
- manually working out:

```
[1,2,3]

sets = [[]]

local_set = [[1]]
sets = [[], [1]]

local_set = [[2], [1, 2]]
sets = [[], [1], [2], [1,2]]

local_set = [[3], [1,3], [2,3], [1,2,3]]
sets = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

```

- comp.t: O(n)
- comp.s: O(2^n)?


## summary

## tags

problems/00078-subsets/typescript/solution.ts

function subsets(nums: number[]): number[][] {
  const sets: number[][] = [[]];

  for (let i = 0; i < nums.length; i++) {
    const localSet: number[][] = [];
    for (const s of sets) {
      localSet.push([...s, nums[i]]);
    }
    sets.push(...localSet);
  }

  return sets;
}

console.log(subsets([1, 2, 3]));
console.log(subsets([0]));

export {};

problems/00079-word-search/README.md

# [SOLVED] 79 - Word Search

[Word Search](https://leetcode.com/problems/word-search/)

## notes

### first thoughts

- idea. take first character of string, iterate all cells of matrix. write
  recursive algorithm to try and walk to find the remaining characters. actually
  can just pass every cell to that helper.
- create helper that takes a call and can lookup whether a cell has been visited
  before. helper should attempt to walk all valid neighbors and only set the
  lookup if it is a valid letter in the word.
- state is going to be: lookup, y, x, and remaining characters

## summary

- comp.t: at each coord, we have 4 options, so O(4^(n * m))?
- comp.s: lookup is just O(len(word))
- the optimizations I looked at were really clever: checking whether word could
  fit in matrix, checking whether letter count even made it viable, and then
  reversing the word if there were more rare characters in the second half
- my initial golang implementation didn’t realize that maps are passed by
  reference, then my `fresh` map function to copy it was too slow, and so I
  switched to making my lookup shared across invocations of `helper` and it just
  annoys me lol.

## tags

medium depth first search
medium dfs
medium recursive
medium matrix

problems/00079-word-search/golang/solution.go

package main

import "fmt"

type coord struct {
	x int
	y int
}

func exist(board [][]byte, word string) bool {
	var helper func(board [][]byte, x int, y int, chars []byte) bool

	lookup := make(map[coord]bool)

	helper = func(board [][]byte, x int, y int, chars []byte) bool {
		if len(chars) == 0 {
			// we are done
			return true
		}

		if x < 0 || len(board[0])-1 < x || y < 0 || len(board)-1 < y {
			// out of bounds
			return false
		}

		cell := coord{x: x, y: y}
		if _, ok := lookup[cell]; ok {
			// we have already been here
			return false
		}

		res := false
		if board[y][x] == chars[0] {
			lookup[cell] = true

			// we have a candidate. check all neighbors
			res = helper(board, x+1, y, chars[1:]) ||
				helper(board, x-1, y, chars[1:]) ||
				helper(board, x, y+1, chars[1:]) ||
				helper(board, x, y-1, chars[1:])

		}

		delete(lookup, cell)

		return res
	}

	for y := 0; y < len(board); y++ {
		for x := 0; x < len(board[0]); x++ {
			// using []byte(word) is dangerous but assume sane input
			if helper(board, x, y, []byte(word)) {
				return true
			}
		}
	}

	return false
}

func main() {
	fmt.Println(exist([][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED"))
	fmt.Println(exist([][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "SEE"))
	fmt.Println(exist([][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCESEEEFS"))

}

problems/00079-word-search/typescript/solution.ts

function exist(board: string[][], word: string): boolean {
  /* loop through every x, y of the board */

  /* find first character of word */

  /* start with i = 0 */

  /* keep track of the letters / cells we have visited */

  /* recursively check all neighbors, incrementing i and passing lookup of
  places we visited */

  const seen = new Set<string>();

  const helper = (i: number, x: number, y: number): boolean => {
    /* base case: */
    if (i === word.length) {
      return true;
    }

    if (y < 0 || board.length <= y) {
      return false;
    }

    if (x < 0 || board[0].length <= x) {
      return false;
    }

    if (seen.has(JSON.stringify([x, y]))) {
      return false;
    }

    const char = word[i];
    const val = board[y][x];

    seen.add(JSON.stringify([x, y]));

    let result = false;
    if (char === val) {
      /* we can continue */
      result =
        helper(i + 1, x, y + 1) ||
        helper(i + 1, x, y - 1) ||
        helper(i + 1, x + 1, y) ||
        helper(i + 1, x - 1, y);
    }

    seen.delete(JSON.stringify([x, y]));

    return result;
  };

  /* we still need to iterate through all x and y */
  for (let y = 0; y < board.length; y++) {
    for (let x = 0; x < board[0].length; x++) {
      if (helper(0, x, y)) {
        return true;
      } else {
        /* continue */
      }
    }
  }

  return false;
}

export {};

problems/00084-largest-rectangle-in-histogram/README.md

# [OPEN] 84 - Largest Rectangle in Histogram

[Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

## notes

- imported old attempt. failed with time limit exceeded.

## summary

## tags

problems/00084-largest-rectangle-in-histogram/typescript/solution.ts

function largestRectangleArea(heights: number[]): number {
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    const height = heights[i];

    let startIndex = i;
    for (let start = i; 0 <= start; start--) {
      const maybeStartingHeight = heights[start];

      if (height <= maybeStartingHeight) {
        startIndex = start;
      } else {
        break;
      }
    }

    let endIndex = i;
    for (let end = i; end < heights.length; end++) {
      const maybeEndingHeight = heights[end];

      if (height <= maybeEndingHeight) {
        endIndex = end;
      } else {
        break;
      }
    }

    const area = height * (endIndex - startIndex + 1);

    /*     console.log({ height, startIndex, endIndex, area }); */

    if (maxArea < area) {
      maxArea = area;
    }
  }

  return maxArea;
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]));
console.log(largestRectangleArea([2, 4]));

export {};

problems/00090-subsets-ii/README.md

# [SOLVED] 90 - Subsets II

[Subsets II](https://leetcode.com/problems/subsets-ii/)

## notes

### first pass thoughts

- same as subsets, but this time use a real set to guard against duplicates
- would need to sort.
- is there a better way?

## summary

- other solutions using backtracking and dfs

## tags

problems/00090-subsets-ii/typescript/solution.ts

function subsetsWithDup(nums: number[]): number[][] {
  const lookup = new Set<string>([JSON.stringify([])]);

  for (const num of nums) {
    const localSubSets: number[][] = [];
    for (const subSet of lookup) {
      localSubSets.push([...JSON.parse(subSet), num]);
    }

    for (const localSubSet of localSubSets) {
      localSubSet.sort((a, b) => {
        return a - b; /* sort ascending */
      });

      lookup.add(JSON.stringify(localSubSet));
    }
  }

  return [...lookup].map((s) => JSON.parse(s));
}

console.log(subsetsWithDup([1, 2, 2]));
console.log(subsetsWithDup([0]));

export {};

problems/00101-symmetric-tree/README.md

# [SOLVED] 101 - Symmetric Tree

[Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)

## notes

### first thoughts

- I actually had trouble conceptualizing how to handle this. I knew I wanted to
  recursively descend, but I kept wanting to use the helper without figuring out
  the sub problem.
- the subproblem was how to determine if trees of depth 1 were symmetric. once I
  figured this I could derive the base cases that helped with the rest of
  implementation
- I do not know off hand how to do the iterative approach

## summary

- comp.t: O(n). we must compare every node
- comp.s: O(log n). the depth of the binary tree is log (n), which is the amount
  of stack space we need to execute the recursive solution.
- added an iterative solution that was correct in spirit but relied a bit too
  much on convoluted `reverse` usage. I did not think the iterative solution was
  easy. There are other iterative approaches too that I did not implement.

## tags

easy binary tree
easy tree
easy recursive
easy iterative

problems/00101-symmetric-tree/golang/solution.go

package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func helper(left *TreeNode, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	} else if left == nil || right == nil {
		return false
	}
	return left.Val == right.Val && helper(left.Left, right.Right) && helper(left.Right, right.Left)
}

func isSymmetricRec(root *TreeNode) bool {
	return helper(root, root)
}

func isSymmetricIter(root *TreeNode) bool {
	return false
}

func isSymmetric(root *TreeNode) bool {
	return isSymmetricRec(root)
}

func main() {
	fmt.Println(isSymmetric(&TreeNode{Val: 1}))
	fmt.Println(isSymmetric(&TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 2}}))
	fmt.Println(isSymmetric(&TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}, Right: &TreeNode{Val: 4}}, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 3}}}))
	fmt.Println(isSymmetric(&TreeNode{Val: 1, Left: &TreeNode{Val: 2, Right: &TreeNode{Val: 3}}, Right: &TreeNode{Val: 2, Right: &TreeNode{Val: 3}}}))
}

problems/00101-symmetric-tree/typescript/solution.ts

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

const recursiveHelper = (
  leftNode: TreeNode | null,
  rightNode: TreeNode | null
): boolean => {
  if (leftNode === null && rightNode === null) {
    /* both null: equal */
    return true;
  } else if (leftNode === null || rightNode === null) {
    /* only one is null, not equal */
    return false;
  }

  return (
    /* values are equal */
    leftNode.val === rightNode.val &&
    /* the outer node of each should be symmetric */
    recursiveHelper(leftNode.left, rightNode.right) &&
    /* as well as the inner nodes */
    recursiveHelper(leftNode.right, rightNode.left)
  );
};

const iterSymmetric = (root: TreeNode | null) => {
  if (root === null) {
    return true;
  }

  /* we want to compare that the left-to-right "level" of the left side is
  equal to the right-toleft "level" of the right side */

  let leftSide = [root.left];
  let rightSide = [root.right];

  let prevLeftLevel: (TreeNode | null)[] = [];
  let prevRightLevel: (TreeNode | null)[] = [];

  let sym = true;
  while (leftSide.length !== 0 && rightSide.length !== 0 && sym) {
    /* compare */
    if (leftSide.length !== rightSide.length) {
      return false;
    }

    for (let i = 0; i < leftSide.length; i++) {
      const l = leftSide[i];
      const r = rightSide[i];

      if (l === null && r === null) {
        /* no problem */
      } else if (l === null || r === null) {
        return false;
      } else if (l.val !== r.val) {
        return false;
      }
    }
    prevLeftLevel = leftSide;
    prevRightLevel = rightSide.reverse();

    /* left to right */
    leftSide = prevLeftLevel.flatMap((n) => {
      const l = n === null ? null : n.left;
      const r = n === null ? null : n.right;
      return [l, r];
    });

    /* right to left */
    rightSide = Array.from(prevRightLevel)
      .reverse()
      .flatMap((n) => {
        const l = n === null ? null : n.left;
        const r = n === null ? null : n.right;
        return [r, l];
      });

    if (
      leftSide.filter((n) => n !== null).length === 0 &&
      rightSide.filter((n) => n !== null).length === 0
    ) {
      break;
    }
  }

  return sym;
};

function isSymmetric(root: TreeNode | null): boolean {
  return recursiveHelper(root, root);
}

console.log(
  iterSymmetric(
    new TreeNode(
      1,
      new TreeNode(2, null, new TreeNode(3)),
      new TreeNode(2, null, new TreeNode(3))
    )
  )
);

console.log(
  iterSymmetric(
    new TreeNode(
      2,
      new TreeNode(
        3,
        new TreeNode(4),
        new TreeNode(5, new TreeNode(8), new TreeNode(9))
      ),
      new TreeNode(
        3,
        new TreeNode(5, new TreeNode(9), new TreeNode(8)),
        new TreeNode(4)
      )
    )
  )
);

export {};

problems/00102-binary-tree-level-order-traversal/README.md

# [SOLVED] 102 - Binary Tree Level Order Traversal

[Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

## notes

- iterative, rather than recursive
- create a level that we flatmap each level and grab the left / right values

## summary

- comp.t: O(n) in worst case.
- comp.s: O(n) output array
- flatmap is very useful here!
- golang implementation was actually simpler. I may have made it too complicated
  w/ `flatMap`

## tags

medium binary tree
medium iterative

problems/00102-binary-tree-level-order-traversal/golang/solution.go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	var output [][]int
	var level []*TreeNode

	if root != nil {
		level = append(level, root)
	}

	for len(level) != 0 {

		var levelVals []int
		var nextLevel []*TreeNode

		// find the values
		for _, tn := range level {
			if tn == nil {
				continue
			}

			levelVals = append(levelVals, tn.Val)

			// update the next level
			if tn.Left != nil {
				nextLevel = append(nextLevel, tn.Left)
			}

			if tn.Right != nil {
				nextLevel = append(nextLevel, tn.Right)
			}

		}

		// add them to the output
		output = append(output, levelVals)

		// update the level
		level = nextLevel

	}

	return output
}

func main() {

}

problems/00102-binary-tree-level-order-traversal/typescript/solution.ts

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

function levelOrder(root: TreeNode | null): number[][] {
  const output: number[][] = [];

  let level = [root].flatMap((n) => {
    if (n === null) {
      return [];
    } else {
      return [n];
    }
  });

  while (level.length !== 0) {
    output.push(
      level.flatMap((n) => {
        if (n === null) {
          return [];
        } else {
          return [n.val];
        }
      })
    );

    level = level.flatMap((n) => {
      if (n === null) {
        return [];
      }

      if (n.left !== null && n.right !== null) {
        return [n.left, n.right];
      }

      if (n.left === null && n.right !== null) {
        return [n.right];
      }

      if (n.left !== null && n.right === null) {
        return [n.left];
      }

      return [];
    });
  }

  return output;
}

console.log(
  levelOrder(
    new TreeNode(
      3,
      new TreeNode(9),
      new TreeNode(20, new TreeNode(15), new TreeNode(7))
    )
  )
);

console.log(levelOrder(new TreeNode(1)));

console.log(levelOrder(null));

export {};

problems/00104-maximum-depth-of-binary-tree/README.md

# [SOLVED] 104 - Maximum Depth of Binary Tree

[Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

## notes

### first thoughts

- recursive
- add 1 for each level, selecting the maximum depth between left and right

## summary

- comp.t: O(n) where n is the number of nodes in the tree
- comp.s: O(log n) which is the depth of the tree

## tags

easy recursive
easy binary tree

problems/00104-maximum-depth-of-binary-tree/golang/solution.go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	lHeight := maxDepth(root.Left)
	rHeight := maxDepth(root.Right)

	var max int

	if lHeight < rHeight {
		max = rHeight
	} else {
		max = lHeight
	}

	return 1 + max
}

func main() {

}

problems/00104-maximum-depth-of-binary-tree/typescript/solution.ts

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

function maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }

  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

console.log(maxDepth(new TreeNode(1, null, null)));
console.log(maxDepth(new TreeNode(1, null, new TreeNode(2))));
console.log(
  maxDepth(
    new TreeNode(
      3,
      new TreeNode(9),
      new TreeNode(20, new TreeNode(15), new TreeNode(17))
    )
  )
);

export {};

problems/00120-triangle/README.md

# [SOLVED] 120 - Triangle

[Triangle](https://leetcode.com/problems/triangle/)

## notes

### first thoughts

- feels like DP
- every branch I get two choices: `i` or `i+1`
- negative numbers are allowed
- I necessarily have to check / rule out all paths
- the last row of a triangle of length `n` will have `n` elements
- I am not sure how the runtime complexity changes with each level being one longer than the next:
  - 0: 1 element. 1 path to get there
  - 1: 2 element. 2 path to get there
  - 2: 3 element. 4 path to get there
  - 3: 4 element. 8 path to get there
- so looks like `2^(n-1)`
- state: `i, j`
- fxn: `shorted_path(i, j) = weight(i,j) + min(shorted_path(i - 1, j - 1), shorted_path(i - 1, j))`
- base case: `shortest_path(0,0) = weight(0,0)`

```
2
3 4
6 5 7
4 1 8 3
```

- OK, that appeared to work
- comp.t: `O(n)` we compute each value exactly once
- comp.s: `O(n)` we store each node’s value exactly once

## summary

- I liked the approach where you work bottom up just taking the min for the next
  level.

## tags

problems/00120-triangle/typescript/solution-1.ts

function minimumTotal(triangle: number[][]): number {
  let minTotal = Number.MAX_SAFE_INTEGER;

  const keyify = (i: number, j: number) => {
    return `${i}-${j}`;
  };

  const lookup = new Map<string, number>();
  lookup.set(keyify(0, 0), triangle[0][0]);

  const helper = (i: number, j: number): number => {
    if (j < 0 || i < 0 || triangle[i].length <= j) {
      /* we went out of bounds */
      return Number.MAX_SAFE_INTEGER;
    }

    const maybeWeight = lookup.get(keyify(i, j));

    if (maybeWeight !== undefined) {
      return maybeWeight;
    }

    const sum =
      triangle[i][j] + Math.min(helper(i - 1, j - 1), helper(i - 1, j));
    lookup.set(keyify(i, j), sum);

    return sum;
  };

  for (let j = 0; j < triangle[triangle.length - 1].length; j++) {
    const sum = helper(triangle.length - 1, j);

    if (sum < minTotal) {
      minTotal = sum;
    }
  }

  return minTotal;
}

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]));
console.log(minimumTotal([[-10]]));
export {};

problems/00120-triangle/typescript/solution-2.ts

function minimumTotal(triangle: number[][]): number {
  for (let i = triangle.length - 2; 0 <= i; i--) {
    for (let j = 0; j < triangle[i].length; j++) {
      triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
    }
  }
  return triangle[0][0];
}

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]));
console.log(minimumTotal([[-10]]));
export {};

problems/00128-longest-consecutive-sequence/README.md

# [SOLVED] 128 - Longest Consecutive Sequence

[Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence/)

## notes

### first thoughts

- must run in O(n) time, which means we could still do multiple passes through
- idea. store the numbers encountered in a lookup. when you encounter a number,
  check whether sequential values are present. if they are, count them and
  compare to max.

### second thoughts

- submitted correct solution but it was slow
- investigation showed that I was doing unnecessary checks. I really only want
  to start the sequence check when I know for sure I am at the bottom of it (the
  smallest value).
- possibly would have realized this if I had drawn out the map and then asked
  “what is performance impact of checking `prev` and `next` for each value?”
- typescript optimization: using `Set` is faster than `Map`

## summary

- comp.t: I think O(n), but for every n we potentially start walking a sequence
  whose size is bounded by n.
- comp.s: O(n) for the lookup.
- intuition was correct, but I have no idea why the golang code is only 5th
  percentile for performance. some solutions sort, which is invalid re: running
  in O(n) time.
- re: speedup, it looks like golang is much faster when you directly access
  rather than create new variables, and minimize your lookup checks. the current
  version only moves forward to check a sequence if it encounters the number
  that is the lowest value in that sequence.

## tags

medium array

problems/00128-longest-consecutive-sequence/golang/solution.go

package main

import "fmt"

func longestConsecutive(nums []int) int {
	lookup := make(map[int]bool, len(nums))

	for i := range nums {
		lookup[nums[i]] = true
	}

	var max int

	for num := range lookup {
		if !lookup[num-1] {
			// we have the lowest in a sequence
			length := 1

			for lookup[num+length] {
				length++
			}

			if max < length {
				max = length
			}

		}
	}

	return max
}

func main() {
	fmt.Println(longestConsecutive([]int{100, 4, 200, 1, 3, 2}))
	fmt.Println(longestConsecutive([]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}))
}

problems/00128-longest-consecutive-sequence/typescript/solution.ts

function longestConsecutive(nums: number[]): number {
  const lookup = new Set(nums);

  let max = 0;
  for (const num of lookup) {
    if (!lookup.has(num - 1)) {
      /* we are at beginning of sequence */
      let length = 1;
      while (lookup.has(num + length)) {
        length++;
      }

      if (max < length) {
        max = length;
      }
    }
  }

  return max;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2]));

export {};

problems/00130-surrounded-regions/README.md

# [SOLVED] 130 - Surrounded Regions

[Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)

## notes

### first thoughts

- need to check every square
- need to determine whether an area is captureable
- create lookup(i, j) = capturable
- mark all edges lookup(i, j) = false
- iterate remaining i and j
- once an O is found, start DFS for x and y
- if board[x,y] is X, back up
- if board[x,y] is O, add x and y to local subset
- check if capturable
- if present and true, we have already been here. back up
- if present and false, we have not been here. continue
- continue until board is complete
- state: `i`, `j`
- transition: `captureable(i, j) = board[i][j] === ‘O’ && (board[i+1][j] === ‘X’
  || capturable(i+1, j) && ... ) `
- note: this did not work. I kept bouncing back and forth between `i` and `j`
  values I had already visited. I

### second thoughts

- iterate non-border cells
- if you encounter an `O`, walk to find every adjacent `O`, recording coordinates
- if coordinates do not contain a border position, flip to `X`
- comp.t: O(m + n)
- comp.s: O(m + n) (storing visited)
- worked, but was very slow

### third thoughts

- top performing ones did dfs from border using a queue
- implemented and got slightly better performance but not much better.

## summary

## tags

problems/00130-surrounded-regions/typescript/solution-1.ts

/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
  console.log("init:");
  console.log(board);

  const keyify = (i: number, j: number) => {
    return `${i},${j}`;
  };

  const visited = new Set<string>();

  /* iterate non-boarder cells */
  for (let i = 1; i < board.length - 1; i++) {
    for (let j = 1; j < board[0].length - 1; j++) {
      const key = keyify(i, j);

      if (visited.has(key)) {
        continue;
      }

      if (board[i][j] === "X") {
        continue;
      }

      /* board[i][j] is "O". walk adjacent until completely filled out  */
      const seenOs = new Set<string>();
      let borderDetected = false;

      const helper = (i2: number, j2: number) => {
        const key2 = keyify(i2, j2);

        /* we have been here before */
        if (seenOs.has(key2)) {
          return;
        }

        /* out of bounds */
        if (
          i2 < 0 ||
          board.length - 1 < i2 ||
          j2 < 0 ||
          board[0].length - 1 < j2
        ) {
          return;
        }

        /* candidate! */
        if (board[i2][j2] === "O") {
          /* did we hit border? */
          if (
            i2 === 0 ||
            i2 === board.length - 1 ||
            j2 === 0 ||
            j2 === board[0].length - 1
          ) {
            borderDetected = true;
          }

          seenOs.add(key2);
          helper(i2 - 1, j2);
          helper(i2 + 1, j2);
          helper(i2, j2 - 1);
          helper(i2, j2 + 1);
          return;
        }
      };

      helper(i, j);

      /* add all to visited */
      for (const k of seenOs) {
        visited.add(k);

        if (borderDetected) {
          /* cannot turn them to "X"s */
        } else {
          /* can safely turn them to Xs */
          const [i3, j3] = k.split(",").map((s) => Number(s));

          board[i3][j3] = "X";
        }
      }
    }
  }
}

const board1 = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"],
];
solve(board1);
console.log(board1);

const board2 = [
  ["O", "X", "X", "O", "X"],
  ["X", "O", "O", "X", "O"],
  ["X", "O", "X", "O", "X"],
  ["O", "X", "O", "O", "O"],
  ["X", "X", "O", "X", "O"],
];
solve(board2);
console.log(board2);

export {};

problems/00130-surrounded-regions/typescript/solution-2.ts

/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
  const maxY = board.length - 1;
  const maxX = board[0].length - 1;

  const queue: number[][] = [];

  /* turn every border cell to B */
  for (let y = 0; y <= maxY; y++) {
    if (board[y][0] === "O") {
      board[y][0] = "B";
      queue.push([y, 0]);
    }

    if (board[y][maxX] === "O") {
      board[y][maxX] = "B";
      queue.push([y, maxX]);
    }
  }

  for (let x = 0; x <= maxX; x++) {
    if (board[0][x] === "O") {
      board[0][x] = "B";
      queue.push([0, x]);
    }

    if (board[maxY][x] === "O") {
      board[maxY][x] = "B";
      queue.push([maxY, x]);
    }
  }

  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];

  while (queue.length !== 0) {
    const coord = queue.pop();

    if (coord === undefined) {
      continue;
    }

    for (const d of directions) {
      const nextY = coord[0] + d[0];
      const nextX = coord[1] + d[1];

      if (
        0 < nextY &&
        nextY < maxY &&
        0 < nextX &&
        nextX < maxX &&
        board[nextY][nextX] === "O"
      ) {
        queue.push([nextY, nextX]);
        board[nextY][nextX] = "B";
      }
    }
  }

  for (let y = 0; y <= maxY; y++) {
    for (let x = 0; x <= maxX; x++) {
      if (board[y][x] === "B") {
        board[y][x] = "O";
      } else if (board[y][x] === "O") {
        board[y][x] = "X";
      } else {
        /* do nothing */
      }
    }
  }
}

const board1 = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"],
];
solve(board1);
console.log(board1);

const board2 = [
  ["O", "X", "X", "O", "X"],
  ["X", "O", "O", "X", "O"],
  ["X", "O", "X", "O", "X"],
  ["O", "X", "O", "O", "O"],
  ["X", "X", "O", "X", "O"],
];
solve(board2);
console.log(board2);

export {};

problems/00131-palindrome-partitioning/README.md

# [OPEN] 131 - Palindrome Partitioning

[Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)

## notes

### first thoughts

- the word split by character will be at least one subset
- we can create a function `isPal` to run on every subset of the word
- we could eliminate word by being smart about remaining permutations not being
  palindromic across their midpoints.
- I misunderstood that `s` must be partitioned such that all members are
  themselves palindromes.

## summary

## tags

problems/00131-palindrome-partitioning/typescript/solution.ts

function partition(s: string): string[][] {
  const isPalindrome = (word: string) => {
    let result = true;
    for (let i = 0; i < word.length; i++) {
      const j = word.length - i;

      result = result && word[i] === word[j];
    }

    return result;
  };

  const partitions = [s.split("")];

  for (let i = 0; i < s.length - 1; i++) {
    for (let j = 2; j <= s.length; j++) {
      const maybePart = s.slice(0, j);

      if (isPalindrome(maybePart)) {
        partitions.push(maybePart);
      }
    }
  }

  return partitions;
}

export {};

problems/00146-lru-cache/README.md

# [SOLVED] 146 - LRU Cache

[LRU Cache](https://leetcode.com/problems/lru-cache/)

## notes

### first thoughts

- implementing `get` and `put` in O(1) means we will likely be using an array or
  a map (or both).
- need to keep track of the complete set of ordered cache values. so we know
  which to evict.
- thinking if an existing value is refreshed, we look it up, get its cacheOrder
  and, if necessary, move it to the front of the array.
- if we are adding a new value and have to evict we: remove the last value from
  the array and then delete it from the lookup.
- the `lookup` value will be like `{v: number, index: number, cacheOrder:
  number}`
- problem is that deleting from an array is not strictly O(n) as items may need
  to be rearranged.
- so maybe we can do it with fixed size array and... somehow keep another array
  of the indices?
- `get` always moves an item to the front. so worse case we move the last item
  to the front and shift all others.
- can implement a Doubly LinkedList-like structure within the map value that
  points to its `prev` and `next`. when `prev` is `undefined` it is already the
  most recently used. when `next` is `undefined` it is the end. we will also
  need to keep track of which word is `head` and which is `tail` so that when we
  fill the map we update the pointers correctly and so that when we reach
  capacity we can quickly determine which to evict (`tail`)

### simplified map

- saw a solution that took advantage of `Map` preserving insertion order when
  accessing `keys()` and decided to try it.

## summary

- first attempt was 100% memory but 13% compute. I don’t really know why it was
  so slow. comp.t: O(1) for all. comp.s: O(k) for capacity.
- simplified map was 94% memory but 50% compute. same comp.t: O(1) for
  all. comp.s: O(k) for capacity.

## tags

problems/00146-lru-cache/typescript/solution-doubly-linked-list.ts

type CacheValue = {
  prevKey?: number;
  nextKey?: number;
  value: number;
};

class LRUCache {
  lookup: Map<number, CacheValue>;
  count: number;
  capacity: number;
  headKey?: number;
  tailKey?: number;

  constructor(capacity: number) {
    this.lookup = new Map<number, CacheValue>();
    this.count = 0;
    this.capacity = capacity;
  }

  get(key: number): number {
    console.log("get:", { key });
    const maybeVal = this.lookup.get(key);

    if (maybeVal === undefined) {
      return -1;
    }

    /* we have the key already stored */
    if (maybeVal.prevKey === undefined) {
      /* nothing to do, we are already head */
    } else {
      this._stitchOutAndPromoteToHead(key, maybeVal, maybeVal.value);
    }

    return maybeVal.value;
  }

  put(key: number, value: number): void {
    console.log("put:", { key, value });
    const maybeVal = this.lookup.get(key);

    if (maybeVal === undefined) {
      /* evict if necessary */
      if (this.tailKey === undefined) {
        /* this is first value we have added */
        this.lookup.set(key, { value: value });
        this.count += 1;
        this.headKey = key;
        this.tailKey = key;
      } else if (this.capacity === 1) {
        if (this.headKey === undefined) {
          throw new Error("no head key when only size 1?");
        }
        this.lookup.delete(this.headKey);
        this.lookup.set(key, { value: value });
        this.headKey = key;
        this.tailKey = key;
      } else if (this.count < this.capacity) {
        /* we have more room to add */

        /* no eviction */
        /* tail stays the same */
        /* find headKey cache value */
        if (this.headKey === undefined) {
          throw new Error("no head key?");
        }

        const maybeHead = this.lookup.get(this.headKey);
        if (maybeHead === undefined) {
          throw new Error("no head?");
        }

        /* update it so prev now points to `key` */
        maybeHead.prevKey = key;
        this.lookup.set(this.headKey, maybeHead);

        /* create `key` cachevalue that points next to prev headKey */
        this.lookup.set(key, { value: value, nextKey: this.headKey });

        /* update the head key */
        this.headKey = key;

        if (this.capacity === 2) {
          /* special case: update tail */
          if (this.tailKey === undefined) {
            throw new Error("no tail key?");
          }

          const maybeTail = this.lookup.get(this.tailKey);
          if (maybeTail === undefined) {
            throw new Error("no tail?");
          }

          maybeTail.prevKey = key;
          this.lookup.set(this.tailKey, maybeTail);
        }

        /* update the count */
        this.count += 1;
      } else {
        /* evict */
        /* eviction required */
        /* find tail CacheValue */
        if (this.tailKey === undefined) {
          throw new Error("no tail key?");
        }

        const maybeTail = this.lookup.get(this.tailKey);
        if (maybeTail === undefined) {
          throw new Error("no tail?");
        }

        /* find prev */
        const maybeNewTailKey = maybeTail.prevKey;
        if (maybeNewTailKey === undefined) {
          throw new Error("no tail prev key?");
        }

        const newTail = this.lookup.get(maybeNewTailKey);
        if (newTail === undefined) {
          throw new Error("no new tail?");
        }

        /* update prev.next to undefined */
        newTail.nextKey = undefined;
        this.lookup.set(maybeNewTailKey, newTail);

        /* delete tail from lookup */
        this.lookup.delete(this.tailKey);

        /* update tail */
        this.tailKey = maybeNewTailKey;

        /* update head */
        if (this.headKey === undefined) {
          throw new Error("no head key?");
        }

        const maybeHead = this.lookup.get(this.headKey);
        if (maybeHead === undefined) {
          throw new Error("no head?");
        }

        /* update old head */
        maybeHead.prevKey = key;
        this.lookup.set(this.headKey, maybeHead);

        /* update new head */
        this.lookup.set(key, { value: value, nextKey: this.headKey });
        this.headKey = key;
      }
    } else {
      this._stitchOutAndPromoteToHead(key, maybeVal, value);
    }
  }

  _stitchOutAndPromoteToHead(
    key: number,
    cacheVal: CacheValue,
    newValue: number
  ) {
    const maybePrevKey = cacheVal.prevKey;
    /* we already exist. arrange correctly */
    if (maybePrevKey === undefined) {
      /* already head */
      cacheVal.value = newValue;
      this.lookup.set(key, cacheVal);
      return;
    }

    const maybePrev = this.lookup.get(maybePrevKey);
    if (maybePrev === undefined) {
      throw new Error("no prev?");
    }

    const maybeNextKey = cacheVal.nextKey;

    let maybeNext = undefined;
    if (maybeNextKey !== undefined) {
      maybeNext = this.lookup.get(maybeNextKey);
      if (maybeNext === undefined) {
        throw new Error("next val exists but no next?");
      }
    }

    if (this.headKey === undefined) {
      throw new Error("no head key?");
    }

    const maybeHead = this.lookup.get(this.headKey);
    if (maybeHead === undefined) {
      throw new Error("no head?");
    }

    /* stitch out */
    maybePrev.nextKey = maybeNextKey;
    this.lookup.set(maybePrevKey, maybePrev);

    if (maybeNextKey !== undefined && maybeNext !== undefined) {
      maybeNext.prevKey = maybePrevKey;
      this.lookup.set(maybeNextKey, maybeNext);
    } else {
      /* update tail */
      this.tailKey = maybePrevKey;
    }

    /* promote to head */
    cacheVal.prevKey = undefined;
    cacheVal.nextKey = this.headKey;
    cacheVal.value = newValue;
    this.lookup.set(key, cacheVal);

    maybeHead.prevKey = key;
    this.lookup.set(this.headKey, maybeHead);

    this.headKey = key;
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

const c1 = new LRUCache(2);
c1.put(1, 1); // cache is {1=1}
console.log(c1);
c1.put(2, 2); // cache is {1=1, 2=2}
console.log(c1);
console.log(c1.get(1)); // return 1
console.log(c1);
c1.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
console.log(c1);
console.log(c1.get(2)); // returns -1 (not found)
console.log(c1);
c1.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
console.log(c1);
console.log(c1.get(1)); // return -1 (not found)
console.log(c1);
console.log(c1.get(3)); // return 3
console.log(c1);
console.log(c1.get(4)); // return 4
console.log(c1);

const c2 = new LRUCache(2);
c2.put(1, 0);
console.log(c2);
c2.put(2, 2);
console.log(c2);

const c3 = new LRUCache(2);
c3.put(2, 1);
console.log(c3);
c3.put(2, 2);
console.log(c3);
console.log(c3.get(2));

const runTest = (commands: string[], args: number[][]) => {
  console.log("\n\n\n", "NEW TEST");
  const c = new LRUCache(args[0][0]);

  for (let i = 1; i < commands.length; i++) {
    const command = commands[i];
    const [k, v] = args[i];

    if (command === "put") {
      c.put(k, v);
    } else {
      c.get(k);
    }
    console.log(c);
  }
};

const tests = [
  {
    commands: [
      "LRUCache",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
    ],
    args: [
      [10],
      [7, 28],
      [7, 1],
      [8, 15],
      [6],
      [10, 27],
      [8, 10],
      [8],
      [6, 29],
      [1, 9],
      [6],
      [10, 7],
      [1],
      [2],
      [13],
      [8, 30],
      [1, 5],
      [1],
      [13, 2],
      [12],
    ],
  },
  {
    commands: [
      "LRUCache",
      "put",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "get",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "put",
      "put",
      "put",
    ],
    args: [
      [10],
      [10, 13],
      [3, 17],
      [6, 11],
      [10, 5],
      [9, 10],
      [13],
      [2, 19],
      [2],
      [3],
      [5, 25],
      [8],
      [9, 22],
      [5, 5],
      [1, 30],
      [11],
      [9, 12],
      [7],
      [5],
      [8],
      [9],
      [4, 30],
      [9, 3],
      [9],
      [10],
      [10],
      [6, 14],
      [3, 1],
      [3],
      [10, 11],
      [8],
      [2, 14],
      [1],
      [5],
      [4],
      [11, 4],
      [12, 24],
      [5, 18],
      [13],
      [7, 23],
      [8],
      [12],
      [3, 27],
      [2, 12],
      [5],
      [2, 9],
      [13, 4],
      [8, 18],
      [1, 7],
      [6],
      [9, 29],
      [8, 21],
      [5],
      [6, 30],
      [1, 12],
      [10],
      [4, 15],
      [7, 22],
      [11, 26],
      [8, 17],
      [9, 29],
      [5],
      [3, 4],
      [11, 30],
      [12],
      [4, 29],
      [3],
      [9],
      [6],
      [3, 4],
      [1],
      [10],
      [3, 29],
      [10, 28],
      [1, 20],
      [11, 13],
      [3],
      [3, 12],
      [3, 8],
      [10, 9],
      [3, 26],
      [8],
      [7],
      [5],
      [13, 17],
      [2, 27],
      [11, 15],
      [12],
      [9, 19],
      [2, 15],
      [3, 16],
      [1],
      [12, 17],
      [9, 1],
      [6, 19],
      [4],
      [5],
      [5],
      [8, 1],
      [11, 7],
      [5, 2],
      [9, 28],
      [1],
      [2, 2],
      [7, 4],
      [4, 22],
      [7, 24],
      [9, 26],
      [13, 28],
      [11, 26],
    ],
  },
];

let count = 0;
for (const { commands, args } of tests) {
  runTest(commands, args);
  count++;
  if (count === 2) {
    break;
  }
}

export {};

problems/00146-lru-cache/typescript/solution-simplified-map.ts

class LRUCache {
  lookup: Map<number, number>;
  capacity: number;

  constructor(capacity: number) {
    this.lookup = new Map<number, number>();
    this.capacity = capacity;
  }

  get(key: number): number {
    const maybeVal = this.lookup.get(key);

    if (maybeVal === undefined) {
      return -1;
    }

    /* delete and reinsert to preserve LRU insertion order */
    this.lookup.delete(key);
    this.lookup.set(key, maybeVal);
    return maybeVal;
  }

  put(key: number, value: number): void {
    if (this.lookup.has(key)) {
      /* delete and reinsert to preserve LRU insertion order */
      this.lookup.delete(key);
    }

    this.lookup.set(key, value);

    if (this.capacity < this.lookup.size) {
      /* evict */
      const lruKey = this.lookup.keys().next().value;
      this.lookup.delete(lruKey);
    }
  }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

const c1 = new LRUCache(2);
c1.put(1, 1); // cache is {1=1}
console.log(c1);
c1.put(2, 2); // cache is {1=1, 2=2}
console.log(c1);
console.log(c1.get(1)); // return 1
console.log(c1);
c1.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
console.log(c1);
console.log(c1.get(2)); // returns -1 (not found)
console.log(c1);
c1.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
console.log(c1);
console.log(c1.get(1)); // return -1 (not found)
console.log(c1);
console.log(c1.get(3)); // return 3
console.log(c1);
console.log(c1.get(4)); // return 4
console.log(c1);

const c2 = new LRUCache(2);
c2.put(1, 0);
console.log(c2);
c2.put(2, 2);
console.log(c2);

const c3 = new LRUCache(2);
c3.put(2, 1);
console.log(c3);
c3.put(2, 2);
console.log(c3);
console.log(c3.get(2));

const runTest = (commands: string[], args: number[][]) => {
  console.log("\n\n\n", "NEW TEST");
  const c = new LRUCache(args[0][0]);

  for (let i = 1; i < commands.length; i++) {
    const command = commands[i];
    const [k, v] = args[i];

    if (command === "put") {
      c.put(k, v);
    } else {
      c.get(k);
    }
    console.log(c);
  }
};

const tests = [
  {
    commands: [
      "LRUCache",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
    ],
    args: [
      [10],
      [7, 28],
      [7, 1],
      [8, 15],
      [6],
      [10, 27],
      [8, 10],
      [8],
      [6, 29],
      [1, 9],
      [6],
      [10, 7],
      [1],
      [2],
      [13],
      [8, 30],
      [1, 5],
      [1],
      [13, 2],
      [12],
    ],
  },
  {
    commands: [
      "LRUCache",
      "put",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "get",
      "put",
      "get",
      "get",
      "get",
      "put",
      "get",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "get",
      "get",
      "get",
      "put",
      "put",
      "put",
      "put",
      "get",
      "put",
      "put",
      "put",
      "put",
      "put",
      "put",
      "put",
    ],
    args: [
      [10],
      [10, 13],
      [3, 17],
      [6, 11],
      [10, 5],
      [9, 10],
      [13],
      [2, 19],
      [2],
      [3],
      [5, 25],
      [8],
      [9, 22],
      [5, 5],
      [1, 30],
      [11],
      [9, 12],
      [7],
      [5],
      [8],
      [9],
      [4, 30],
      [9, 3],
      [9],
      [10],
      [10],
      [6, 14],
      [3, 1],
      [3],
      [10, 11],
      [8],
      [2, 14],
      [1],
      [5],
      [4],
      [11, 4],
      [12, 24],
      [5, 18],
      [13],
      [7, 23],
      [8],
      [12],
      [3, 27],
      [2, 12],
      [5],
      [2, 9],
      [13, 4],
      [8, 18],
      [1, 7],
      [6],
      [9, 29],
      [8, 21],
      [5],
      [6, 30],
      [1, 12],
      [10],
      [4, 15],
      [7, 22],
      [11, 26],
      [8, 17],
      [9, 29],
      [5],
      [3, 4],
      [11, 30],
      [12],
      [4, 29],
      [3],
      [9],
      [6],
      [3, 4],
      [1],
      [10],
      [3, 29],
      [10, 28],
      [1, 20],
      [11, 13],
      [3],
      [3, 12],
      [3, 8],
      [10, 9],
      [3, 26],
      [8],
      [7],
      [5],
      [13, 17],
      [2, 27],
      [11, 15],
      [12],
      [9, 19],
      [2, 15],
      [3, 16],
      [1],
      [12, 17],
      [9, 1],
      [6, 19],
      [4],
      [5],
      [5],
      [8, 1],
      [11, 7],
      [5, 2],
      [9, 28],
      [1],
      [2, 2],
      [7, 4],
      [4, 22],
      [7, 24],
      [9, 26],
      [13, 28],
      [11, 26],
    ],
  },
];

let count = 0;
for (const { commands, args } of tests) {
  runTest(commands, args);
  count++;
  if (count === 2) {
    break;
  }
}

export {};

problems/00151-reverse-words-in-a-string/README.md

# [SOLVED] 151 - Reverse Words in a String

[Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/)

## notes

### first thoughts

- I am not sure the difficulty here. split on whitespace and reverse.
- added a filter because I split on the literal space character rather than some
  regex for whitespace

## summary

- 89th percentile performance

## tags

problems/00151-reverse-words-in-a-string/typescript/solution.ts

function reverseWords(s: string): string {
  const words = s.split(" ").filter((w) => 0 < w.length);
  words.reverse();
  return words.join(" ");
}

console.log(reverseWords("the sky is blue"));
console.log(reverseWords("  hello world  "));
console.log(reverseWords("a good   example"));

export {};

problems/00153-find-minimum-in-rotated-sorted-array/README.md

# [SOLVED] 153 - Find Minimum in Rotated Sorted Array

[Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

## notes

### golang thoughts

- sorted but rotated and O(log n) requirement makes me think binary search
- idea is to find the discontinuity. if not found just return the first element

## summary

- submitted accepted solution after iterating on logic for finding pivot. other
  solutions made search logic just normal binary search but not run with `l < r`
  and to not move `r` by `-1` (like I ended up doing).
- comp.t: O(log n) due to binary search
- comp.s: O(1) due to not using additional space

## tags

medium array
medium binary search

problems/00153-find-minimum-in-rotated-sorted-array/golang/solution.go

package main

import "fmt"

func findMin(nums []int) int {
	pivotIndex := -1
	for l, m, r := 0, -1, len(nums)-1; l <= r; {
		m = l + (r-l)/2
		if m+1 < len(nums) && nums[m+1] < nums[m] {
			pivotIndex = m
			break
		}

		// m is on left side of pivot
		if nums[l] < nums[m] && nums[r] < nums[m] {
			l = m + 1
		} else if nums[m] < nums[l] && nums[m] < nums[r] {
			r = m
		} else {
			// couldn't find it
			break
		}
	}

	if pivotIndex == -1 {
		return nums[0]
	}

	return nums[pivotIndex+1]
}

func main() {
	fmt.Println("answer:", findMin([]int{3, 4, 5, 1, 2}) == 1)
	fmt.Println("answer:", findMin([]int{4, 5, 6, 7, 0, 1, 2}) == 0)
	fmt.Println("answer:", findMin([]int{11, 13, 15, 17}) == 11)
	fmt.Println("answer:", findMin([]int{2, 3, 4, 5, 1}) == 1)
	fmt.Println("answer:", findMin([]int{4, 5, 1, 2, 3}) == 1)
}

problems/00153-find-minimum-in-rotated-sorted-array/typescript/solution.ts

/* nums is unique, so no [0,0,0] */

/* thoughts: */
/* rotate array until first and last are descending, then binary search */
/* trying to find where n[i] and n[i+1] (wrapped) are descending */
/* modified binary search where if right value is found smaller than left
value, means that that discontinuity is between them. we are always trying to
keep left value greater than right value. as soon as it is less, we are done */

/* [1] length 1 => n[0] minimum */
/* [2,1] length 2 => n[0] or n[1] minimum */
/* [2,3,1] length 3 =>  */

/* [3,4,5,1,2] */
/* 0: l=3, r=2, m=5 */
/* 1: l=1, r=2, m=1 */

/* [4,5,6,7,0,1,2] */
/* 0: l=4, r=2, m=7 */
/* 1: l=0, r=2, m=1 */

/* [11,13,15,17] */
/* 0: l=11, r=17, m=13 */

/* [2,1] */
/* 0: l=2, r=1, m=2 */
/* 1: l=1, r=1 */

/* [3,1,2] */
/* 0: l=3, r=2, m=1 */
/* 1: l=3, r=1, m=3 */

function findMin(nums: number[]): number {
  let leftIndex = 0;
  let rightIndex = nums.length - 1;

  let left = nums[leftIndex];
  let right = nums[rightIndex];

  while (right < left && leftIndex <= rightIndex) {
    const midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);
    const mid = nums[midIndex];

    if (left <= mid) {
      leftIndex = midIndex + 1;
    } else {
      /* move only by `midIndex`, rather than `midIndex-1`, because we need to
      compare the difference between the two, rather than find a single value
      */
      rightIndex = midIndex;
    }

    left = nums[leftIndex];
    right = nums[rightIndex];
  }

  return left;
}

console.log(findMin([2, 1]));
console.log(findMin([3, 1, 2]));

export {};

problems/00155-min-stack/README.md

# [SOLVED] 155 - Min Stack

[Min Stack](https://leetcode.com/problems/min-stack/)

## notes

### first thoughts

- to achieve O(1) operation likely need to use lookup or array
- can use two stacks one for the backing stack and the other for the `getMin`
  call

## summary

- comp.t: O(1) for all operations
- comp.s: O(n) need to store 2x how ever many n elements are pushed
- saw an alternative optimized way that used a length and single `[][2]int`
  where the val was stored in `0` and the min in `1`. this would reduce
  operations required in half.

## tags

medium stack
medium array

problems/00155-min-stack/golang/solution.go

package main

type MinStack struct {
	stack []int
	mins  []int
}

func Constructor() MinStack {

	return MinStack{[]int{}, []int{}}
}

func (this *MinStack) Push(val int) {
	this.stack = append(this.stack, val)

	if len(this.mins)-1 < 0 || val < this.mins[len(this.mins)-1] {
		this.mins = append(this.mins, val)
	} else {
		this.mins = append(this.mins, this.mins[len(this.mins)-1])
	}

}

func (this *MinStack) Pop() {
	this.mins = this.mins[:len(this.mins)-1]
	this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
	return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
	return this.mins[len(this.mins)-1]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

func main() {

}

problems/00155-min-stack/typescript/solution.ts

class MinStack {
  stack: number[];
  mins: number[];

  constructor() {
    this.stack = [];
    this.mins = [];
  }

  push(val: number): void {
    this.stack.push(val);

    if (this.mins.length === 0) {
      /* we have no min yet */
      this.mins.push(val);
    } else if (val < this.mins[this.mins.length - 1]) {
      /* this val is less than our current min */
      this.mins.push(val);
    } else {
      /* our current minimum is also the minimum after pushing val */
      this.mins.push(this.mins[this.mins.length - 1]);
    }
  }

  pop(): void {
    this.stack.pop();
    this.mins.pop();
  }

  top(): number {
    if (this.stack.length === 0) {
      return -1;
    }
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    if (this.mins.length === 0) {
      return -1;
    }
    return this.mins[this.mins.length - 1];
  }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

export {};

problems/00167-two-sum-ii---input-array-is-sorted/README.md

# [SOLVED] 167 - Two Sum II - Input Array is Sorted

[Two Sum II - Input Array is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)

## notes

## summary

## tags

medium array
medium two pointers

problems/00167-two-sum-ii---input-array-is-sorted/typescript/solution.ts

/* Your solution must use only constant extra space. */

function twoSum(numbers: number[], target: number): number[] {
  let leftPointer = 0;
  let rightPointer = numbers.length - 1;

  while (leftPointer < rightPointer) {
    const left = numbers[leftPointer];
    const right = numbers[rightPointer];

    const sum = left + right;

    if (sum === target) {
      return [leftPointer + 1, rightPointer + 1];
    } else if (sum < target) {
      leftPointer++;
    } else {
      rightPointer--;
    }
  }

  return [-1, -1];
}

export {};

problems/00199-binary-tree-right-side-view/README.md

# [SOLVED] 199 - Binary Tree Right Side View

[Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)

## notes

### first thoughts

- did not understand the problem until rereading “values of the nodes *you can
  see*”. so this means that we could return values that are on the “left” side
  of the tree but are only visible because of `null` right side values.
- first thought is to create an array for each “level” of the binary tree, and
  then just return the last values from it.
- another thought is to walk the tree depth first from right to left, keeping
  track of whether or not we have seen a node at the specified level. we prefer
  the first node we encounter for each level.
- the tree is not necessarily balanced, so we could have to visit every node of
  the tree, meaning comp.t is O(n)
- let’s do both solution approaches
- recursive: `helper` should go as deep as possible, preferring right side, and
  return an array of values seen at each level. it should take a value level
  which is used to set the first value it encounters in the array and increment
  it on depth.
- iter: should keep a list of each level and flatmap over the roots to figure
  out what the next course is.

## summary

- recursive. comp.t: O(n) we must visit every node
- recursive. comp.s (alg stack): O(n) in worst case, we must recursively dive
  down
- iter. comp.t: O(n) we must visit every node
- iter. comp.s (data structure): O(n) in worst case storing values in `output`
- iter. had implementation bug where adding the values to `level` via `flatMap`
  needed to be in order that ensured `[l,r]`, then `[r]`, then `[l]` were
  preferentially added.
- typescript solution, even with iter approach was only at 39% percentile. my
  guess is that the use of `flatMap` is not as fast as if I had just iterated
  directly
- golang 50th percentile for performance and am not sure the faster go solutions
  are really doing anything that fancy to learn from. I find them harder to
  read.

## tags

medium recursion
medium binary tree

problems/00199-binary-tree-right-side-view/golang/solution.go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
	var output []int
	var level []*TreeNode

	if root != nil {
		level = append(level, root)
	}

	for len(level) != 0 {
		// grab the rightmost val and add to output
		output = append(output, level[len(level)-1].Val)

		// build next level
		var nextLevel []*TreeNode

		for _, tn := range level {
			if tn.Left != nil {
				nextLevel = append(nextLevel, tn.Left)
			}

			if tn.Right != nil {
				nextLevel = append(nextLevel, tn.Right)
			}
		}

		level = nextLevel

	}

	return output
}

func main() {

}

problems/00199-binary-tree-right-side-view/typescript/solution.ts

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

const helperRecursive = (
  node: TreeNode | null,
  currentDepth: number,
  records: number[]
): number[] => {
  console.log({ node, currentDepth, records });
  if (node === null) {
    return records;
  }

  if (records[currentDepth] === undefined) {
    /* first time we have encountered it. set it */
    records[currentDepth] = node.val;
  }

  /* start descending preferring right side */
  let updatedRecords = helperRecursive(node.right, currentDepth + 1, records);
  updatedRecords = helperRecursive(node.left, currentDepth + 1, updatedRecords);

  return updatedRecords;
};

function rightSideView(root: TreeNode | null): number[] {
  return helperRecursive(root, 0, []);
}

function rightSideViewIter(root: TreeNode | null): number[] {
  /* goal with the iter approah is to keep track of each level */

  const output: number[] = [];

  let level: TreeNode[] = [root].flatMap((n) => {
    if (n === null) {
      return [];
    } else {
      return [n];
    }
  });

  while (level.length !== 0) {
    const rightMost = level[level.length - 1];
    output.push(rightMost.val);

    level = level.flatMap((n) => {
      if (n.left === null && n.right === null) {
        return [];
      }

      if (n.left !== null && n.right !== null) {
        return [n.left, n.right];
      }

      if (n.right !== null) {
        return [n.right];
      }

      if (n.left !== null) {
        return [n.left];
      }

      return [];
    });
  }

  return output;
}

console.log(rightSideView(null));
console.log(rightSideView(new TreeNode(1, null, new TreeNode(3))));
console.log(
  rightSideView(
    new TreeNode(
      1,
      new TreeNode(2, null, new TreeNode(5)),
      new TreeNode(3, null, new TreeNode(4))
    )
  )
);

console.log(rightSideViewIter(null));
console.log(rightSideViewIter(new TreeNode(1, null, new TreeNode(3))));
console.log(
  rightSideViewIter(
    new TreeNode(
      1,
      new TreeNode(2, null, new TreeNode(5)),
      new TreeNode(3, null, new TreeNode(4))
    )
  )
);

export {};

problems/00207-course-schedule/README.md

# [OPEN] 207 - Course Schedule

[Course Schedule](https://leetcode.com/problems/course-schedule/)

## notes

### first thoughts

- I do not fully understand if the prerequisites refer to the `numCourses`
  values specifically or just a label for any course?
- anyway my approach will be to create a lookup of `a` to all `b_i...j` and then
  check two things
  - whether we have visited a course before (cycle)
  - whether the count of walking the graph exceeds `numCourses`

## summary

## tags

problems/00207-course-schedule/typescript/solution.ts

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  /* create req lookup */
  const lookup = new Map<number, number[]>();
  for (const [a, b] of prerequisites) {
    const reqs = lookup.get(a) ?? [];
    reqs.push(b);

    lookup.set(a, reqs);
  }

  /* walk graph */
  const visited = new Set<number>();

  const helper = (requirement: number, coursesRemaining: number): boolean => {
    /* no more courses we can take */
    if (coursesRemaining < 0) {
      return false;
    }

    const requirements = lookup.get(requirement);

    /* no requirements left */
    if (requirements === undefined) {
      return true;
    }

    /* we have been here before: cycle! */
    if (visited.has(requirement)) {
      return false;
    }

    visited.add(requirement);

    /* can we also do all the requirements? */
    let result = true;
    for (const r of requirements) {
      result = result && helper(r, coursesRemaining--);
    }

    return result;
  };

  return helper(numCourses - 1, numCourses);
}

console.log(canFinish(2, [[1, 0]]));
console.log(
  canFinish(2, [
    [1, 0],
    [0, 1],
  ])
);

export {};

problems/00208-implement-trie-prefix-trie/README.md

# [SOLVED] 208 - Implement Trie (Prefix Trie)

[Implement Trie (Prefix Trie)](https://leetcode.com/problems/implement-trie-prefix-tree/)

## notes

### first thoughts

- can create using one map for word check and then a graph of maps for prefix
  search.
- thought initially that I could use a tree of tries, but wikipedia says that
  the root node is always the empty character.
- likely going to be kind of heavyweight creating a map for each character

## summary

- `solution-with-map.ts` was 37th percentile
- `solution-with-object.ts` was 80th percentile

## tags

problems/00208-implement-trie-prefix-trie/typescript/solution-with-map.ts

type TNode = {
  word: string;
  next: Map<string, TNode>;
};

class Trie {
  node: TNode;

  constructor() {
    this.node = { word: "", next: new Map<string, TNode>() };
  }

  insert(word: string): void {
    const chars = word.split("");

    let node = this.node;

    for (const c of chars) {
      let nextNode = node.next.get(c) ?? {
        word: "",
        next: new Map<string, TNode>(),
      };

      node.next.set(c, nextNode);

      node = nextNode;
    }

    node.word = word;
  }

  search(word: string): boolean {
    const chars = word.split("");

    let node = this.node;

    for (const c of chars) {
      let nextNode = node.next.get(c);

      if (nextNode === undefined) {
        break;
      } else {
        node = nextNode;
      }
    }

    return node.word === word;
  }

  startsWith(prefix: string): boolean {
    const chars = prefix.split("");

    let present = true;
    let node = this.node;

    for (const c of chars) {
      let nextNode = node.next.get(c);

      if (nextNode === undefined) {
        present = false;
        break;
      } else {
        node = nextNode;
      }
    }

    return present;
  }
}

const trie = new Trie();
console.log(trie.insert("apple"));
console.log(trie.search("apple")); // return True
console.log(trie.search("app")); // return False
console.log(trie.startsWith("app")); // return True
console.log(trie.insert("app"));
console.log(trie.search("app")); // return True

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

export {};

problems/00208-implement-trie-prefix-trie/typescript/solution-with-object.ts

type TNode = {
  word: string;
  children: { [key: string]: TNode };
};

class Trie {
  node: TNode;

  constructor() {
    this.node = { word: "", children: {} };
  }

  insert(word: string): void {
    const chars = word.split("");

    let node = this.node;

    for (const c of chars) {
      let nextNode = node.children[c] ?? {
        word: "",
        children: {},
      };

      node.children[c] = nextNode;

      node = nextNode;
    }

    node.word = word;
  }

  search(word: string): boolean {
    const chars = word.split("");

    let node = this.node;

    for (const c of chars) {
      let nextNode = node.children[c];

      if (nextNode === undefined) {
        break;
      } else {
        node = nextNode;
      }
    }

    return node.word === word;
  }

  startsWith(prefix: string): boolean {
    const chars = prefix.split("");

    let present = true;
    let node = this.node;

    for (const c of chars) {
      let nextNode = node.children[c];

      if (nextNode === undefined) {
        present = false;
        break;
      } else {
        node = nextNode;
      }
    }

    return present;
  }
}

const trie = new Trie();
console.log(trie.insert("apple"));
console.log(trie.search("apple")); // return True
console.log(trie.search("app")); // return False
console.log(trie.startsWith("app")); // return True
console.log(trie.insert("app"));
console.log(trie.search("app")); // return True

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

export {};

problems/00217-contains-duplicate/README.md

# [SOLVED] 217 - Contains Duplicate

[Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)

## notes

### first thoughts

- could sort and loop through checking if neighbors are same
- could create lookup of seen numbers

## summary

- comp.t: O(n) must iterate all elements
- comp.s: O(n) storing elements in lookup

## tags

easy array

problems/00217-contains-duplicate/golang/solution.go

package main

func containsDuplicate(nums []int) bool {
	lookup := make(map[int]bool, len(nums))

	var output bool
	for _, num := range nums {
		if _, ok := lookup[num]; ok {
			output = true
			break
		} else {
			lookup[num] = true
		}
	}

	return output
}

func main() {

}

problems/00217-contains-duplicate/typescript/solution.ts

/* time: O(n) */
/* space: O(n) */
function containsDuplicate(nums: number[]): boolean {
  /* cheeky */
  return new Set(nums).size !== nums.length;
}

/* time: O(n) but short circuits */
/* space: O(n) but short circuits */
function containsDuplicateAlt(nums: number[]): boolean {
  const lookup = new Set<number>();

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

    if (lookup.has(num)) {
      return true;
    }

    lookup.add(num);
  }

  return false;
}

console.log("orig:");

console.log(containsDuplicate([1, 2, 3, 1]));
console.log(containsDuplicate([1, 2, 3, 4]));
console.log(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]));

console.log("alt:");

console.log(containsDuplicateAlt([1, 2, 3, 1]));
console.log(containsDuplicateAlt([1, 2, 3, 4]));
console.log(containsDuplicateAlt([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]));

export {};

problems/00226-invert-binary-tree/README.md

# [SOLVED] 226 - Invert Binary Tree

[Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)

## notes

### first thoughts

- recursive, binary tree
- implementation should just swap right and left

## summary

- comp.t: O(n) must visit every node of the tree
- comp.s: O(log n), but could be O(n) in worst case for unbalanced tree.
- implemented correct solution. looked at other solutions and saw an alternative
  approach that I implemented. noted some clarity differences but it was more
  performant.

## tags

easy binary tree
easy recursive

problems/00226-invert-binary-tree/golang/solution.go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	oldLeft := root.Left
	root.Left = invertTree(root.Right)
	root.Right = invertTree(oldLeft)

	return root
}

// alternative implementation that eliminates multiple returns and temporary
// variable. I personally always feel weird calling recursive functions that
// return something and not actually doing anything with them, so even though
// this is performance improvement I do not think it improves readability.
func invertTreeAlt(root *TreeNode) *TreeNode {
	if root != nil {
		root.Left, root.Right = root.Right, root.Left

		invertTree(root.Left)
		invertTree(root.Right)
	}

	return root
}

func main() {

}

problems/00226-invert-binary-tree/typescript/solution.ts

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

/* first thoughts: */
/*  recursion */
/*  base case: swap left and right */

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  const left = root.left;
  const right = root.right;

  root.left = invertTree(right);
  root.right = invertTree(left);

  return root;
}

export {};

problems/00234-palindrome-linked-list/README.md

# [SOLVED] 234 - Palindrome Linked List

[Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/)

## notes

## summary

## tags

easy linked list

problems/00234-palindrome-linked-list/typescript/solution.ts

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function isPalindrome(head: ListNode | null): boolean {
  if (head === null) {
    return false;
  }

  // better idea: build two arrays and compare at end

  let ln: ListNode | null = head;
  let arr1: number[] = [];
  let arr2: number[] = [];
  while (ln !== null) {
    arr1.push(ln.val);
    arr2.unshift(ln.val);
    ln = ln.next;
  }

  for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] != arr2[i]) {
      return false;
    }
  }

  return true;
}

export {};

problems/00238-product-of-array-except-self/README.md

# [SOLVED] 238 - Product of Array Except Self

[Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)

## notes

### first thoughts

- cannot use division
- noticed that for `nums[i]` the value is the product of `nums[0]` to
  `nums[i-1]` multiplied by the product of `nums[i+1]` to `nums[nums.length-1]`
- solution approach will be to create two arrays: one containing the product of
  `nums[i]` from left to right and the other from right to left
- algorithm will be to multiply the `ltr[i-1]` and `rtl[i+1]` values

## summary

- comp.t: O(n): we loop through `nums` 3 times, so O(3n), but this reduces to O(n)
- comp.s: O(n): we create three arrays of size `n`

## tags

medium array

problems/00238-product-of-array-except-self/typescript/solution.ts

function productExceptSelf(nums: number[]): number[] {
  const ltr: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    const val = nums[i];
    if (i === 0) {
      ltr[i] = val;
    } else {
      ltr[i] = ltr[i - 1] * val;
    }
  }

  const rtl: number[] = [];
  for (let i = nums.length - 1; 0 <= i; i--) {
    const val = nums[i];
    if (i === nums.length - 1) {
      rtl[i] = val;
    } else {
      rtl[i] = rtl[i + 1] * val;
    }
  }

  /* optimization: could remove this and perform the multiplication during each
  iteration of `ltr` and `rtl` */
  const result: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    const ltrVal = ltr[i - 1] ?? 1;
    const rtlVal = rtl[i + 1] ?? 1;

    result[i] = ltrVal * rtlVal;
  }

  return result;
}

productExceptSelf([1, 2, 3, 4]);
productExceptSelf([-1, 1, 0, -3, 3]);

export {};

problems/00242-valid-anagram/README.md

# [SOLVED] 242 - Valid Anagram

[Valid Anagram](https://leetcode.com/problems/valid-anagram/)

## notes

- sort each string and then compare equality

## summary

- comp.t: O(sc log sc) + O(tc log tc) where sc and tc are the number of
  characters in s and t
- comp.s: O(sc + tc) a list for each
- highly optimized take advantage of `s` and `t` are only composed of lowercase
  English letters and create two `[26]int{}` that are populated via single
  passes through each string and then compared index by index. smart!
- typescript implementation takes different approach: it creates a lookup for
  each string and then compares the two. this avoids the sort.

## tags

easy string

problems/00242-valid-anagram/golang/solution.go

package main

import (
	"sort"
	"strings"
)

func isAnagram(s string, t string) bool {
	sc := strings.Split(s, "")
	sort.Strings(sc)

	tc := strings.Split(t, "")
	sort.Strings(tc)

	return strings.Join(sc, "") == strings.Join(tc, "")
}

func main() {

}

problems/00242-valid-anagram/typescript/solution.ts

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    /* no way that different lengths can be anagram */
    return false;
  }

  const createLookup = (str: string): Map<string, number> => {
    return str.split("").reduce((memo, c) => {
      const numOccurrences = memo.get(c);

      if (numOccurrences === undefined) {
        memo.set(c, 1);
      } else {
        memo.set(c, numOccurrences + 1);
      }

      return memo;
    }, new Map<string, number>());
  };

  const sLookup = createLookup(s);
  const tLookup = createLookup(t);

  if (sLookup.size !== tLookup.size) {
    return false;
  }

  let isAnagram = true;

  for (const [c, count] of sLookup) {
    isAnagram = isAnagram && tLookup.get(c) === count;

    if (!isAnagram) {
      break;
    }
  }

  return isAnagram;
}

console.log(isAnagram("anagram", "nagaram"));
console.log(isAnagram("rat", "car"));

export {};

problems/00322-coin-change/README.md

# [OPEN] 322 - Coin Change

[Coin Change](https://leetcode.com/problems/coin-change/)

## notes

### first thoughts

- divide sum by largest
- prompted / hinted that there are combinations that just dividing by largest
  will not work
- dynamic programming

## summary

## tags

problems/00322-coin-change/typescript/solution.ts

/* below is attempt to get version working that returns the list of
permutations. I am trying to improve upon what I did w/ dphil */
const coins = (
  remainingAmount: number,
  currentPermutation: number[],
  denoms: number[],
  lookup: Map<number, number[]>
): number[] => {
  console.log({ remainingAmount, currentPermutation, denoms, lookup });
  /* no more options */
  const foo = currentPermutation[currentPermutation.length - 1] ?? 0;
  if (remainingAmount - foo === 0) {
    return currentPermutation;
  }

  /* cannot make change */
  if (remainingAmount < 0 || denoms.length === 0) {
    return [];
  }

  /* have we already calculated the minimum for this amt before? */
  const maybeRemaining = lookup.get(remainingAmount);
  if (maybeRemaining !== undefined) {
    if (maybeRemaining.length === 0) {
      /* we cannot make it */
      return [];
    } else {
      currentPermutation.push(...maybeRemaining);
      return currentPermutation;
    }
  }

  let min = Number.MAX_SAFE_INTEGER;
  let choice: number[] = [];

  for (const d of denoms) {
    const newAmount = remainingAmount - d;
    const option = coins(
      newAmount,
      [d],
      denoms.filter((d) => d <= newAmount),
      lookup
    );

    if (option.length !== 0 && option.length < min) {
      choice = Array.from(option);
      choice.unshift(...currentPermutation);
      min = choice.length;
    }
  }

  lookup.set(remainingAmount, Array.from(choice));
  return choice;
};

function fewestCoinsNeeded(amount: number, denominations: number[]): number[] {
  return coins(
    amount,
    [],
    denominations.filter((d) => d <= amount),
    new Map<number, number[]>()
  );
}

/* console.log(fewestCoinsNeeded(7, [2, 3]));
 * console.log(fewestCoinsNeeded(1, [1, 5, 10, 25, 50]));
 * console.log(fewestCoinsNeeded(2, [1, 5, 10, 25, 50])); */
console.log(fewestCoinsNeeded(5, [1, 5, 10, 25, 50]));
/* console.log(fewestCoinsNeeded(147, [1, 5, 10, 25, 50])); */

export {};

problems/00347-top-k-frequent-elements/README.md

# [SOLVED] 347 - Top K Frequent Elements

[Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)

## notes

## summary

- comp.t O(n + n + n log n), O(n log n)
- comp.s O(n + n + n), O(n)
- should look at other solutions and revisit for improved performance

## tags

medium array
medium sort

problems/00347-top-k-frequent-elements/typescript/solution.ts

/* note: can improve nlogn with bst of the k elements to be nlogk */
function topKFrequent(nums: number[], k: number): number[] {
  /* thought: keep count of numbers in lookup, then iterate the lookup values
  (counts), sort them, and slice k */

  const countLookup = nums.reduce((memo, num) => {
    const count = memo.get(num);

    if (count === undefined) {
      memo.set(num, 1);
    } else {
      memo.set(num, count + 1);
    }

    return memo;
  }, new Map<number, number>());

  const stats = [];

  for (const [num, count] of countLookup) {
    stats.push({ num: num, count: count });
  }

  return stats
    .sort((a, b) => b.count - a.count)
    .map((s) => s.num)
    .slice(0, k);
}

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));
console.log(topKFrequent([1], 1));

export {};

problems/00383-ransom-note/README.md

# [SOLVED] 383 - Ransom Note

[Ransom Note](https://leetcode.com/problems/ransom-note/)

## notes

### first thoughts

- convert magazine into a set and remove when used in ransom note
- set needs to have counts of duplicate letters
- split the strings, sort them, group them into sub arrays, make a lookup out of
  magazine by letter, and then determine if there is enough by comparing the sub
  arrays
- I want to only read ransom note once, and then search magazine
- if I search for each character after iterating through ransome note, that
  would be quadratic n * n log(n)
- convert both to maps of counts and then compare

## summary

## tags

easy string

problems/00383-ransom-note/typescript/solution.ts

function canConstruct(ransomNote: string, magazine: string): boolean {
  // lets get base cases out of the way
  if (magazine.length < ransomNote.length) {
    return false;
  }

  const ransomLookup = ransomNote.split("").reduce((memo, char) => {
    const num = memo.get(char);
    if (num === undefined) {
      memo.set(char, 1);
    } else {
      memo.set(char, num + 1);
    }
    return memo;
  }, new Map<string, number>());

  const magazineLookup = magazine.split("").reduce((memo, char) => {
    const num = memo.get(char);
    if (num === undefined) {
      memo.set(char, 1);
    } else {
      memo.set(char, num + 1);
    }
    return memo;
  }, new Map<string, number>());

  // we only care if we can support ransom note creation
  for (const [char, ransomCount] of ransomLookup.entries()) {
    const maybeMagCount = magazineLookup.get(char);
    if (maybeMagCount === undefined || maybeMagCount < ransomCount) {
      return false;
    }
  }

  return true;
}

export {};

problems/00412-fizz-buzz/README.md

# [SOLVED] 412 - Fizz Buzz

[Fizz Buzz](https://leetcode.com/problems/fizz-buzz/)

## notes

## summary

## tags

easy

problems/00412-fizz-buzz/typescript/solution.ts

function fizzBuzz(n: number): string[] {
  const answer: string[] = [];
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      answer.push("FizzBuzz");
    } else if (i % 3 === 0) {
      answer.push("Fizz");
    } else if (i % 5 === 0) {
      answer.push("Buzz");
    } else {
      answer.push(String(i));
    }
  }

  return answer;
}

export {};

problems/00665-non-decreasing-array/README.md

# [OPEN] 665 - Non-decreasing Array

[Non-decreasing Array](https://leetcode.com/problems/non-decreasing-array/)

## notes

- array of length 1 is true
- array of length 2 is also true
- incorrect initial thought: array of length 3 is true if there is _only one_ x[i+1] < x[i]
- array of length 3 is false if you find non-decreasing and try changing either the first or second value and test


## summary

## tags

problems/00665-non-decreasing-array/typescript/solution.ts

const isSequentiallyNonDecreasing = (nums: number[], i: number): boolean => {
  const curr = nums[i];
  const next = nums[i + 1];

  console.log({ curr, next });

  return curr <= next;
};

const isNonDecreasing = (nums: number[]): boolean => {
  for (let i = 0; i <= nums.length - 2; i++) {
    if (isSequentiallyNonDecreasing(nums, i)) {
      /* do nothing */
    } else {
      return false;
    }
  }

  return true;
};

function checkPossibility(nums: number[]): boolean {
  if (nums.length === 1) {
    return true;
  }

  if (nums.length === 2) {
    return true;
  }

  let result = false;
  if (isNonDecreasing(nums)) {
    result = true;
  } else {
    /* we found a non decreasing sequence, try modifying positions  */

    let f_i = 0;
    for (let i = 0; i <= nums.length - 2; i++) {
      if (isSequentiallyNonDecreasing(nums, i)) {
        /* do nothing */
      } else {
        f_i = i;
        break;
      }
    }

    /* scenario: nums[f_i - 1] is out of bounds; try changing to nums[f_i + 1] */
    /* scenario: nums[f_i - 1] exists; try changing to nums[f_i - 1] */
    /* scenario: change nums[f_i + 1] to nums[f_i]  */

    if (f_i - 1 < 0) {
      const attempt1 = [...nums];
      attempt1[f_i] = attempt1[f_i + 1];

      result = isNonDecreasing(attempt1);
    } else {
      const attempt2 = [...nums];
      attempt2[f_i] = attempt2[f_i - 1];

      if (isNonDecreasing(attempt2)) {
        result = true;
      } else {
        const attempt3 = [...nums];
        attempt3[f_i + 1] = attempt3[f_i];

        if (isNonDecreasing(attempt3)) {
          result = true;
        }
      }
    }
  }

  return result;
}

console.log(checkPossibility([4, 2, 3]));
console.log(checkPossibility([4, 2, 1]));
console.log(checkPossibility([3, 4, 2, 3]));

export {};

problems/00704-binary-search/README.md

# [SOLVED] 704 - Binary Search

[Binary Search](https://leetcode.com/problems/binary-search/)

## notes

### first thoughts

- binary search due to sorted array

## summary

- comp.t: O(log n) due to halving problem space at each `midIndex` change
- comp.s: O(1) just returning index
- know binary search cold
- visualize items on a number line and asking yourself “what region do I want to
  be in?”

## tags

easy array
easy binary search

problems/00704-binary-search/golang/solution.go

package main

import "fmt"

func search(nums []int, target int) int {
	for l, r, m := 0, len(nums)-1, -1; l <= r; {
		m = l + (r-l)/2

		if nums[m] == target {
			return m
		} else if nums[m] < target {
			l = m + 1
		} else if target < nums[m] {
			r = m - 1
		} else {
			// can't happen
		}

	}

	return -1
}

func main() {
	fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 9))
	fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 2))
}

problems/00704-binary-search/typescript/solution.ts

function search(nums: number[], target: number): number {
  let index = -1;

  let leftIndex = 0;
  let rightIndex = nums.length - 1;

  while (leftIndex <= rightIndex) {
    let midIndex = Math.floor(leftIndex + (rightIndex - leftIndex) / 2);

    const maybeTarget = nums[midIndex];

    if (maybeTarget < target) {
      /* shift the left */
      leftIndex = midIndex + 1;
    } else if (target < maybeTarget) {
      /* shift the right */
      rightIndex = midIndex - 1;
    } else {
      /* found it */
      index = midIndex;
      break;
    }
  }

  return index;
}

export {};

problems/00739-daily-temperatures/README.md

# [SOLVED] 739 - Daily Temperatures

[Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)

## notes

### first thoughts

- last value will always be 0 as there are no more days ahead
- once we have passed a value and set its value it is no longer useful to us.
- idea. sort the temperatures, store a record of temp and value. for every
  value, find the temperature, then search that temperature + remaining for the
  smallest index.
- idea. when working backward from end, can we use the min days until greater
  temperature to determine future temperatures that will potentially be warmer?
- so you basically work backwards, check if n+1 is greater, if yes, you are done
  just put 1. otherwise look up the result array and see how many days you have
  to go before getting a warmer temperature than that. you know that this is
  necessarily the next largest temperature, otherwise you’d have a smaller
  number.
- smells kind of like dynamic programming because you can start at the end and
  work your way to beginning. the last value will always be 0.

## summary

- implemented accepted solution but had bug caught in test cases for condition
  entering while loop.
- also had unnecessary index check that I removed.
- comp.t: O(n) to check every temperature, and for each temperature `i` need to
  perform worst case `n - i` comparison operations (e.g. `temperature` contains
  a high value followed by much smaller but successively increasing values. I am
  not sure how this should be amortized.
- comp.s: O(n) storing `answer`

### for version `solution-stack.go`

- comp.t: O(n) and I think may be slightly better performance because you go
  through `temperatures` once O(n) and go through at most `n` values in `stack`,
  so this would be 2 * O(n). not clear to me which is better.
- comp.s: O(n) storing `answer` and `stack`

## tags

medium array
medium stack

problems/00739-daily-temperatures/golang/solution-original.go

package main

import "fmt"

func dailyTemperatures(temperatures []int) []int {
	// initialize our answers to 0s
	answer := make([]int, len(temperatures))
	for i := range answer {
		answer[i] = 0
	}

	// we know the last value will always be zero, so working backward from the
	// second to last index, calculate the future closest warmest day using
	// information we have already accumulated.
	for i := len(temperatures) - 2; 0 <= i; i-- {
		todaysTemp := temperatures[i]

		// try tomorrow as first guess for next warmest day
		candidateNextWarmestIndex := i + 1
		candidateNextWarmest := temperatures[candidateNextWarmestIndex]

		// if it isn't that is OK: we have already calculated how many days away
		// _that_ value is from the next warmest. use that information to jump
		// forward and see if that value is warmer than today
		for candidateNextWarmest <= todaysTemp {
			daysUntilNextWarmest := answer[candidateNextWarmestIndex]
			if daysUntilNextWarmest == 0 {
				// we are done, cannot find a warmer temperature
				break
			}

			// jump to this next warmer temperature. this should never jump beyond
			// the bounds
			candidateNextWarmestIndex += daysUntilNextWarmest
			candidateNextWarmest = temperatures[candidateNextWarmestIndex]
		}

		// we have looped through to find our best candidate. if it is warmer than
		// todays temp, set it. otherwise leave the default 0
		if todaysTemp < candidateNextWarmest {
			answer[i] = candidateNextWarmestIndex - i
		}
	}

	return answer
}

func main() {
	fmt.Println(dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76, 73}))
	fmt.Println(dailyTemperatures([]int{30, 40, 50, 60}))
	fmt.Println(dailyTemperatures([]int{30, 60, 90}))
	fmt.Println(dailyTemperatures([]int{89, 62, 70, 58, 47, 47, 46, 76, 100, 70}))
}

problems/00739-daily-temperatures/golang/solution-stack.go

package main

import "fmt"

type record struct {
	temp int
	idx  int
}

func dailyTemperatures(temperatures []int) []int {
	answer := make([]int, len(temperatures))
	var stack []record

	for i := 0; i < len(temperatures); i++ {
		for 0 < len(stack) && stack[len(stack)-1].temp < temperatures[i] {
			// we found a candidate
			record := stack[len(stack)-1]
			answer[record.idx] = i - record.idx

			// remove it from the stack
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, record{temperatures[i], i})
	}

	return answer
}

func main() {
	fmt.Println(dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76, 73}))
	fmt.Println(dailyTemperatures([]int{30, 40, 50, 60}))
	fmt.Println(dailyTemperatures([]int{30, 60, 90}))
	fmt.Println(dailyTemperatures([]int{89, 62, 70, 58, 47, 47, 46, 76, 100, 70}))
}

problems/00739-daily-temperatures/typescript/solution.ts

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = Array(temperatures.length).fill(0);

  for (let i = temperatures.length - 2; 0 <= i; i--) {
    const todaysTemp = temperatures[i];
    let candidateTemperatureIndex = i + 1;
    let candidateWarmerDayTemp = temperatures[candidateTemperatureIndex];

    while (candidateWarmerDayTemp <= todaysTemp) {
      const hopsUntilNextWarmerDay = answer[candidateTemperatureIndex];

      if (hopsUntilNextWarmerDay === 0) {
        /* no more warmer we are done */
        break;
      }

      candidateTemperatureIndex += hopsUntilNextWarmerDay;
      candidateWarmerDayTemp = temperatures[candidateTemperatureIndex];
    }

    if (todaysTemp < candidateWarmerDayTemp) {
      answer[i] = candidateTemperatureIndex - i;
    }
  }

  return answer;
}

console.log(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]));
console.log(dailyTemperatures([30, 40, 50, 60]));
console.log(dailyTemperatures([30, 60, 90]));

export {};

problems/00875-koko-eating-bananas/README.md

# [SOLVED] 875 - Koko Eating Bananas

[Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/)

## notes

### typescript first attempt

- could not solve, had to look up answer, did not understand utility of binary
  search

### golang implementation

- we need to determine `k`, the min eating speed
- we are told that `h` will always be greater than or equal to `piles.length`
- naive solution: try values of `k` starting at 1 until we have finished before
  `h`
- that is kind of the same as saying `k=[1,2,...,m]` where our upper bound `m`
  is `max(k_1, ..., k_i)`. if we find the max, we could then binary search
  values of k until we get the minimum `k` such that there are 0 left over
  bananas
- is there a smarter way though? sort the piles, `h-len(piles)` is the amount of
  “extra” cycles we have to eat more...I feel like there is a mathematical
  approach to do this minimization but I do not know it. going to try the binary
  search approach.
- calculation is: `num(piles) = sum(remainder piles[i] / k), stopping when h is
  less than zero`
- got memory exceeded error for creating `possibleK` of values rather than just
  using possible values of k directly.
- got time limit exceeded. needed to improve `bananasRemaining`
- got accepted answer, but still slow.
- optimization: no need to sort, just get max
- not seeing more optimization differences between this and top answers

## summary

- comp.t: assume `n = len(piles)` and `k = max(piles[i])`. we need O(log k) for
  finding optimal k, then for each of those perform O(n) operations to check the
  remaining bananas. so total I think is O(n log k).
- comp.s: O(1) no additional space

## tags

medium array
medium binary search

problems/00875-koko-eating-bananas/golang/solution.go

package main

import (
	"fmt"
)

func bananasRemaining(piles []int, h int, k int) int {
	var remaining int

	// had to make this faster
	for _, amt := range piles {
		if h < 0 {
			remaining += amt
			continue
		}

		// integer division ceiling
		neededH := 1 + (amt-1)/k

		var iter int
		if neededH <= h {
			// we can perform it
			iter = neededH
		} else {
			iter = h
		}

		h -= iter

		amt -= iter * k

		if 0 < amt {
			remaining += amt
		}
	}

	return remaining
}

func minEatingSpeed(piles []int, h int) int {
	var max int

	for _, size := range piles {
		if max < size {
			max = size
		}
	}

	var k int
	for l, m, r := 1, -1, max; l <= r; {
		m = l + (r-l)/2

		if bananasRemaining(piles, h, m) <= 0 {
			// we have a candidate, try a smaller value of k
			k = m
			r = m - 1
		} else {
			// we are not eating fast enough
			l = m + 1
		}

	}

	return k
}

func main() {
	fmt.Println(minEatingSpeed([]int{3, 6, 7, 11}, 8))
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 5))
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 6))

	// fmt.Println(bananasRemaining([]int{30, 11, 23, 4, 20}, 5, 26))
	// fmt.Println(bananasRemaining([]int{30, 11, 23, 4, 20}, 5, 27))
	// fmt.Println(bananasRemaining([]int{30, 11, 23, 4, 20}, 5, 28))
	// fmt.Println(bananasRemaining([]int{30, 11, 23, 4, 20}, 5, 29))
	// fmt.Println(bananasRemaining([]int{30, 11, 23, 4, 20}, 5, 30))
}

problems/00875-koko-eating-bananas/typescript/solution.ts

/* piles = [3,6,7,11], h = 8 */
/* k: 1...max(piles) */

function minEatingSpeed(piles: number[], h: number): number {
  if (piles.length === 1) {
    return Math.ceil(piles[0] / h);
  }

  let max = -1;
  for (let i = 0; i < piles.length; i++) {
    const maybeMax = piles[i];

    if (max < maybeMax) {
      max = maybeMax;
    }
  }

  /* idea: loop through piles to figure out how many hours it takes for a given k */
  const hoursPerCandidate = (candidate: number) => {
    return piles.reduce((memo, numBananas) => {
      memo += Math.ceil(numBananas / candidate);
      return memo;
    }, 0);
  };

  let left = 1;
  let right = max;
  let k = max;

  while (left <= right) {
    const maybeK = left + Math.floor((right - left) / 2);

    let maybeHours = hoursPerCandidate(maybeK);

    if (maybeHours <= h) {
      k = Math.min(k, maybeK);
      right = maybeK - 1;
    } else if (h < maybeHours) {
      left = maybeK + 1;
    } else {
      /* can't happen */
    }
  }

  return k;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8));
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));
console.log(minEatingSpeed([312884470], 312884469));

export {};

problems/00876-middle-of-the-linked-list/README.md

# [SOLVED] 876 - Middle of the Linked List

[Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

## notes

## summary

## tags

easy linked list

problems/00876-middle-of-the-linked-list/typescript/solution.ts

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

/* case: null */
/* case: head.next === null */
/* case: h1.next -> h2; h2.next -> null  */

function middleNode(head: ListNode | null): ListNode | null {
  if (head === null) {
    return null;
  }

  if (head.next === null) {
    return head;
  }

  /* we must have been passed an ll with at least two nodes */
  let middleNode = null;

  const arr = [];

  let current: ListNode | null = head;

  while (current) {
    arr.push(current);

    current = current.next;
  }

  if (arr.length % 2 === 0) {
    /* even: take second middle node */
    middleNode = arr[arr.length / 2];
  } else {
    /* odd: take middle node */
    middleNode = arr[Math.floor(arr.length / 2)];
  }

  return middleNode;
}

export {};

problems/00981-time-based-key-value-store/README.md

# [SOLVED] 981 - TIme Based Key-Value Store

[TIme Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/)

## notes

### first thoughts

- attempted typescript a few weeks ago and realized I needed to use a map but
  did not realize I need to use a binary search. had to look up solution and
  learn about binary search.

### golang implementation

- the criteria that the calls to `set` will be with timestamps that are strictly
  increasing is clue, but I am not sure how yet
- I can create a lookup that contains a slice of structs that contain both value
  and timestamp, but then I will have to search it for `get`, which I could use
  binary search on to be fast. is there a way I can do the lookup in O(1)?

## summary

- comp.t: Set: O(1), Get: O(log n)
- comp.s: O(n) for map object
- submitted working version that was similar to approach to others
- got hung up on how to implement binary search for non equality condition
  (e.g. the largest number lower than or equal to target)
- also got hung up thinking if there was an O(1) Get implementation
- noticed much more idiomatic golang code for implementation and did improved
  implementation


## tags

medium data structure
medium array
medium map
medium binary search

problems/00981-time-based-key-value-store/golang/solution-1.go

package main

import "fmt"

type TimestampVal struct {
	value     string
	timestamp int
}

type TimeMap struct {
	lookup map[string][]TimestampVal
}

func Constructor() TimeMap {
	m := make(map[string][]TimestampVal)

	return TimeMap{m}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	vals := this.lookup[key]

	if len(vals) == 0 {
		this.lookup[key] = []TimestampVal{{value, timestamp}}
	} else {
		vals = append(vals, TimestampVal{value, timestamp})
		this.lookup[key] = vals
	}

	fmt.Println(this.lookup)
}

func (this *TimeMap) Get(key string, timestamp int) string {
	if vals, ok := this.lookup[key]; ok {

		candidateIndex := -1
		// bs for closest without going over timestamp
		for l, m, r := 0, -1, len(vals)-1; l <= r; {
			m = l + (r-l)/2

			fmt.Println(l, m, r, timestamp, candidateIndex, vals)

			if vals[m].timestamp == timestamp {
				return vals[m].value
			}

			if timestamp < vals[m].timestamp {
				// our midpoint has overshot our timestamp, move r
				r = m - 1
			} else if vals[m].timestamp < timestamp {
				// our midpoint _could_ be a candidate
				if candidateIndex < vals[m].timestamp {
					// only update it if it is better than our previous
					candidateIndex = m
				}
				l = m + 1
			} else {
				// can't happen
			}
		}

		if candidateIndex != -1 {
			return vals[candidateIndex].value
		}

	}

	return ""
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */

func main() {
	obj := Constructor()
	obj.Set("foo", "bar", 1)
	fmt.Println(obj.Get("foo", 1))
	fmt.Println(obj.Get("foo", 3))
	obj.Set("foo", "bar2", 4)
	fmt.Println(obj.Get("foo", 4))
	fmt.Println(obj.Get("foo", 5))

}

problems/00981-time-based-key-value-store/golang/solution-2.go

package main

// this takes a more idiomatic approach and cleans up the binary search logic

type record struct {
	value     string
	timestamp int
}

type TimeMap struct {
	lookup map[string][]record
}

func Constructor() TimeMap {
	return TimeMap{
		lookup: map[string][]record{},
	}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	if _, ok := this.lookup[key]; !ok {
		// not found, set an empty
		this.lookup[key] = []record{}
	}

	this.lookup[key] = append(this.lookup[key], record{value, timestamp})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	var res string
	records := this.lookup[key]

	// bs for closest without going over timestamp
	for l, m, r := 0, -1, len(records)-1; l <= r; {
		m = l + (r-l)/2

		if records[m].timestamp == timestamp {
			//  we are done
			return records[m].value
		} else if timestamp < records[m].timestamp {
			// our midpoint has overshot our timestamp, move r
			r = m - 1
		} else if records[m].timestamp < timestamp {
			// our midpoint _could_ be a candidate. because of the way that binary
			// search works, our left pointer will never be decremented. this means
			// that if we get into this condition we know that we will have the
			// closest possible (at the moment) timestamp without going over

			res = records[m].value
			l = m + 1
		} else {
			// can't happen
		}
	}

	return res
}

problems/00981-time-based-key-value-store/typescript/solution.ts

/* thoughts: */

/*  - no removal to consider */
/*  - need to store all timestamped values for a given key */
/*  - max([timestamp_prev1, timestamp_prev2]) <= timestamp */
/*  - use a map as backing datastructure */
/*  - store an array of objects   */

type Recording = {
  timestamp: number;
  value: string;
};

/* space: O(n) */
class TimeMap {
  lookup: Map<string, Recording[]>;

  constructor() {
    this.lookup = new Map<string, Recording[]>();
  }

  /* time: O(1) */
  set(key: string, value: string, timestamp: number): void {
    const recordings = this.lookup.get(key) ?? [];
    recordings.push({ timestamp: timestamp, value: value });

    this.lookup.set(key, recordings);
  }

  /* time: O(1) + O(log n) */
  get(key: string, timestamp: number): string {
    const maybeRecordings = this.lookup.get(key) ?? [];

    let val = "";

    let leftIndex = 0;
    let rightIndex = maybeRecordings.length - 1;

    while (leftIndex <= rightIndex) {
      const midIndex = leftIndex + Math.floor((rightIndex - leftIndex) / 2);
      const mid = maybeRecordings[midIndex];

      if (mid.timestamp <= timestamp) {
        val = mid.value;
        leftIndex = midIndex + 1;
      } else {
        rightIndex = midIndex - 1;
      }
    }

    return val;
  }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

export {};

problems/01337-the-k-weakest-rows-in-a-matrix/README.md

# [SOLVED] 1337 - The K Weakest Rows in a Matrix

[The K Weakest Rows in a Matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/)

## notes

### golang implementation

- need to read every value (could stop when encounter a 0)
- need two items to do strength comparison: the number of soldiers and the index
  of the row.
- cannot do a fixed strength calculation because index only comes into play when
  comparing equivalent numbers of soldiers.
- feels like a map and sort

## summary

- comp.t: O(m + n) + O(m log m) because we sort so total O(n + m log m)
- comp.s: O(m) we store information for each row
- some optimizations are: use a min heap, use binary search to find the index of
  the last 1

## tags

easy matrix
easy array
easy sort

problems/01337-the-k-weakest-rows-in-a-matrix/golang/solution.go

package main

import "sort"

type regiment struct {
	cnt int
	idx int
}

func kWeakestRows(mat [][]int, k int) []int {
	var rows []regiment

	for i, val := range mat {
		var cnt int
		for _, s := range val {
			if s == 0 {
				break
			}
			cnt += s
		}

		rows = append(rows, regiment{cnt, i})
	}

	sort.Slice(rows, func(i, j int) bool {
		if rows[i].cnt == rows[j].cnt {
			return rows[i].idx < rows[j].idx
		}

		return rows[i].cnt < rows[j].cnt
	})

	var indices []int
	for _, reg := range rows {
		indices = append(indices, reg.idx)
	}

	return indices[:k]
}

func main() {

}

problems/01337-the-k-weakest-rows-in-a-matrix/typescript/solution.ts

function kWeakestRows(mat: number[][], k: number): number[] {
  return mat
    .map((row, i) => {
      return [
        row.reduce((memo, person) => {
          return (memo += person);
        }, 0),
        i,
      ];
    }) /* [[2,0], [4,1], [1,2], [2,3], [5, 4]] */
    .sort((a, b) => {
      if (a[0] === b[0]) {
        return a[1] - b[1];
      }

      return a[0] - b[0];
    }) /* [[1,2], [2,0], [2,3], [4,1], [5,4]] */
    .map((strength) => {
      return strength[1];
    }) /* [2, 0, 3, 1, 4] */
    .slice(0, k); /* [2, 0, 3] */
}

export {};

problems/01342-number-of-steps-to-reduce-a-number-to-zero/README.md

# [SOLVED] 1342 - Number of Steps to Reduce a Number to Zero

[Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)

## notes

### golang implementation thoughts

- perform the successive operations and keep count

## summary

- comp.t: O(log n)? we divide the space in half at every even number, but I do
  not know how many even numbers we will encounter for a given n. I do not
  remember how to tell which even numbers divide in half to other evens.
- comp.s: O(1)

## tags

easy math

problems/01342-number-of-steps-to-reduce-a-number-to-zero/golang/solution.go

package main

func numberOfSteps(num int) int {
	var count int
	for 0 < num {
		count += 1
		if num%2 == 0 {
			num /= 2
		} else {
			num -= 1
		}
	}

	return count
}

func main() {

}

problems/01342-number-of-steps-to-reduce-a-number-to-zero/typescript/solution.ts

function numberOfSteps(num: number): number {
  let count = 0;

  let reduced = num;

  while (reduced !== 0) {
    if (reduced % 2 === 0) {
      reduced = reduced / 2;
    } else {
      reduced = reduced - 1;
    }

    count++;
  }

  return count;
}

export {};

problems/01672-richest-customer-wealth/README.md

# [SOLVED] 1672 - Richest Customer Wealth

[Richest Customer Wealth](https://leetcode.com/problems/richest-customer-wealth/)

## notes

## summary

## tags

easy array

problems/01672-richest-customer-wealth/typescript/solution.ts

function maximumWealth(accounts: number[][]): number {
  return accounts /* [[1,5],[7,3],[3,5]] */
    .map((customerAccounts) => {
      return customerAccounts.reduce((memo, balance) => {
        return memo + balance;
      }, 0);
    }) /* [6,10,8] */
    .sort((a, b) => {
      return b - a;
    })[0];
}

export {};

problems/02281-sum-of-total-strength-of-wizards/README.md

# [OPEN] 2281 - Sum of Total Strength of Wizards

[Sum of Total Strength of Wizards](https://leetcode.com/problems/sum-of-total-strength-of-wizards/)

## notes

### first thoughts

- feels kind of like dynamic programming as `helper([1,3])` is the same as
  `helper([3,1])`
- if I sort the values added to `min` and `sum` I can use them as cache keys
- I cannot sort the entire `strength` as that would mess up the subarrays
- is there significance to the modulo being `10^9 + 7`?
- feels like I need two for loops to go through each permutation of
  subarray... not very efficient
- state will be the subarray
- transition function: `str = min(sub) * sum(sub)`
- comp.t: O(n^2) for operations times O(n log n) for the sort. O(n^3 log n)
  which is really bad. need to find a different approach

## summary

## tags

problems/02281-sum-of-total-strength-of-wizards/golang/attempt-1.go

package main

import (
	"fmt"
	"math"
	"sort"
)

func sum(input []int) int {
	var total int

	for _, val := range input {
		total += val
	}

	return total
}

func totalStrength(strength []int) int {

	normalization := (int(math.Pow(10, 9)) + 7)
	lookup := make(map[string]int)

	helper := func(input []int) int {
		sub := make([]int, len(input), cap(input))
		copy(sub, input)
		sort.Ints(sub)

		min := sub[0]
		total := sum(sub)

		key := fmt.Sprintf("%d-%d", min, total)

		if val, ok := lookup[key]; ok {
			return val
		}

		localStrength := min * total

		lookup[key] = localStrength

		return localStrength
	}

	var total int
	for i := 0; i < len(strength); i++ {
		for j := i + 1; j <= len(strength); j++ {
			total += helper(strength[i:j])
		}
	}

	return total % normalization
}

func main() {
	fmt.Println(totalStrength([]int{1, 3, 1, 2}))
	fmt.Println(totalStrength([]int{5, 4, 6}))
	fmt.Println(totalStrength([]int{747, 812, 112, 1230, 1426, 1477, 1388, 976, 849, 1431, 1885, 1845, 1070, 1980, 280, 1075, 232, 1330, 1868, 1696, 1361, 1822, 524, 1899, 1904, 538, 731, 985, 279, 1608, 1558, 930, 1232, 1497, 875, 1850, 1173, 805, 1720, 33, 233, 330, 1429, 1688, 281, 362, 1963, 927, 1688, 256, 1594, 1823, 743, 553, 1633, 1898, 1101, 1278, 717, 522, 1926, 1451, 119, 1283, 1016, 194, 780, 1436, 1233, 710, 1608, 523, 874, 1779, 1822, 134, 1984}))
}

problems/tsconfig.json

{
  "compilerOptions": {
    /* Visit https://aka.ms/tsconfig.json to read more about this file */

    /* Projects */
    // "incremental": true,                              /* Enable incremental compilation */
    // "composite": true,                                /* Enable constraints that allow a TypeScript project to be used with project references. */
    // "tsBuildInfoFile": "./",                          /* Specify the folder for .tsbuildinfo incremental compilation files. */
    // "disableSourceOfProjectReferenceRedirect": true,  /* Disable preferring source files instead of declaration files when referencing composite projects */
    // "disableSolutionSearching": true,                 /* Opt a project out of multi-project reference checking when editing. */
    // "disableReferencedProjectLoad": true,             /* Reduce the number of projects loaded automatically by TypeScript. */

    /* Language and Environment */
    "target": "es2016",                                  /* Set the JavaScript language version for emitted JavaScript and include compatible library declarations. */
    // "lib": [],                                        /* Specify a set of bundled library declaration files that describe the target runtime environment. */
    // "jsx": "preserve",                                /* Specify what JSX code is generated. */
    // "experimentalDecorators": true,                   /* Enable experimental support for TC39 stage 2 draft decorators. */
    // "emitDecoratorMetadata": true,                    /* Emit design-type metadata for decorated declarations in source files. */
    // "jsxFactory": "",                                 /* Specify the JSX factory function used when targeting React JSX emit, e.g. 'React.createElement' or 'h' */
    // "jsxFragmentFactory": "",                         /* Specify the JSX Fragment reference used for fragments when targeting React JSX emit e.g. 'React.Fragment' or 'Fragment'. */
    // "jsxImportSource": "",                            /* Specify module specifier used to import the JSX factory functions when using `jsx: react-jsx*`.` */
    // "reactNamespace": "",                             /* Specify the object invoked for `createElement`. This only applies when targeting `react` JSX emit. */
    // "noLib": true,                                    /* Disable including any library files, including the default lib.d.ts. */
    // "useDefineForClassFields": true,                  /* Emit ECMAScript-standard-compliant class fields. */

    /* Modules */
    "module": "commonjs",                                /* Specify what module code is generated. */
    "rootDir": "./",                                     /* Specify the root folder within your source files. */
    // "moduleResolution": "node",                       /* Specify how TypeScript looks up a file from a given module specifier. */
    // "baseUrl": "./",                                  /* Specify the base directory to resolve non-relative module names. */
    // "paths": {},                                      /* Specify a set of entries that re-map imports to additional lookup locations. */
    // "rootDirs": [],                                   /* Allow multiple folders to be treated as one when resolving modules. */
    // "typeRoots": [],                                  /* Specify multiple folders that act like `./node_modules/@types`. */
    // "types": [],                                      /* Specify type package names to be included without being referenced in a source file. */
    // "allowUmdGlobalAccess": true,                     /* Allow accessing UMD globals from modules. */
    // "resolveJsonModule": true,                        /* Enable importing .json files */
    // "noResolve": true,                                /* Disallow `import`s, `require`s or `<reference>`s from expanding the number of files TypeScript should add to a project. */

    /* JavaScript Support */
    // "allowJs": true,                                  /* Allow JavaScript files to be a part of your program. Use the `checkJS` option to get errors from these files. */
    // "checkJs": true,                                  /* Enable error reporting in type-checked JavaScript files. */
    // "maxNodeModuleJsDepth": 1,                        /* Specify the maximum folder depth used for checking JavaScript files from `node_modules`. Only applicable with `allowJs`. */

    /* Emit */
    // "declaration": true,                              /* Generate .d.ts files from TypeScript and JavaScript files in your project. */
    // "declarationMap": true,                           /* Create sourcemaps for d.ts files. */
    // "emitDeclarationOnly": true,                      /* Only output d.ts files and not JavaScript files. */
    // "sourceMap": true,                                /* Create source map files for emitted JavaScript files. */
    // "outFile": "./",                                  /* Specify a file that bundles all outputs into one JavaScript file. If `declaration` is true, also designates a file that bundles all .d.ts output. */
    // "outDir": "./",                                   /* Specify an output folder for all emitted files. */
    // "removeComments": true,                           /* Disable emitting comments. */
    // "noEmit": true,                                      /* Disable emitting files from a compilation. */
    // "importHelpers": true,                            /* Allow importing helper functions from tslib once per project, instead of including them per-file. */
    // "importsNotUsedAsValues": "remove",               /* Specify emit/checking behavior for imports that are only used for types */
    // "downlevelIteration": true,                       /* Emit more compliant, but verbose and less performant JavaScript for iteration. */
    // "sourceRoot": "",                                 /* Specify the root path for debuggers to find the reference source code. */
    // "mapRoot": "",                                    /* Specify the location where debugger should locate map files instead of generated locations. */
    // "inlineSourceMap": true,                          /* Include sourcemap files inside the emitted JavaScript. */
    // "inlineSources": true,                            /* Include source code in the sourcemaps inside the emitted JavaScript. */
    // "emitBOM": true,                                  /* Emit a UTF-8 Byte Order Mark (BOM) in the beginning of output files. */
    // "newLine": "crlf",                                /* Set the newline character for emitting files. */
    // "stripInternal": true,                            /* Disable emitting declarations that have `@internal` in their JSDoc comments. */
    // "noEmitHelpers": true,                            /* Disable generating custom helper functions like `__extends` in compiled output. */
    // "noEmitOnError": true,                            /* Disable emitting files if any type checking errors are reported. */
    // "preserveConstEnums": true,                       /* Disable erasing `const enum` declarations in generated code. */
    // "declarationDir": "./",                           /* Specify the output directory for generated declaration files. */
    // "preserveValueImports": true,                     /* Preserve unused imported values in the JavaScript output that would otherwise be removed. */

    /* Interop Constraints */
    // "isolatedModules": true,                          /* Ensure that each file can be safely transpiled without relying on other imports. */
    // "allowSyntheticDefaultImports": true,             /* Allow 'import x from y' when a module doesn't have a default export. */
    "esModuleInterop": true,                             /* Emit additional JavaScript to ease support for importing CommonJS modules. This enables `allowSyntheticDefaultImports` for type compatibility. */
    // "preserveSymlinks": true,                         /* Disable resolving symlinks to their realpath. This correlates to the same flag in node. */
    "forceConsistentCasingInFileNames": true,            /* Ensure that casing is correct in imports. */

    /* Type Checking */
    "strict": true,                                      /* Enable all strict type-checking options. */
    // "noImplicitAny": true,                            /* Enable error reporting for expressions and declarations with an implied `any` type.. */
    // "strictNullChecks": true,                         /* When type checking, take into account `null` and `undefined`. */
    // "strictFunctionTypes": true,                      /* When assigning functions, check to ensure parameters and the return values are subtype-compatible. */
    // "strictBindCallApply": true,                      /* Check that the arguments for `bind`, `call`, and `apply` methods match the original function. */
    // "strictPropertyInitialization": true,             /* Check for class properties that are declared but not set in the constructor. */
    // "noImplicitThis": true,                           /* Enable error reporting when `this` is given the type `any`. */
    // "useUnknownInCatchVariables": true,               /* Type catch clause variables as 'unknown' instead of 'any'. */
    // "alwaysStrict": true,                             /* Ensure 'use strict' is always emitted. */
    // "noUnusedLocals": true,                           /* Enable error reporting when a local variables aren't read. */
    // "noUnusedParameters": true,                       /* Raise an error when a function parameter isn't read */
    // "exactOptionalPropertyTypes": true,               /* Interpret optional property types as written, rather than adding 'undefined'. */
    // "noImplicitReturns": true,                        /* Enable error reporting for codepaths that do not explicitly return in a function. */
    // "noFallthroughCasesInSwitch": true,               /* Enable error reporting for fallthrough cases in switch statements. */
    // "noUncheckedIndexedAccess": true,                 /* Include 'undefined' in index signature results */
    // "noImplicitOverride": true,                       /* Ensure overriding members in derived classes are marked with an override modifier. */
    // "noPropertyAccessFromIndexSignature": true,       /* Enforces using indexed accessors for keys declared using an indexed type */
    // "allowUnusedLabels": true,                        /* Disable error reporting for unused labels. */
    // "allowUnreachableCode": true,                     /* Disable error reporting for unreachable code. */

    /* Completeness */
    // "skipDefaultLibCheck": true,                      /* Skip type checking .d.ts files that are included with TypeScript. */
    "skipLibCheck": true                                 /* Skip type checking all .d.ts files. */
  }
}

utilities/edits/edits.go

package main

import (
	"fmt"
	"io/fs"
	"io/ioutil"
	"log"
	"path/filepath"
	"regexp"
	"strings"
)

func main() {

	// take a directory
	filepath.Walk("../../problems", func(path string, info fs.FileInfo, err error) error {
		if err != nil {
			fmt.Printf("prevent panic by handling failure accessing a path %q: %v\n", path, err)
			return err
		}
		if ok, _ := regexp.MatchString(".*/node_modules/.*", path); ok {
			return nil
		}

		// find all files by a certain name, at any depth
		if ok, _ := regexp.MatchString(".*/README.md", path); ok {
			fmt.Println(path)

			input, err := ioutil.ReadFile(path)
			if err != nil {
				log.Fatalln(err)
			}

			// read their contents
			lines := strings.Split(string(input), "\n")

			// replace with "# [SOLVED]"
			firstLine := strings.Split(lines[0], " ")
			firstLine = append(firstLine[:2], firstLine[1:]...)
			firstLine[1] = "[SOLVED]"

			lines[0] = strings.Join(firstLine, " ")

			// rewrite files
			output := strings.Join(lines, "\n")
			err = ioutil.WriteFile(path, []byte(output), 0644)
			if err != nil {
				log.Fatalln(err)
			}
		}

		return nil
	})

}

utilities/edits/go.mod

module github.com/klandergren/leetcode/utilities/edits

go 1.19

utilities/leet/go.mod

module github.com/klandergren/leetcode/utilities/leet

go 1.19

utilities/leet/leet.go

package main

import (
	"errors"
	"flag"
	"fmt"
	"log"
	"os"
	"strings"
)

func main() {
	const (
		DefaultNumber   = -1
		DefaultTitle    = ""
		DefaultLanguage = ""
		DefaultURL      = ""
	)

	supportedLanguageSolutionFilenameLookup := map[string]string{
		"typescript": "solution.ts",
		"golang":     "solution.go",
	}

	supportedLanguageSolutionFilecontentsLookup := map[string]string{
		"typescript": "\n\nexport{};",
		"golang":     "package main\n\nfunc main() {\n\n}\n",
	}

	numberFlag := flag.Int("number", DefaultNumber, "the problem number")
	titleFlag := flag.String("title", DefaultTitle, "the problem title")
	languageFlag := flag.String("language", DefaultLanguage, "the solution language")
	urlFlag := flag.String("url", DefaultURL, "the problem URL")

	flag.Parse()

	if *numberFlag == DefaultNumber {
		log.Fatal("missing --number flag")
	}

	if *titleFlag == DefaultTitle {
		log.Fatal("missing --title flag")
	}

	if *languageFlag == DefaultLanguage {
		log.Fatal("missing --language flag")
	}

	if *urlFlag == DefaultURL {
		log.Fatal("missing --url flag")
	}

	solutionFileName, ok := supportedLanguageSolutionFilenameLookup[*languageFlag]

	if !ok {
		log.Fatal("language not supported")
	}

	// number
	problemNumber := fmt.Sprintf("%05d", *numberFlag)

	// title
	lowerCaseTitle := strings.ToLower(*titleFlag)
	titleComponents := strings.Split(lowerCaseTitle, " ")
	cleanedTitle := strings.Join(titleComponents, "-")

	// directories
	problemDirectory := fmt.Sprintf("problems/%s-%s", problemNumber, cleanedTitle)
	languageSolutionDirectory := fmt.Sprintf("%s/%s", problemDirectory, *languageFlag)

	// files
	readmeFilePath := fmt.Sprintf("%s/README.md", problemDirectory)
	readmeText := fmt.Sprintf("# [OPEN] %d - %s\n\n[%s](%s)\n\n## notes\n\n## summary\n\n## tags\n\n", *numberFlag, *titleFlag, *titleFlag, *urlFlag)

	solutionFilePath := fmt.Sprintf("%s/%s", languageSolutionDirectory, solutionFileName)
	solutionText, ok := supportedLanguageSolutionFilecontentsLookup[*languageFlag]
	if !ok {
		log.Fatal("language not supported")
	}

	// create directories
	os.MkdirAll(languageSolutionDirectory, 0755)

	// create files
	readme, err := os.OpenFile(readmeFilePath, os.O_RDWR|os.O_CREATE|os.O_EXCL, 0755)
	defer readme.Close()
	if err != nil {
		if errors.Is(err, os.ErrExist) {
			log.Printf("could not create %s. skipping. message: %v\n", readmeFilePath, err)
		} else {
			log.Fatalf("could not create %s. message: %v\n", readmeFilePath, err)
		}
	} else {
		fmt.Fprintln(readme, readmeText)
	}

	solution, err := os.OpenFile(solutionFilePath, os.O_RDWR|os.O_CREATE|os.O_EXCL, 0755)
	defer solution.Close()
	if err != nil {
		if errors.Is(err, os.ErrExist) {
			log.Printf("could not create %s. skipping. message: %v\n", solutionFilePath, err)
		} else {
			log.Fatalf("could not create %s. message: %v\n", solutionFilePath, err)
		}
	} else {
		fmt.Fprintln(solution, solutionText)
	}

}