---
# System prepended metadata

title: LandIsland-LeetCode+English Project

---

# LandIsland-LeetCode+English Project

## [Recursion]2021.12.05 21:00  Host: David
### [347. Top K Frequent Elements](https://leetcode.com/problems/powx-n/)(David)

SOL 1:
```js=
var myPow = function(x, n) {
    if (n == 0){
        return 1;
    }
    if (n == 1){
        return x;
    }
    if (n == -1) {
        return 1/x;
    }
    if(n%2 == 0){
        return myPow(x*x, n/2) ;
    }else{
        return x * myPow(x*x, (n-1)/2) ;
    }
};
```
## [HashMap]2021.11.21 21:00  Host: JinWei
### [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements)(Jinwei)

SOL 1: JW
```js=
function topKFrequent(nums, k) {
  let map = new Map();

  nums.forEach((eachNum) => {
    if (map.get(eachNum)) {
      const numAmount = map.get(eachNum);
      map.set(eachNum, numAmount + 1);
    } else {
      map.set(eachNum, 1);
    }
  });

  // sort
  const sortMap = new Map([...map.entries()].sort((a, b) => b[1] - a[1]));
  const finalArr = [];
  sortMap.forEach((val, key) => {
    let idx = 0;
    if (idx < k) {
      finalArr.push(key);
      idx++;
    }
  });
  return finalArr;
}

```

SOL2 : Online
```js=
var topKFrequent = function(nums, k) {
    const count = new Map()
    const bucket = Array.from({ length: nums.length + 1 }, _ => [])
    for (const n of nums) {
        count.set(n, (count.get(n) || 0) + 1)
    }
    for (const entry of count.entries()) {
        const [n, freq] = entry
        bucket[freq].push(n)
    }
    return bucket.flat().slice(-k)
};
```





### [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)(Even Pan)

#### solution 1 (Even)
```python=
class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        self.room = {} # key: seat, value: List[list]
        for idx, menber_group in enumerate(groupSizes):
            self.check_room_seat(menber_group, idx)
        result = []
        for i in self.room.values():
            result.extend(i)
        return result
            
        
    def check_room_seat(self, seat, idx):
        self.room.setdefault(seat, [[]])
        if len(self.room.get(seat)[-1]) < seat:
            self.room[seat][-1].append(idx)
        else:
            self.create_new_room(seat, idx)
    
    def create_new_room(self, seat, idx):
        self.room[seat].append([idx])
```
#### solution 2 source:[ online](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/discuss/448447/Python-Simple.-Hashmap.-With-comments-(beats-99))
```python=

class Solution:
    def groupThePeople(self, groupSizes: List[int]) -> List[List[int]]:
        '''
		Example input-> groupSizes=[3,3,3,3,3,1,3]
        Store in a dictionary[i] the list of indices of input array groupSizes that belong to a group size i 
		'''
        _dict_=collections.defaultdict(list)
        for idx,i in enumerate(groupSizes):
            _dict_[i].append(idx)
        '''
        print (_dict_)-> defaultdict(<class 'list'>, {3: [0, 1, 2, 3, 4, 6], 1: [5]})
        _dict_[i] has list of indices of input array groupSizes that belong to groupsize i
        Next, create lists of size i parsing through _dict_[i], and append them to answer[].
        Further since a solution is guaranteed to exist, len(_dict_[i])/i will always be perfectly divisible. 
		Infact, len(_dict_[i])/i gives exactly the number of groups of size i
        '''
        answer=[]
        for key, lst in _dict_.items():
            for idx in range(0, len(lst), key):
                answer.append(lst[idx:idx + key])
        return (answer)	

```




## [Array]2021.11.14 21:00  Host: Rosy
### [807. Max Increase to Keep City Skyline](https://leetcode.com/problems/max-increase-to-keep-city-skyline/)(Even Pan)
```python=

# slow solution
# time = O(n^2)
# space = O(n)
class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        
        grid_copy = [[0]*len(grid) for _ in range(len(grid[0]))]
        additional_level = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                max_x = max(grid[i])
                max_y = max([i[j] for i in grid])
                # print('x: ', max_x, ';y: ', max_y)
                grid_copy[i][j] = min(max_x, max_y)
                additional_level += grid_copy[i][j] - grid[i][j]
        print(grid_copy)
        print(grid)
        return additional_level

    
# fast solution
# time = O(n)
# space = O(log(n))
class Solution:
    def maxIncreaseKeepingSkyline(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        
        ops = 0
        max1=[]
        max2=[]
        
        
        # print(zip(*grid))
        # print([i for i in zip(*grid)])
        
        for i in grid:
            max1.append(max(i))
            print(max1)
        
        for j in list(zip(*grid)):
            max2.append(max(j))
            print(max2)
            
        for i1, val1 in enumerate(max1):
            for i2, val2 in enumerate(max2):
                ops+=(min(val1, val2)-grid[i1][i2])
            
        return ops
```

