###### tags: `grind75`, `week3`

# Grind 75 Week 3

# 1. Add Binary
:::success
- Time: $O(\text{max}(L_a, L_b)+1)$
- Space: $O(\text{max}(L_a, L_b)+1)$

| Runtime | 0 ms Beats 100% |
| --- | --- |
| Memory | 6.5 MB Beats 37.32% |

class Solution {
public:
    string addBinary(string a, string b) {
        short carry=0;
        int size_a = a.size(), size_b = b.size();
        stringstream result;
        int ai=size_a-1, bi=size_b-1;
        while(carry || ai >= 0 || bi >= 0) {
          carry += (ai >= 0 ? a[ai] - '0' : 0) + (bi >= 0 ? b[bi] - '0' : 0);
          result << (carry%2);
          carry/=2;
          
          ai--; bi--;
        } 
        string answer = result.str();
        reverse(answer.begin(), answer.end());
        return answer;
    }
};

:::

:::info
# Solution1: BigInt

- TC: O(n)
- SC: O(n)

Explanations

1. Make `a` `b` be treated as binary number

In JavaScript, the prefix **`0b`** is used to represent a binary number literal.

2. Use `BigInt` to sum `a` `b` as normal number

When we pass this string to the **`BigInt()`** function, it will be converted to a **`BigInt`** integer with the value **`10`**.

3. convert the result back to a binary string using the **`toString()`** method with a base of 2.

Why BigInt?

- **BigInt is used to represent Integers greater than 2^53 -1.**
- The binary number may over the `2^53 - 1`(maximum of Number)

var addBinary = function(a, b) {
    const aBin = `0b${a}`;
    const bBin = `0b${b}`;
    const sum = BigInt(aBin) + BigInt(bBin);
    return sum.toString(2);
};

// Example
// a = 11, b = 1
// aBin = 0b11, BigInt(aBin) = 3n
// bBin = 0b1, BigInt(bBin) = 1n
// sum = 4n
// sum.toString(2) = 100

---

# Solution2

- TC: O(n)
- SC: O(1)

Explanation

Why `parseInt(a.charAt(aLen--)`?

- extract the integer value of the current digit in the binary string **`a`** at position **`aLen`**, and decrement **`aLen`**to move to the next digit in the next iteration of the while loop.

var addBinary = function(a, b) {
    let aLen = a.length - 1;
    let bLen = b.length - 1;
    let carry = 0;
    let result = "";

    while (aLen >= 0 || bLen >= 0 || carry > 0) {
        let sum = carry;
        if (aLen >= 0) sum += parseInt(a.charAt(aLen--));
        if (bLen >= 0) sum += parseInt(b.charAt(bLen--));
		// Calculate the binary digit value of the current sum by taking sum modulo 2
		// and prepend it to the result string. ( + result is prepend)
        result = (sum % 2) + result;
        carry = Math.floor(sum / 2);
    }

    return result;
};

:::
# 2. Diameter of Binary Tree
:::success
- Time: $O(N)$
- Space: $O(N)$

| Runtime | 3 ms Beats 98.73% |
| --- | --- |
| Memory | 20.9 MB Beats 8.85% |

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
       if(!root) return 0;
       
       int d=0;
       height(root, d);
       return d;
    }
    int height(TreeNode* root, int &d) {
      if(!root) return 0;
      
      int l = height(root->left, d);
      int r = height(root->right, d);
      d = max({d, l+r});
      return 1 + max({l, r});
    }
};

:::

:::info
# Solution1: BFS
- TC: O(n^2)
- SC: O(n)

var diameterOfBinaryTree = function(root) {
    if (!root) return 0;

    let max = 0;
    let queue = [root];

    while (queue.length) {
        let node = queue.shift();

        let leftDepth = getDepth(node.left);
        let rightDepth = getDepth(node.right);

        max = Math.max(max, leftDepth + rightDepth);

        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }

    return max;
};

// Asscoiated w/ 104. max depth
function getDepth(node) {
    if (!node) return 0;

    return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
}

# Solution2: DFS

- TC: O(n)
- SC: O(n)

