###### tags: `grind75`

# Grind 75 Week1

## 1. Two Sum

Harry:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      unordered_map<int, int> seen;
      for(int i = 0; i< nums.size(); i++) {
        int dif = target - nums[i]; 
        if(seen.count(dif)) {
          return {seen[dif], i};
        } else {
          seen[nums[i]] = i;
        }
      }
      return {};
    }
};

var twoSum = function(nums, target) {
    const map = new Map();

    for (let i = 0; i <= nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i)
        }
    }
}

## 2. Valid Parentheses

class Solution {
public:
    bool isValid(string s) {
      if (s.size() == 1) return false;

       unordered_map<char, char> rightToLeft = {
          {')', '('},
          {']', '['},
          {'}', '{'},
       };
       stack<char> lefts;
       for(int i = 0;i<s.size();i++) {
         switch(s[i]) {
           case '(':
           case '[':
           case '{':
            lefts.push(s[i]);
            break;
           case ')':
           case ']':
           case '}':
            if(lefts.empty() || rightToLeft[s[i]] != lefts.top()) {
              return false;
            }
            lefts.pop();
         }
       }

       return lefts.empty();
    }
};

### Stack
Runtime
- 51 ms
- Beats 98.36%
Memory
- 42 MB
- Beats 87.14%

var isValid = function(s) {
    const stack = [];
    const map = {
        '(': ')',
        '[': ']',
        '{': '}',
    }

    for (const char of s) {
        if (map[char]) {
            stack.push(map[char])
        } else if (char !== stack.pop()) {
            return false;
        }
    }

    return !stack.length;
}

### Brute Force
first time: 2022 / 10 / 08
Runtime
- 64 ms
- Beats 69.93%
Memory
- 42.3 MB
- Beats 64.35%

var isValid = function(s) {    
    let arr = [s[0]];

    for (let i = 1; i <= s.length - 1; i++) {
        let prev = arr[arr.length - 1];
        let curr = s[i];
        
        if (curr === ']') {
            if (prev === '[') {
                arr.splice(arr.length - 1);
            } else {
                return false;                
            }
        }

        if (curr === '}') {
            if (prev === '{') {
                arr.splice(arr.length - 1);
            } else {
                return false;                
            }
        }
        
        if (curr === ')') {
            if (prev === '(') {
                arr.splice(arr.length - 1);
            } else {
                return false;
            }
        }

        if (curr === '(' || curr === '{' || curr === '[') {
            arr.push(s[i])            
        }
    }
    
    return arr.length === 0;
};

## 3. Merge Two Sorted Lists

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
      ListNode* head = new ListNode();
      ListNode* node = head;
      while(list1 || list2) {
        if (list1 && list2) {
          int minVal; 
          if (list1->val < list2->val) {
            minVal = list1->val;
            list1 = list1->next;
          } else {
            minVal = list2->val;
            list2 = list2->next;
          }
          node->next = new ListNode(minVal);
          node = node->next;
        } else {
          if(list1) {
            node->next = list1;
          }
          if(list2) {
            node->next = list2;
          }
          break;
        }
      }
      return head->next;
    }
};

var mergeTwoLists = function(list1, list2) {
    const head = new ListNode(null)

    let cur = head;

    while(list1 && list2) {
        if (list1.val < list2.val) {
            cur.next = list1
            list1 = list1.next
        } else {
            cur.next = list2
            list2 = list2.next
        }

        cur = cur.next
    }

    cur.next = list1 || list2

    return head.next;
}

#### Recursion

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

  if(list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}


Harry:

def merge_two_lists(list1, list2)
    return list1 if list2.nil?
    return list2 if list1.nil?
    
    min, max = list1.val > list2.val ? [list2, list1] : [list1, list2]
    ListNode.new(min.val, merge_two_lists(min.next, max))
end

## 4. Best Time to Buy and Sell Stock

Harry:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
      int buyPrice = prices[0];
      int profit = 0;
      for(int i = 1 ; i < prices.size(); i++) {
        if (prices[i] < buyPrice) {
           buyPrice = prices[i];
        } else {
          if (prices[i] - buyPrice > profit) {
            profit = prices[i] - buyPrice;
          }
        }
      }
      return profit;
    }
};

Parker:

var maxProfit = function(prices) {
    let buyPrice = prices[0];
    let profit = 0;

    for (let i = 1; i < prices.length; i++) {
        if (buyPrice > prices[i]) {
            buyPrice = prices[i];
        } else if (prices[i] - buyPrice > profit) {
            profit = prices[i] - buyPrice;
       }
    }
    
    return profit;
};