## [Hash Table]2021.11.7 21:00  Host: Iris
### [480. Sliding Window Median](https://leetcode.com/problems/sliding-window-median/)(Even Pan)
```python=
class Solution:
    def median(self, nums):
        """ calculate median in a list of sorted numbers
        Argument:
            nums: list, list of numbers which is sorted
        Return:
            return median number if it list have odd length
            else return average of two median numbers
        """
        mid = len(nums) // 2
        if len(nums) % 2:
            return nums[mid]
        return (nums[mid-1] + nums[mid]) / 2
    
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        if not nums:
            return []
        window = sorted(nums[:k-1])
        result = []
        for idx, n in enumerate(nums[(k-1):]):
            self.insert_new_num(window,n)
            result.append(self.median(window))
            self.remove_old_num(window, nums[idx])
        return result
    
    @staticmethod
    def find_insert_loc(li , num):
        """ find the index for num in a sorted list 
        Argument:
            li: list, sorted list to be insert
            num: int, num to be insert
        
        Return:
            lo: int, index for insert in the list
        
        Example:
            case1: [1,2,3,4], 2  -> ([1,2,(2),3,3]) ... 2
            case2: [1,4,5,7,10], 8 -> ([1,4,5,7,8,10]) ... 4

            case3: [1,4,5,7,10], 6 -> ([1,4,5,6,7,10]) ... 3
                psudo 
                mid = 2, << lo= 2+1
                mid = (3+5) =4 num[min] = 10 >> hi = 4
                mid = 3 num[3] = 7 >> hi = 3 , hi == lo break

                case 3 output example:
                    mid:  2 , li[mid]:  5
                    0 5 2 5
                    update lo 0 to 3
                    mid:  4 , li[mid]:  10
                    3 5 4 10
                    update hi 5 to 4
                    mid:  3 , li[mid]:  7
                    3 4 3 7
                    update hi 4 to 3
                    3
        """
        hi = len(li)
        lo = 0
        while lo < hi:
            mid = (lo + hi) // 2
            # print('mid: ', mid, ', li[mid]: ', li[mid])
            if num < li[mid]:
                # print(lo, hi, mid, li[mid])
                # print(f'update hi {hi} to {mid}')
                hi = mid
            else:
                # print(lo, hi, mid, li[mid])
                # print(f'update lo {lo} to {mid + 1}')
                lo = mid + 1
        return lo
    
    def insert_new_num(self, li, num):
        """ insert num in the sorted list
        Arguments:
            li: list, input sorted list
            num: int, input number
            
        Example:
            case1: ([1,2,3,4], 2)  -> [1,2,(2),3,3]
            case2: ([1,4,5,7,10], 8) -> [1,4,5,7,(8),10]
            case3: ([1,4,5,7,10], 6) -> [1,4,5,(6),7,10]
        """
        loc = self.find_insert_loc(li, num)
        li.insert(loc, num)

    def remove_old_num(self, li, num):
        """ remove num in sorted list
        Arguments:
            li: list, input sorted list
            num: int, number to be remove
        Example:
            case1: ([1,2,2,3,3], 2)  -> [1,2,3,3]
            case2: ([1,4,5,7,8,10], 8) -> [1,4,5,7,10]
            case3: ([1,4,5,6,7,10], 6) -> [1,4,5,7,10]
        """
        loc = self.find_insert_loc(li, num) - 1
        del li[loc]
```

### [1817. Finding the Users Active Minutes](https://leetcode.com/problems/finding-the-users-active-minutes/) (Iris)
- Solution1
```javascript=
var findingUsersActiveMinutes = function(logs, k) {
    const m = new Map();
    const result = new Array(k).fill(0)
    logs.forEach((arr)=>{
        const id = arr[0];
        const minute = arr[1];
        if(!m.has(id)){
            m.set(id,[minute])
        }else{
            const prev = m.get(id);
            if(!prev.includes(minute)){
                // arr.includes time complexity = O(n)
                prev.push(minute);
                 m.set(id,prev);
            }
        }
    })
    for(let i of m){
        const len = i[1].length;

        result[len-1]++;
    }
    return result;
};
//Space Complexity = O(n + k)
```

- Solution2
use set and conditional operator to polish
```javascript=
var findingUsersActiveMinutes = function(logs, k) {

    const map = new Map();
    logs.forEach(([id, time]) => { 
       
        const set = map.has(id) ? map.get(id) : new Set();
        set.add(time);
        map.set(id, set);
    })

    const result = new Array(k).fill(0);
    map.forEach((value, key) => {  
        if(value.size <= k) {
            result[value.size - 1] ++;
        }
    })
    return result;
};
```


