
> You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
>
> Merge all the linked-lists into one sorted linked-list and return it.
>
> Input: lists = [[1,4,5],[1,3,4],[2,6]]  
> Output: [1,1,2,3,4,4,5,6]
>
> Explanation: The linked-lists are:  
> [1->4->5,1->3->4,2->6]
>
> merging them into one sorted list:  
> 1->1->2->3->4->4->5->6

```ts
// Priority Queue (Min Heap) solution:
const mergeKLists = (lists: Array<ListNode | null>): ListNode | null => {
  let dummy = new ListNode(0)
  const pq = new Heap()<ListNode>(null, (a, b) => b.val - a.val)

  for (let l of lists) {
    if (l) pq.offer(l)
  }

  let cur = dummy
  while (!pq.isEmpty()) {
    cur.next = pq.poll()
    if (cur.next.next) {
      pq.offer(cur.next.next)
    }
    cur = cur.next
  }

  return dummy.next
}

type Comparator<T> = (a: T, b: T) => number

class Heap<T> {
  items: T[]
  comparator: Comparator<T>

  constructor(list: T[] | null, comparator: Comparator<T>) {
    this.items = list || []
    this.comparator = comparator
    this.buildHeap()
  }

  buildHeap(): void {
    for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
      this.moveDown(i)
    }
  }

  moveDown(curIdx: number): void {
    const lastIndex = this.size() - 1
    const items = this.items
    while (this.leftChild(curIdx) <= lastIndex) {
      let i = this.leftChild(curIdx)

      // if i is not the last element -> compare i with i+1
      // if i was the last element, i+1 would give us index out of bound!
      if (i < lastIndex && this.comparator(items[i], items[i + 1]) < 0) {
        i++
      }

      if (this.comparator(items[i], items[curIdx]) < 0) {
        break
      }

      this.exchange(curIdx, i)
      curIdx = i
    }
  }

  moveUp(curIdx: number): void {
    while (curIdx > 0) {
      let parent = this.parent(curIdx)
      if (this.comparator(this.items[curIdx], this.items[parent]) < 0) break
      this.exchange(parent, curIdx)
      curIdx = parent
    }
  }

  offer(value: T) {
    this.items.push(value)
    this.moveUp(this.size() - 1)
  }

  poll(): T | null {
    if (this.size() === 0) return null

    const item = this.items[0]
    const last = this.items.pop()

    if (this.size() && last) {
      this.items[0] = last
      this.moveDown(0)
    }

    return item
  }

  leftChild(parent: number): number {
    return 2 * parent + 1
  }

  rightChild(parent: number): number {
    return 2 * parent + 2
  }

  parent(child: number): number {
    return Math.floor((child - 1) / 2)
  }

  peek(): T {
    return this.items[0]
  }

  size(): number {
    return this.items.length
  }

  isEmpty(): boolean {
    return this.size() === 0
  }

  exchange(i: number, j: number): void {
    let temp = this.items[i]
    this.items[i] = this.items[j]
    this.items[j] = temp
  }
}
```


Merge K Sorted Lists


> Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
>
> An input string is valid if:
>
> 1. Open brackets must be closed by the same type of brackets.
> 2. Open brackets must be closed in the correct order.
> 3. Every close bracket has a corresponding open bracket of the same type.
>
> Input: s = "()"  
> Output: true
>
> Input: s = "(]"  
> Output: false

```js
const peak = (st) => st[st.length - 1];

const isValid = function (s) {
  if (!s || s.length === 1) return false;

  const st = [];
  const openBrackets = ["{", "(", "["];
  const map = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  let i = 0;
  while (i < s.length) {
    const curChar = s[i++];
    if (openBrackets.includes(curChar)) {
      st.push(curChar);
      continue;
    }

    if (peak(st) !== map[curChar]) {
      return false;
    }

    st.pop();
  }

  if (st.length) {
    return false;
  }

  return true;
};
```


Valid Parentheses


> Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
>
> Implement the Solution class:
>
> 1. Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
> 2. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
>
> **Follow up:**
>
> 1. What if the linked list is extremely large and its length is unknown to you?
> 2. Could you solve this efficiently without using extra space?

```js
const Solution = function (head) {
  this.indexMap = [];

  let cur = head;
  let curIdx = 0;
  while (cur) {
    this.indexMap[curIdx++] = cur.val;
    cur = cur.next;
  }
};

Solution.prototype.getRandom = function () {
  const rand = Math.floor(Math.random() * this.indexMap.length);
  return this.indexMap[rand];
};
```