## 5. Valid Palindrome
### Two Pointer
Parker:

const isPalindrome = function(s) {
  s = s.replace(/[^a-z0-9]/gi, '').toLowerCase();

  let start = 0;

  let end = s.length - 1;

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

  return true;
}

Harry:

class Solution {
public:
    bool isPalindrome(string s) {
      if(s.size() == 1) return true;
      // remove non a-z 0-9
      s.erase(remove_if(s.begin(), s.end(), [](char const &c) {
        return !isalnum(c);
      }), s.end());
      
      int start = 0, end = s.size() - 1;
      while (start < end) {
        char left = 97 <= s[start] && s[start] <= 122 ? s[start] - 32 : s[start]; 
        char right =97 <= s[end] && s[end] <= 122 ? s[end] - 32 : s[end];
        if(left != right) return false;
        start++;
        end--;
      } // abcdefggfedcba
      return true;
    }
};

# 6. Invert Binary Tree

:::success
Harry:
- Time: $O(\#\ \text{of nodes})$
- Space: $O(1)$: O(1)，其餘沒有使用
- 3 ms Beats 60.35% Memory 9.7 MB Beats 86.13%

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        if(!root->left && !root->right) return root;
        if(root->left) root->left = invertTree(root->left);
        if(root->right) root->right = invertTree(root->right);

        TreeNode * temp = root->left;
        root->left = root->right;
        root->right = temp;
        return root;
    }
};

:::

#### Stack
:::info
- TC: O(n)
- SC: O(n)
- Runtime 53 ms Beats 93.68% / Memory 42.5 MB Beats 22.95%

var invertTree = function(root) {
    const stack = [root];

    while (stack.length) {
        // node 代表當前要處理的 node，從 root 開始
        let node = stack.pop();

        if (node) {
            // invert
            [node.left, node.right] = [node.right, node.left];

            // 這邊會把當前的 node 的 left / right Push 進去
            stack.push(node.left, node.right);
        }
    }

    return root;
};

:::

:::info
### Recursion
- TC: O(n)
- SC: O(h)

var invertTree = function(root) {
    if (!root) return null;
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    return root;
};

:::

# 7. Valid Anagram
:::success
## Complexity
- Time: $O(len_s) = O(n)$
- Space: $O(1)$

## Code

**0 ms** Beats **100%**
**7.4 MB** Beats **61.7%**

class Solution {
public:
    bool isAnagram(string s, string t) {
      if(s.size() != t.size()) return false;

      int tally[26]={0};
      for(int i =0 ; i<s.size() ; i++) {
        tally[s[i]-97]+=1;
        tally[t[i]-97]-=1;
      }

      for(int i=0;i<26;i++) {
        if(tally[i] != 0) return false;
      }
      return true;
    }
};

:::

:::info
#### Hash Map
- TC: O(n)
- SC: O(n)

> 可以直接轉成 for loop

var isAnagram = function(s, t) {
    if (s.length !== t.length) return false;

    const map = new Map();

    s.split('').forEach(char => {
        if (map.has(char)) {
            map.set(char, map.get(char) + 1)
        } else {
            map.set(char, 0)
        }
    })

    t.split('').forEach(char => {
        if (!map.has(char)) return false;

        if (map.get(char) === 0) {
            map.delete(char)
        } else {
            map.set(char, map.get(char) - 1)
        }
    })

    return map.size === 0;
};

#### Sort
- TC: O(n log n)
- SC: O(n)

const isAnagram = (s,t) => 
    s.split('').sort().join('')
=== t.split('').sort().join('');

:::

# 8. Binary Search
:::success
### Loop
#### Complexity

- Time: $O(logn)$
- Space: $O(1)$

#### Code

Runtime **46 ms** Beats **24.14%**

Memory **27.6 MB** Beats **69.63%**

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int s =0,e=nums.size()-1;
        while(s <= e) {
          int mid = (s + e )/2;
          if(nums[mid] == target) return mid;
          
          if(target > nums[mid]) s = mid+1;
          else e = mid-1;
        }
        return -1;
    }
};

### Recursive
#### Complexity

- Time: $O(logn)$
- Space: $O(logn)$：每找一次都會建立一個新的 stack frame，只要還沒找到 stack frame 就會一直堆疊 至多 logn 次搜尋

#### Code

Runtime **38 ms** Beats **70.70%**

Memory **27.6 MB** Beats **69.63%**