## [Dynamic Prog.]2021.10.31 9:00  Host: Aaron
### [96. Unique Binary Search Tree](https://leetcode.com/problems/unique-binary-search-trees/submissions/)

G(n) the number of unique BST for a sequence of length n

F(i,n): the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.

G(n)= F(1,n)+F(2,n)+.....F(n,n)
G(3)= F(1,3)+F(2,3)+F(3,3)

G(0)=1, G(1)=1

F(3,7)=G(2)*G(4) [1,2] [4,5,6,7]
F(i,n)=G(i-1)*G(n-i) 1 <= i <= n

G(n)=G(0)*G(n-1)+G(1)*G(n-2)....G(n-1)*G(0)

- Solution 1

Explaination:https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i)
```python=
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        g={}
        for i in range(n+1):
            g[i]=0
        g[0]=1
        g[1]=1
        for i in range(2,(n+1)):
            for j in range(1,(i+1)):
                g[i]+=g[j-1]*g[i-j]
        return g[n]
```
range(1,5) 1 2 3 4

---
### [877. Stone Game](https://leetcode.com/problems/stone-game/) (Tim)
- Solution 1
```cpp=
class Solution{
public:
   bool stoneGame(vector<int>& piles){
      int n = piles.size();
      
      // dparray[i][j] represents # of stones which Alice has
      // more than Bob when playing game from piles i to j.
      int dparray[n][n];

      // initialize dparray with zero
      memset(dparray, 0, sizeof(dparray));
      
      // initialize last step (only 1 pile left)
      for(int i=0; i<n; i++) dparray[i][i] = -piles[i];

      // fill out the dparray
      for(int i=0; i<n; i++){
         for(int j=i+1; j<n; j++){
            if((i+j)%2==0){
               // Alice's turn, try to maximise final result
               dparray[i][j] = max(piles[i]+dparray[i+1][j], 
                                   piles[j]+dparray[i][j-1]);
            } else{
               // Bob's turn, try to minimise final result
               dparray[i][j] = min(piles[i]+dparray[i+1][j], 
                                   piles[j]+dparray[i][j-1]);
            } 
         }
      }
      
      return dparray[0][n-1];
   }
}

```

- Solution 2
```cpp=
class Solution{
public:
   bool stoneGame(vector<int>& piles){
      // since the first one to play the game can always 
      // take all the odd or even piles, he/she can easily
      // sum up and choose the subset with more stones 
      // and win.
      return true;
   }
}
```
---
### [581. Coin Change 2](https://leetcode.com/problems/coin-change-2/) (Jinwei)
---
### [64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) (Rosy)
---
### [119. Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/) (Jing)
---
### [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/) (Aaron)
---
### [338. Counting Bits](https://leetcode.com/problems/counting-bits/) (Iris)
---

## [Array]2021.10.24 12:00 Host:Iris
### [78. Subsets](https://leetcode.com/problems/subsets/solution/)(Iris)
- Solution 1 (cascading)
```javascript=
var subsets = function(nums) {
    let output = [[]]
    
    for (num of nums) {
        output.forEach((el)=>{
            const newArr = [...el, num]
            output.push(el) 
            } 
        )
    }
    return output
};
```
- Solution 2 (Backtracking)recursion
```javascript=
const subsets = function(nums) {
  const output = [];
    
  function backtrack(start, list){

      if(start > nums.length) return;
      output.push([...list])

      for(let idx = start; idx < nums.length; idx++){
          list.push(nums[idx])

          backtrack(idx+1, list)
    
          list.pop()

      }
  } 
   backtrack(0,[]) 
   return output
};
```

## [Array]2021.10.24 21:00 Host:Even
### [68. Text Justification](https://leetcode.com/problems/text-justification/)(Even)
```py
from typing import List


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        print(self.better_spacer(room=3, count_words=3))
        self.maxWidth = maxWidth
        result = []
        new_line = []
        current_loading = 0
        all_length = len(words)
        for i, word in enumerate(words):
            word_length = len(word)
            if current_loading + word_length > maxWidth:
                print('need next line')
                result.append(new_line.copy())
                new_line = []
                current_loading = 0
            new_line.append(word)
            current_loading += word_length + 1
            print('newline = ', new_line, 'current loading: ',current_loading)
                
                
            if i == all_length - 1:
                result.append(new_line.copy())
                result = self.format_result(result)
                return result

    def format_result(self, result: List[List[str]]) -> List[str]:
        last_line = result[-1]
        standard_lines = result[:-1]
        
        formated_lines = []
        
        for line in standard_lines:
            formated_lines.append(self.justify_space(line))
        
        formated_lines.append(self.justify_space(last_line, True))
        return formated_lines
    
    def justify_space(self, line: list, is_last: bool=False) -> str:        
        count_words = len(line)
        room = self.maxWidth - sum(len(word) for word in line)
        if is_last:
            formated_line = " ".join(line) + " " * (room - (count_words - 1))
        else:
            # # use self.better_spacer
            space_list = self.better_spacer(room, count_words)
            formated_line = self.format_spaces(space_list, line, count_words)
            
            # old method 如果空格不能整除，會失效，引入better spacer 跟 format space解決
            # spaces = round(room/(count_words - 1))
            # formated_line = (" "*spaces).join(line)
        return formated_line
    
    @staticmethod
    def better_spacer(room, count_words) -> list:
        # 最後一格只有餘數個空格
        # aaabb  floor(room/count_words) = b , n個a , room%count_words
        if count_words == 1:
            return [room]
        space_list = [floor(room/(count_words - 1))] * (count_words - 1)
        for i in range(room%(count_words - 1)):
            space_list[i] += 1
        return space_list

    @staticmethod
    def format_spaces(space_list, line, count_words):
        formated_line = line[0]
        for i in range(len(space_list)):
            formated_line += " " * space_list[i]
            try:
                formated_line += line[i+1]
            except Exception:
                pass
        return formated_line
```