var diameterOfBinaryTree = function(root) {
    if (!root) return 0;
    let max = 0;

    function getHeight(node) {
        if (!node) return 0;

        let leftHeight = getHeight(node.left);
        let rightHeight = getHeight(node.right);
        
        max = Math.max(leftHeight + rightHeight, max);

        return Math.max(leftHeight, rightHeight) + 1;
    }

    getHeight(root);

    return max;
};

:::
# 3. Middle of the Linked List
:::success
Time: O(N)
Space: O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(!head->next) return head;

        ListNode * slow= head, * fast=head;
        
        while(fast->next && fast->next->next) {
          slow = slow->next;
          fast = fast->next->next;
        }

        if(fast->next) return slow->next;

        return slow;
    }
};

:::

:::info
# Solution1: Fast & Slow Pointers ( One Pass )
When **`fast`** reaches the end of the linked list, **`slow`** will be at the middle node of the linked list.

1. Start with two pointers **`slow`** and **`fast`** at the head of the linked list.
2. Move **`slow`**one step at a time, and **`fast`** two steps at a time.

- TC: O(n)
- SC: O(1)
- we only need to use two pointers **`slow`**
and **`fast`**.

var middleNode = function(head) {
    let fast = head;
    let slow = head;

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

    return slow;
};

---

# Solution2: Brute Force ( Two Pass )
Get the length of linked-list, then find the middle.

- TC: O(n)
- SC: O(1)

var middleNode = function(head) {
	let count = 0;
	let current = head;

	while (current) {
		count++;
		current = current.next;
	}

	// 中間值有兩個時，直接取下一個，所以無條件進位。
	let middle = Math.floor(count/2);
	current = head;
	for (let i = 0; i < middle; i++) {
		current = current.next;
	}

	return current;
}

:::
# 4. Maximum Depth of Binary Tree
:::success
**4 ms** Beats **93.18%**

**18.7 MB** Beats **93.34%**

- Time: $O(n)$：
- 如果 skewed，一整條走過就會是 n
- Space: $O(n)$：
- 如果 skewed，一整條走過當下 stack 最多有 n 個 dfs

# Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* root, int depth) {
      if(!root) {
        return depth;
      }
      int left=depth, right=depth;
      if(root->left) {
        left = dfs(root->left, depth+1);
      }
      
      if(root->right) {
        right = dfs(root->right, depth+1);
      }
      return max(left, right);
    }
    int maxDepth(TreeNode* root) {
      if(!root) return 0;
      
      return dfs(root, 1);
    }
};

:::

:::info
# Solution1: DFS

- TC: O(n)
- SC: O(n)

var maxDepth = function(root) {
    if (!root) return 0;
    
    return getHeight(root);
};

function getHeight(node) {
    if (!node) return 0;

    let leftHeight = getHeight(node.left);
    let rightHeight = getHeight(node.right);

    return Math.max(leftHeight, rightHeight) + 1;
}

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

---

# Solution2: BFS

- TC: O(n)
- SC: O(n)

var maxDepth = function(root) {
    if (!root) return 0;

    let levels = 0, queue = [root];

    while (queue.length) {
				// 沒有鎖定的 levelSize，直接在 for loop 中使用 queue.length 的話會變成在計算每層 node 的數量
  			let levelSize = queue.length;

        // BFS 的方式 iterate 每個 node
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();

            // 進入下一層，沒得 push 時，代表該 node 的 左 or 右 是空的
            if (node.right) queue.push(node.right);
            if (node.left) queue.push(node.left); 
        }

        levels++;
    }

    return levels;
};

:::
# 5. Contains Duplicate
:::success
T: O(N)
S: O(N)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, bool> seen;
       for(auto &e : nums) {
         if(seen.count(e)) return true;

         seen[e] = true;
       }
       return false;
    }
};

:::

:::info
# Solution1: Hash Table

- TC: O(n)
- SC: O(n)

var containsDuplicate = function(nums) {
    const map = new Map();

    for (const num of nums) {
        if (map.has(num)) return true;

        map.set(num , 1);
    }

    return false;
};

:::