class Solution {
public:
    int bs(vector<int> & nums, int target, int s, int e) {
      if(s > e) return -1;
      
      int mid = (s+e)/2;
      if(nums[mid] == target) return mid;

      if(nums[mid] < target) return bs(nums, target, mid+1, e);
      else return bs(nums, target, s, mid-1);
    }
    int search(vector<int>& nums, int target) {
      return bs(nums, target, 0, nums.size()-1);
    }
};

:::

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

const search = (nums, target) => {
	let right = nums.length - 1;
	let left = 0;

	while (left <= right) {
		let current = Math.floor((right - left) / 2);

		if (nums[current] === target) {
			return current;
		} else if (nums[current] > target) {
			left = current + 1;
		} else {
			right = current - 1;
		}
	}

	return -1;
}

:::

# 9. Flood Fill

:::success
# BFS
## Complexity

- Time: $O(MN)$
- Space: $O(MN)$

## Code

**7 ms** Beats **87.60%**

**14.5 MB** Beats **13.83%**

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
      if(image[sr][sc] == color) return image;
      int oldColor = image[sr][sc];
      image[sr][sc] = color; // 先標起來，順便當作 visited。
      
      int m = image.size(), n = image[0].size();
      queue<pair<int,int>> q({{sr,sc}});

      // BFS 只看鄰居，先換顏色後再放進去 queue
      while(!q.empty()) {
        auto top = q.front();
        int r = top.first, c = top.second;
        q.pop();
        
        if (0<c && image[r][c-1] == oldColor)  {
          image[r][c-1] = color;
          q.push({r,c-1});
        }
        if (0<r && image[r-1][c] == oldColor) {
          image[r-1][c]  = color;
          q.push({r-1,c});
        }
        if (c<n-1 && image[r][c+1] == oldColor) {
          image[r][c+1] = color;
          q.push({r,c+1});
        }
        if (r<m-1 && image[r+1][c] == oldColor) {
          image[r+1][c] = color;
          q.push({r+1,c});
        }
      }
      return image;
    }
};

# DFS
# Complexity

- Time: $O(MN)$
- Space: $O(MN)$

# Code

**7 ms** Beats **87.60%**

**14.7 MB** Beats **5.35%**

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
      if(image[sr][sc] == color) return image;
      int m=image.size(), n=image[0].size();
      // 先塗
      int oldColor = image[sr][sc];
      image[sr][sc] = color;
      
      // 哪邊欠塗
      if(sc > 0 && image[sr][sc-1] == oldColor) floodFill(image, sr, sc-1, color);
      if(sr > 0 && image[sr-1][sc] == oldColor) floodFill(image, sr-1, sc, color);
      if(sc < n-1 && image[sr][sc+1] == oldColor) floodFill(image, sr, sc+1, color);
      if(sr < m-1 && image[sr+1][sc] == oldColor) floodFill(image, sr+1, sc, color);
      return image;
    }

}; 
/*
  [0,0,0]
  [(0),1,0]
  2
*/

:::

:::info
> 其實就是遍歷所有 目標點 `image[sr][sc]` 周圍的點，透過 dfs 去檢查跟覆寫鄰居
- TC: O(m * n)
- SC: O(m * n)

var floodFill = function(image, sr, sc, color) {
    let oldColor = image[sr][sc];

    if (oldColor !== color) {
        dfs(image, sr, sc, oldColor, color);
    }

    return image;
};

function dfs(image, row, col, oldColor, newColor) {
    if (
        row < 0
        || row >= image.length
        || col < 0
        || col >= image[0].length
        || image[row][col] !== oldColor
    ) return;

    image[row][col] = newColor;

    dfs(image, row + 1, col, oldColor, newColor);
    dfs(image, row - 1, col, oldColor, newColor);
    dfs(image, row, col + 1, oldColor, newColor);
    dfs(image, row, col - 1, oldColor, newColor);
}

:::

# 10. Lowest Common Ancestor of a Binary Search Tree

:::success
## Complexity

- Time: $O(logN)$
- Space: $O(logN)$

## Code

**33 ms** Beats **53.67%**

**23.4 MB** Beats **27.92%**

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);

        return root;
    }
};

:::

:::info
# Brute Force
- TC: O(n)
- SC: O(1)

var lowestCommonAncestor = function(root, p, q) {
	let current = root;

	// break when find until the last node.
	while (current !== null) {
		// move to left
		if (p.val < current.val && q.val < current.val) {
			current = current.left;
		// move to right
		} else if (p.val > current.val && q.val > current.val) {
			current = current.right;
		// the current node is the LCA
		} else {
			return current;
		}
	}

	return null;
};

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

var lowestCommonAncestor = function(root, p, q) {
		// move to right
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }

		// move to left
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }

		// find the LCA
    return root;
};

:::