## [Linked list]2021.10.17 21:00  Host: David
### [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) (David)
- Solution 1
```javascript=
var detectCycle = function(head) {
    let node_pointers = []
    let node = head
    while(1){
        if(node_pointers.indexOf(node) !== -1){
            return node
        }
        if(node == null){
            return null
        }
        node_pointers.push(node)
        node = node.next
    }
}
```
- Solution 2
(https://medium.com/@ChYuan/leetcode-no-142-linked-list-cycle-ii-%E5%BF%83%E5%BE%97-medium-c5b53dcca804)
```javascript=
var detectCycle = function(head) {
    let dummy = new ListNode();
    dummy.next = head;
    let node_slow = dummy;
    let node_fast = dummy;
    while(1){
        if( node_fast == null){
            return null
            
        }
        if( node_fast.next == null){
            return null
            
        }
        node_slow = node_slow.next;
        node_fast = node_fast.next.next;
        if (node_slow == node_fast){
            node_slow = dummy;
            while(1){
                node_slow = node_slow.next
                node_fast = node_fast.next
                if(node_slow == node_fast){
                    return node_slow
                }
            }
        }
    }
};
```

Comment
Jinwei: Super Brilliant! 👍

---
### [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/) (Jinwei)

<a href="shorturl.at/givLV">
Visualization Process</a>


```javascript=
var deleteDuplicates = function(head) {
    let cur = head;

    while (cur && cur.next) {
        let nextNextNode = cur.next.next;
        if (cur.val === cur.next.val) {
            cur.next.next = null;
            cur.next = nextNextNode;
        } else {
            cur = cur.next;
        }
    }
    return head;
};

```
---
### [234. Palindrome Linked List](https://leetcode.com/problems/palindrome-linked-list/) (Aaron)
- Solution 1
```javascript=
var isPalindrome = function(head) {
    
    var sequence = "";
    var reverse = "";

    while(head != null){
        sequence += head.val;
        reverse = head.val + reverse;
        head = head.next;
    }
    return sequence == reverse;
};

// space complexity: O(n)
// time complexity: O(n)
```
- Solution 2
```javascript=
var isPalindrome = function(head) {

    var middle = findMiddle(head); 
    var rNode = reverseNode(middle); 

    while(rNode != null){
        if(head.val != rNode.val) {
            return false;
        }
        head = head.next;
        rNode = rNode.next;
    }
    return true;


    function findMiddle(node){
        var fast = node;
        var slow = node;

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

    function reverseNode(node){
        if(node==null || node.next==null) return node;  
        var prev = null;
        var cur  = node;
        while(cur != null){
            var temp = cur;
            cur = cur.next;   
            temp.next = prev;
            prev = temp;
        }
        return prev;
    }
};

// space complexity: O(1)
// time complexity: O(n)
```

---
## [Array]2021.10.10 21:00  Host: Iris
### [134. Gas Station](https://leetcode.com/problems/gas-station/) (Iris)
- Solution1
```javascript=
var canCompleteCircuit = function(gas, cost) {
    let start = 0, tank = 0, total = 0;
    // best option = a gas station that allows us to arrive the next station
    // find a optimal strat point
    for(let i = 0; i < gas.length; i++) {

        const consume = gas[i] - cost[i];

        tank += consume;
      
        if(tank < 0) {
            tank = 0;
            start = i + 1;
        }
        // tank > 0 = find a start station => start will stay in that index
        // to calculate if we can complete the curcuit
        total += consume;
    }
    return total < 0 ? -1 : start;
};
```

- Solution2
```
var canCompleteCircuit = function(gas, cost) {
    .....
};
```