> The follow up question with unknown size of linked list would require understanding of **Reservoir Sampling**.
>
> - [this](https://leetcode.com/problems/linked-list-random-node/solutions/85662/java-solution-with-cases-explain/)
> - [this](https://gregable.com/2007/10/reservoir-sampling.html)


Linked List Random Node


> Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
>
> Input: n = 3  
> Output: ["((()))","(()())","(())()","()(())","()()()"]
>
> Input: n = 1  
> Output: ["()"]

```js
const generateParenthesis = function (n) {
  const res = [];
  generate(n, n, "", n, res);
  return res;
};

const generate = (left, right, temp, n, res) => {
  if (temp.length === 2 * n) {
    res.push(temp);
    return;
  }

  if (left > 0) {
    generate(left - 1, right, temp + "(", n, res);
  }

  // can place right only if left is already placed
  if (right > left) {
    generate(left, right - 1, temp + ")", n, res);
  }
};
```

> ")" can only chosen when their "remaining" pool is **bigger** than "(". Which means more "(" have been used already as compared to ")", now it's okay to pick ")" to complete valid parenthesis.
>
> At any moment or choice, number of ")" used cannot be more than "(" used.
>
> ()) -> Wrong! The choice of last ")" is wrong because the number of ")" used is now more than "(" used.

```js
// Good stack based solution to avoid recursion
const generateParenthesis = function (n) {
  const res = [];
  const stack = [["(", 1, 0]];

  // these open and close are the count of each that are already
  // used/added to the curRes string.
  while (stack.length) {
    const [curRes, open, close] = stack.pop();

    if (curRes.length === 2 * n) {
      res.push(curRes);
      continue;
    }

    if (open < n) {
      stack.push([curRes + "(", open + 1, close]);
    }

    if (open > close) {
      stack.push([curRes + ")", open, close + 1]);
    }
  }

  return res;
};
```


Generate Parentheses


> You are given the heads of two sorted linked lists list1 and list2.
>
> Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
>
> Return the head of the merged linked list.
>
> Input: list1 = [1,2,4], list2 = [1,3,4]  
> Output: [1,1,2,3,4,4]

```js
const mergeTwoLists = function (list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  const res = new ListNode();
  let cur = res;

  while (list1 && list2) {
    const v1 = list1.val;
    const v2 = list2.val;

    if (v1 <= v2) {
      cur.next = list1;
      list1 = list1.next;
    } else if (v1 > v2) {
      cur.next = list2;
      list2 = list2.next;
    }

    cur = cur.next;
  }

  cur.next = list1 || list2;

  return res.next;
};
```

```js
// Recursive
const mergeTwoLists = function (l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;

  if (l1.val > l2.val) {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  } else {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  }
};
```


Merge Two Sorted Lists


> Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
>
> There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
>
> Do not modify the linked list.
>
> Input: head = [3,2,0,-4], pos = 1  
> Output: tail connects to node index 1  
> Explanation: There is a cycle in the linked list, where tail connects to the second node.

```js
// This solution is more cleaner than the second one
const detectCycle = function (head) {
  if (!head) return null;

  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      break;
    }
  }

  if (!fast || !fast.next) {
    return null;
  }

  let cur = head;
  while (slow !== cur) {
    slow = slow.next;
    cur = cur.next;
  }

  return cur;
};
```

```js
const detectCycle = function (head) {
  if (!head) return null;

  let slow = head;
  let fast = head;

  while (slow && fast) {
    slow = slow.next;
    fast = fast.next;
    fast = fast && fast.next;

    if (slow === fast) {
      break;
    }
  }

  if (!fast) {
    return null;
  }

  let cur = head;
  while (slow !== cur) {
    slow = slow.next;
    cur = cur.next;
  }

  return cur;
};
```


Linked List Cycle II


```js
// Boundary check
const isOffBoundary = (grid, r, c) => {
  return r < 0 || c < 0 || r >= grid.length || c >= grid[0].length;
};

// Iterative DFS
var numIslands = function (grid) {
  if (!grid.length || !grid[0].length) {
    return 0;
  }

  const Dir = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const rowsLen = grid.length;
  const colsLen = grid[0].length;
  let count = 0;

  for (let r = 0; r < rowsLen; r++) {
    for (let c = 0; c < colsLen; c++) {
      if (grid[r][c] === "1") {
        count++;
        const stack = [[r, c]];
        while (stack.length > 0) {
          const coord = stack.pop();
          grid[coord[0]][coord[1]] = "0";

          for (const [dr, dc] of Dir) {
            const nr = coord[0] + dr;
            const nc = coord[1] + dc;

            if (isOffBoundary(grid, nr, nc) || grid[nr][nc] === "0") {
              continue;
            }

            stack.push([nr, nc]);
          }
        }
      }
    }
  }

  return count;
};
```

```js
// Boundary check
const isOffBoundary = (grid, r, c) => {
  return r < 0 || c < 0 || r >= grid.length || c >= grid[0].length;
};

// Recursive DFS
var numIslands = function (grid) {
  if (!grid.length || !grid[0].length) {
    return 0;
  }

  const rowsLen = grid.length;
  const colsLen = grid[0].length;
  let count = 0;

  for (let r = 0; r < rowsLen; r++) {
    for (let c = 0; c < colsLen; c++) {
      if (grid[r][c] === "1") {
        count++;
        explore(grid, r, c);
      }
    }
  }

  return count;
};

const explore = (grid, r, c) => {
  if (isOffBoundary(grid, r, c) || grid[r][c] === "0") {
    return;
  }

  grid[r][c] = "0";
  explore(grid, r + 1, c);
  explore(grid, r - 1, c);
  explore(grid, r, c + 1);
  explore(grid, r, c - 1);
};
```

```js
// Union Find
class DSU {
  constructor(LEN) {
    this.sets = [...Array(LEN).keys()];
  }

  find(x) {
    if (this.sets[x] !== x) {
      return (this.sets[x] = this.find(this.sets[x]));
    }

    return x;
  }

  union(x, y) {
    if (this.sets[x] === this.sets[y]) {
      return;
    }

    x = this.find(x);
    y = this.find(y);

    this.sets[x] = y;
  }

  findComponents() {
    let count = 0;
    for (let i = 0; i < this.sets.length; i++) {
      if (this.sets[i] === i) {
        count++;
      }
    }

    return count;
  }

  markInvalid(x) {
    this.sets[x] = -1;
  }
}

var numIslands = function (grid) {
  if (!grid || !grid.length) return 0;

  const DIRS = [
    [1, 0],
    [0, 1],
  ]; // only 2 direction - bottom and right
  const ROWS = grid.length;
  const COLS = grid[0].length;
  const dsu = new DSU(ROWS * COLS);
  const isValid = (r, c) =>
    r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] === "1";
  const normalize = (r, c) => r * COLS + c;

  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (grid[r][c] === "1") {
        for (let [dr, dc] of DIRS) {
          let nr = r + dr;
          let nc = c + dc;
          if (!isValid(nr, nc)) {
            continue;
          }
          dsu.union(normalize(r, c), normalize(nr, nc));
        }
      } else {
        dsu.markInvalid(normalize(r, c));
      }
    }
  }

  return dsu.findComponents();
};
```

> Union Find Tip:  
> Normalise MxN matrix's coordinates. (r \* COLS) + c


Number of Islands


> Given the head of a linked list, remove the nth node from the end of the list and return its head.
>
> Input: head = [1,2,3,4,5], n = 2  
> Output: [1,2,3,5]

```js
const removeNthFromEnd = function (head, n) {
  if (!head) return head;

  let lead = head;
  let follow = head;

  // if n > len(linked list), this will fail.
  // Always check if n can be greater than the len.
  // If yes, add the check before this condition.
  for (let i = 0; i < n; i++) {
    lead = lead.next;
  }

  // This is important for a case when n == len(linked list)
  // 1 -> 2 -> null, n = 2
  //
  // i = 0; i < n; i++
  //
  // cur
  // 1 -> 2 -> null, beginning of loop
  //
  //      cur
  // 1 -> 2 -> null, after i = 0 cycle runs
  //
  //           cur
  // 1 -> 2 -> null, after i = 1 cycle runs
  //
  // In this case when n == len(linked list), we basically
  // want to remove the first element of the list.
  // so your head becomes head.next
  if (!lead) {
    return head.next;
  }

  while (lead.next) {
    follow = follow.next;
    lead = lead.next;
  }

  follow.next = follow.next.next;
  return head;
};
```


Remove Nth node from end of the list


> Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
>
> A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
>
> Input: digits = "23"  
> Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

```js
const letterCombinations = function (digits) {
  if (!digits) return []

  const map = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  }

  // We add all 3 or 4 characters of a given digit
  // to the "so-far" calculated result, one by one.
  //
  // Consider the so-far result as ["a", "b", "c"].
  // The given digit is 4, so its characters are: "g", "h", "i"
  // So we add each character to each element of the result.
  // ["ag", "bg", "cg"]

  let ans = ['']
  for (let i = 0; i < digits.length; i++) {
    const temp = []
    const curDigit = digits[i]
    const letters = map[curDigit]

    for (const l of letters) {
      for (const a of ans) {
        temp.push(a + l)
      }
    }

    ans = temp
  }

  return ans
}
```

```js
const letterCombinations = function (digits) {
  if (!digits) return []

  const map = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  }

  // For a given digits: 23, the pressed will look like this
  // ["abc", "def"]
  // Now, go like this:
  // a -> def
  // ad, ae, af
  // b -> def
  // bd, be, bf
  // c -> def
  // cd, ce, cf

  const pressed = []
  for (const d of digits) {
    pressed.push(map[d])
  }

  let ans = []
  function iterator(start, str) {
    if (start >= pressed.length) {
      ans.push(str)
      return
    }

    const curStr = pressed[start]
    for (let idx = 0; idx < curStr.length; idx++) {
      const curChar = curStr[idx]
      iterator(start + 1, str + curChar)
    }
  }

  iterator(0, '')
  return ans
}
```


Letter Combinations of a Phone Number


> Given a string s, find the length of the longest substring without repeating characters.
>
> Input: s = "abcabcbb"  
> Output: 3  
> Explanation: The answer is "abc", with the length of 3.

```js
// Approach 1
// Calculate maxLen every time, and adjust start when already seen character is found.
const lengthOfLongestSubstring = function (s) {
  if (!s) return 0;

  let start = 0;
  let end = 0;
  let map = new Map();
  let res = 0;

  while (end < s.length) {
    let curChar = s[end];
    if (map.has(curChar)) {
      const seenIdx = map.get(curChar);
      // make sure you don't jump back to the wrong index.
      // ex: abba
      // when looking at the second 'a', don't jump back to
      // first 'b' (seenIdx + 1). This is wrong because
      // you are now considering two 'b's.
      // Instead, use the below condition.
      start = Math.max(seenIdx + 1, start);
    }

    map.set(curChar, end);
    // this +1 avoids one-off error.
    // ex: "a"
    // Both end and start will be zero, so according to
    // our logic if we don't do +1, 0 - 0 -> 0
    // This will give us a wrong answer.
    res = Math.max(res, end - start + 1);
    end++;
  }

  return res;
};
```

```js
// Approach 2
// Calculate maxLen only when the existing character is found
const lengthOfLongestSubstring = function (s) {
  if (!s) return 0;

  let start = 0;
  let end = 0;
  let map = new Map();
  let res = 0;

  while (end < s.length) {
    let curChar = s[end];
    if (map.has(curChar) && map.get(curChar) >= start) {
      // Note: here we are first calculating the maxLen,
      // without considering this new 'already seen' character.
      // Basically we are considering(adding) the seen character when
      // calculating the maxLen, and then we increase the start idx.
      res = Math.max(res, end - start);
      start = map.get(curChar) + 1;
    }

    map.set(curChar, end);
    end++;
  }

  return Math.max(res, end - start);
};
```

> There are two approaches:
>
> 1. Where you calculate maxLen every time. Adjust startIndex accordingly.
> 2. Where you calculate maxLen only when the existing character is found.
>
> Check old and new solution to understand both approaches.

> To avoid one-off error when calculating the maxLen, make sure you run the loop till endIdx < s.length. This will make sure when the loop ends, endIdx will be equal to s.length. Then you can substract the startIdx from endIdx to get the length.
>
> Take an example:
>
> s = "abcd"  
> At the beginning: len(s) = 4, startIdx = endIdx = 0  
> When the loop (endIdx < s.length) ends, endIdx = 4  
> Then, endIdx - startIdx = 4 - 0 = 4, which is the correct answer.

> Edge cases:
>
> s = ""  
> s = "a"  
> s = "abba". Here the first 'already seen' character is 'b', and the second 'already seen' character is 'a'. Note that 'a' comes before 'b' at the start of the given string. If you are not cautious when you set the 'startIdx', then you may jump back to the wrong startIdx, which will be idx(a) + 1. This is wrong because you are now again considering the first 'b'(idx = 1) when calculating the maxLen. The wrong answer will be 4 - 1 = 3, which accounts for two 'b's in it.


Longest substring without repeating characters


> You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

```js
const addTwoNumbers = function (l1, l2) {
  const ans = new ListNode(0);
  let cur = ans;
  let carry = 0;

  while (l1 || l2) {
    let first = (l1 && l1.val) || 0;
    let second = (l2 && l2.val) || 0;
    let sum = first + second + carry;

    cur.next = new ListNode(sum % 10);
    carry = Math.floor(sum / 10);

    cur = cur.next;
    l1 = l1 && l1.next;
    l2 = l2 && l2.next;
  }

  if (carry > 0) {
    cur.next = new ListNode(carry);
  }

  return ans.next;
};
```

> Don't forget to consider the carry at the last iteration. You might still have some left over carry that is not appended to the list yet.
>
> Or, you could make the carry as a part of your loop. Until l1, l2 or carry remains, run the loop. This will make sure the "last" carry is handled and added to the list.
