---
# System prepended metadata

title: LC Daily

---

[TOC]

# Solutions

## [779. K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar)
#### 10/25/2023
Pawan 
```python

```
Victor
```c++
class Solution {
public:
    int kthGrammar(int n, int k) {
        k--;
        int flip = 0;
        while (n > 1) {
            flip ^= k & 1;
            k >>= 1;
            n--;
        }
        // n == 1
        return flip;
    }
};
```
Shang-Yi 
```python
```
Aishwarya 
```python
```

## [515. Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row)
#### 10/24/2023
Pawan 
```python

```
Victor

It would have been more efficient to remember the levels using the number of elements, but I think this two-queue idea is pretty clean.
```c++
/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> queueA, queueB;
        queue<TreeNode*>* currentRow = &queueA;
        queue<TreeNode*>* nextRow = &queueB;
        vector<int> result;

        if (root == nullptr) {
            return result;
        }

        currentRow->push(root);
        while (true) {
            int currentRowMax = currentRow->front()->val;
            while (!currentRow->empty()) {
                TreeNode *node = currentRow->front();
                currentRow->pop();
                currentRowMax = max(currentRowMax, node->val);
                if (node->left) nextRow->push(node->left);
                if (node->right) nextRow->push(node->right);
            }
            result.push_back(currentRowMax);

            if (nextRow->empty()) {
                return result;
            }
            swap(currentRow, nextRow);
        }
    }
};
```
Shang-Yi 
```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        # BFS
        # keep max for each level

        ans = {}
        q = deque([(root, 0)])
        while q:
            node, level = q.popleft()
            if not node:
                continue
            if level not in ans:
                ans[level] = node.val
            ans[level] = max(ans[level], node.val)
            q.append((node.left, level + 1))
            q.append((node.right, level + 1))
    
        return [v for _, v in ans.items()]
```
Aishwarya 
```python
```

## [342. Power of Four](https://leetcode.com/problems/power-of-four)
#### 10/23/2023
Pawan 
```python

```
Victor
```c++
#include <bit>

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        unsigned int m = n;
        return std::popcount(m) == 1 && (std::countr_zero(m) & 1) == 0;
    }
};
```
Shang-Yi 
```python
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
            
        while n % 4 == 0:
            n /= 4

        return n == 1
```
Aishwarya 
```python
```

## [341. Flatten Nested List Iterator](https://leetcode.com/problems/flatten-nested-list-iterator)
#### 10/20/2023
Pawan 
```python

```
Victor

Bottom 10% in terms of runtime and memory :(
```python
class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.queue = deque(nestedList)
        self._ready_next()
    
    def next(self) -> int:
        result = self.queue.popleft()
        self._ready_next()
        return result
    
    def hasNext(self) -> bool:
         return bool(self.queue)

    def _ready_next(self):
        while self.queue and not self.queue[0].isInteger():
            self.queue.extendleft(reversed(self.queue.popleft().getList()))
```
Shang-Yi 
```python
```
Aishwarya 
```python
```

## [Parallel Courses III](https://leetcode.com/problems/parallel-courses-iii/description/?envType=daily-question&envId=2023-10-18)
#### 10/18/2023

Pawan 
```python=
from heapq import * 

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        
        adj = {i : set() for i in range(n)}
        prev = {i : set() for i in range(n)}

        for a, b in relations: 
            adj[a-1].add(b-1)
            prev[b-1].add(a-1)
        
        heap = [] 
        
        for key, value in prev.items():
            if len(value) == 0:
                heappush(heap, (time[key], key))

        res = 0 
        while heap: 
            finishTime, course = heappop(heap)
            res = finishTime 
            for nx in adj[course]:
                prev[nx].remove(course)
                if len(prev[nx]) == 0:
                    heappush(heap, (time[nx] + res, nx))
        
        return res 
```
Victor
```python
```
Shang-Yi 
```python
class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        in_degree = [0] * (n + 1)
        graph = [[] for _ in range(n + 1)]

        for prev_course, next_course in relations:
            in_degree[next_course] += 1
            graph[prev_course].append(next_course)
        
        q = []
        months_needs_per_course = [0] * (n + 1)

        for course in range(1, n + 1):
            if in_degree[course] == 0:
                q.append(course)
                months_needs_per_course[course] = time[course - 1]
        
        plan = []

        while q:
            course = q.pop(0)
            plan.append(course)
            for next_course in graph[course]:
                months_needs_per_course[next_course] = max( \
                    months_needs_per_course[next_course], \
                    months_needs_per_course[course] + time[next_course - 1])

                in_degree[next_course] -= 1
                if in_degree[next_course] == 0:
                    q.append(next_course)
    
        if len(plan) == n:
            return max(months_needs_per_course)
        
        return -1
```
Aishwarya 
```python
```


## [1269. Number of Ways to Stay in the Same Place After Some Steps](https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/description/?envType=daily-question&envId=2023-10-15)
#### 10/14/2023 
Pawan 
```python
```
Victor
```python
```
Shang-Yi 
```python
class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def solve(i, remaining):
            nonlocal steps, arrLen
            if remaining == 0:
                if i == 0:
                    return 1
                return 0
            
            stay = solve(i, remaining - 1)
            move_left = (solve(i - 1, remaining - 1) % MOD) if i > 0 else 0
            move_right = (solve(i + 1, remaining - 1) % MOD) if i < arrLen - 1 else 0

            return (stay + move_left + move_right) % MOD
        
        return solve(0, steps)
```
Aishwarya 
```python
```

## [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=daily-question&envId=2023-10-13)
#### 10/12/2023 
Pawan 
```python
```
Victor
```python
```
Shang-Yi 
```python
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        
        @cache
        def solve(i):
            nonlocal cost, n

            if i >= n:
                return 0

            one_step = cost[i] + solve(i + 1)
            two_step = cost[i] + solve(i + 2)
            return min(one_step, two_step) 
        
        return min(solve(0), solve(1))

```
Aishwarya 
```python
```

## [1095. Find in Mountain Array](https://leetcode.com/problems/find-in-mountain-array)
#### 10/11/2023
Pawan 
```python

```
Victor
```python
from operator import lt, gt

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        M = Solution.findMaxIndex(mountain_arr)
        i = Solution.indexOfInSortedArr(target, mountain_arr, 0, M, lt)
        if i == -1:
            i = Solution.indexOfInSortedArr(target, mountain_arr, M, mountain_arr.length()-1, gt)
        return i

    def findMaxIndex(mountain_arr: 'MountainArray'):
        L = 0
        L_val = mountain_arr.get(L)
        R = mountain_arr.length()-1
        R_val = mountain_arr.get(R)
        C = R // 2
        C_val = mountain_arr.get(C)
        while True:
            if C - L == 1:
                if R - C == 1:
                    return C
                O = C - 1
                O_val = mountain_arr.get(O)
                return O if O_val > C_val else C
            elif R - C == 1:
                O = C + 1
                O_val = mountain_arr.get(O)
                return O if O_val > C_val else C

            L1 = (L + C) // 2
            L1_val = mountain_arr.get(L1)
            R1 = (C + R) // 2
            R1_val = mountain_arr.get(R1)

            if L1_val < C_val <= R1_val:
                L, L_val = C, C_val
                C, C_val = R1, R1_val
            elif L1_val < C_val > R1_val:
                L, L_val = L1, L1_val
                R, R_val = R1, R1_val
            elif L1_val >= C_val > R1_val:
                R, R_val = C, C_val
                C, C_val = L1, L1_val
            else:
                raise Exception("Unexpected order of vals", L1, C, R1)

    def indexOfInSortedArr(target, mountain_arr, L, R, sort_order):
        L_val = mountain_arr.get(L)
        if L_val == target:
            return L
        R_val = mountain_arr.get(R)
        if R_val == target:
            return R
        while R - L > 1:
            C = (L + R) // 2
            C_val = mountain_arr.get(C)
            if sort_order(C_val, target):
                L = C
            elif sort_order(target, C_val):
                R = C
            else:
                return C
            
        return -1
```
Shang-Yi 
```python
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        # 1. find peak
        # 2. find left and right, since it's mountain array, 
        #    at most two target, one on left, and one on right
    
        # find peak
        n = mountain_arr.length()
        peak_idx = -1
        start, end = 0, n - 1
        while start <= end:
            mid = (start + end) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                start = peak_idx = mid + 1
            else:
                end = mid - 1
        
        # invalid mtn arr
        if peak_idx == -1:
            return -1
        
        # find left
        start, end = 0, peak_idx
        while start <= end:
            mid = (start + end) // 2
            mid_val = mountain_arr.get(mid)
            if mid_val == target:
                return mid
            if mid_val < target:
                start = mid + 1
            else:
                end = mid - 1
        
        # find right
        start, end = peak_idx, n - 1
        while start <= end:
            mid = (start + end) // 2
            mid_val = mountain_arr.get(mid)
            if mid_val == target:
                return mid
            if mid_val > target:
                start = mid + 1
            else:
                end = mid - 1
          
        
        return -1
```
Aishwarya 
```python
```

## [2009. Minimum Number of Operations to Make Array Continuous](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/description/?envType=daily-question&envId=2023-10-10)
#### 10/09/2023 
Pawan 
```python
```
Victor
```python
```
Shang-Yi 
```python
# I follow Editorial
```
Aishwarya 
```python
```

## [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/1070538710/?envType=daily-question&envId=2023-10-09)
#### 10/08/2023 
Pawan 
```python=
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        def binarySearchFirst():
            l = 0 
            h = len(nums)-1
            found = False 

            while l <= h:
                m = (l + h)//2 
                if target == nums[m]:
                    h = m-1 
                    found = True 
                elif target < nums[m]:
                    h = m-1
                else: 
                    l = m+1        
            return l if found else -1 
    
        def binarySearchLast():
            l = 0 
            h = len(nums)-1
            found = False 

            while l <= h:
                m = (l + h)//2 
                if target == nums[m]:
                    l = m+1 
                    found = True 
                elif target < nums[m]:
                    h = m-1
                else: 
                    l = m+1        
            return h if found else -1

        return [binarySearchFirst(), binarySearchLast()]
```
Victor
```python
```
Shang-Yi 
```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = -1
        start, end = 0, len(nums) - 1

        while start <= end:
            mid = (start + end) // 2
            if target == nums[mid]:
                end = mid - 1
                first = mid
            elif nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1

        snd = -1
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if target == nums[mid]:
                start = mid + 1
                snd = mid
            elif nums[mid] > target:
                end = mid - 1
            else:
                start = mid + 1

        return [first, snd]
```
Aishwarya 
```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l, r = 0, len(nums) - 1
        ans = []
        while l<=r:
            mid = (l+r)//2
            if nums[mid] == target and (mid-1 < 0 or nums[mid-1]<target):
                ans.append(mid)
                break
            elif nums[mid]<target:
                l = mid+1
            else:
                r = mid-1
        
        l, r = 0, len(nums)-1
        while l<=r:
            mid = (l+r)//2
            if nums[mid] == target and ((mid+1)>=len(nums) or nums[mid+1]>target):
                ans.append(mid)
                break
            elif nums[mid]>target:
                r = mid - 1
            else:
                l = mid + 1
        
        return ans if ans else [-1, -1]
```

## [1458. Max Dot Product of Two Subsequences](https://leetcode.com/problems/max-dot-product-of-two-subsequences/description/?envType=daily-question&envId=2023-10-08)
#### 10/07/2023 
Pawan 
```python=
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        
        n1 = len(nums1)
        n2 = len(nums2)

        # n1 x n2 matrix 
        dp = [[float("-inf")] * (n2+1) for _ in range(n1+1)]
        
        for i in range(n1-1, -1, -1):
            for j in range(n2-1, -1, -1):
                dp[i][j] = max(
                    dp[i+1][j],
                    dp[i][j+1], 
                    nums1[i] * nums2[j],
                    nums1[i] * nums2[j] + dp[i+1][j+1]
                )
        
        return dp[0][0]
```
Victor
```python
```
Shang-Yi 
```python
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        @cache
        def solve(i, j):
            if i == m or j == n:
                return 0
            
            pick = nums1[i] * nums2[j] + solve(i + 1, j + 1)
            skip_one = solve(i + 1, j)
            skip_two = solve(i, j + 1)

            return max(pick, skip_one, skip_two)
        
        # generate min negative
        if max(nums1) < 0 and min(nums2) > 0:
            return max(nums1) * min(nums2)
        
        if max(nums2) < 0 and min(nums1) > 0:
            return max(nums2) * min(nums1)
        
        return solve(0, 0)
```
Aishwarya 
```python
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

        dp = [[float('-inf') for x in range(len(nums2)+1)] for y in range(len(nums1)+1)]

        res = float('-inf')

        for i in range(len(nums1)-1, -1, -1):
            for j in range(len(nums2)-1, -1, -1):
                dp[i][j] = max(nums1[i]*nums2[j], nums1[i]*nums2[j] + dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
                res = max(res, dp[i][j])
                #print(dp)
        
        return res
```

## [1420. Build Array Where You Can Find The Maximum Exactly K Comparisons](https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/)
#### 10/06/2023 
Pawan 
```python

```
Victor
```python
```
Shang-Yi 
```python
# credit: Editorial for state transfering

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        @cache
        def solve(i, cur_max, remaining_k):
            nonlocal n, m, MOD
            if i == n:
                if remaining_k == 0:
                    return 1
                return 0
            
            pick_less_or_equal_than_cur_max = (cur_max * solve(i + 1, cur_max, remaining_k)) % MOD

            pick_greater_than_cur_max = 0
            for new_max in range(cur_max + 1, m + 1):
                pick_greater_than_cur_max += solve(i + 1, new_max, remaining_k - 1)
                pick_greater_than_cur_max %= MOD
            
            return pick_less_or_equal_than_cur_max + pick_greater_than_cur_max
        
        return solve(0, 0, k)
```
Aishwarya 
```python
```


## [343. Integer Break](https://leetcode.com/problems/integer-break/description/)
#### 10/04/2023
Pawan 
The hints helped. 

```python=
class Solution:
    def integerBreak(self, n: int) -> int:
        n_3 = n // 3 
        rem = n % 3

        if n == 3:
            return 2

        if n_3 == 0:
            return 1 
        
        if rem == 1:
            return 3 ** (n_3-1) * 4 
        
        if rem == 2:
            return 3 ** (n_3) * 2

        return 3 ** (n_3)
```
Victor
```python
```
Shang-Yi 
```python
# credit: Editorial for base case developing

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1

        @cache
        def solve(num):
            # if num less or equal than 3, split will be smaller
            if num <= 3: 
                return num
            
            ans = num
            for i in range(2, num):
                ans = max(ans, i * solve(num - i))
            
            return ans
        
        return solve(n)

```
Aishwarya 
```python
class Solution:
    def integerBreak(self, n: int) -> int:
        if n<=3:
            return n-1

        prod = 1
        while n>4:
            prod *= 3
            n -=3
        
        if n:
            prod *= n
        
        return prod 
```



## [229. Majority Element II](https://leetcode.com/problems/majority-element-ii/description/?envType=daily-question&envId=2023-10-05)
#### 10/04/2023 
Pawan 
The main question is easy, the interesting part is the follow up. Couldnt figure it out. Turns out it uses something called "Moore's Voting Algorithm" which is based on the Pigon-Hole Principle, I recommend you watch it: 

https://www.youtube.com/watch?v=n5QY3x_GNDg 

After watching that, these two analogies helped me understand it clearly:

https://leetcode.com/problems/majority-element-ii/description/comments/1868197 

https://leetcode.com/problems/majority-element-ii/description/comments/2085167 


```python
from heapq import * 

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
                

        majEle1 = None 
        majEle2 = None 
        majEle1Count = 0
        majEle2Count = 0 

        for n in nums: 
            if n == majEle1:
                majEle1Count += 1 
            elif n == majEle2: 
                majEle2Count += 1
            elif majEle1Count == 0: 
                majEle1 = n 
                majEle1Count = 1 
            elif majEle2Count == 0: 
                majEle2 = n 
                majEle2Count = 1 
            else: 
                majEle1Count -= 1 
                majEle2Count -= 1 

        
        Ele1Count = 0
        Ele2Count = 0 
        for n in nums: 
            if n == majEle1: 
                Ele1Count += 1 
            elif n == majEle2:
                Ele2Count += 1 
        
        res = [] 
        if Ele1Count > len(nums) //3:
            res.append(majEle1)
        
        if Ele2Count > len(nums) //3:
            res.append(majEle2)
        
        return res
```
Victor
```python
```
Shang-Yi 
```python
from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        target = len(nums) // 3
        ctr = Counter(nums)
        return [num for num in ctr if ctr[num] > target]
```
Aishwarya 
```python
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        hmap, res = {}, []
        for num in nums:
            count = hmap.get(num, 0)
            count += 1
            hmap[num] = count

        for key in hmap:
            if hmap[key]>len(nums)//3:
                res.append(key)
        
        return res
```


## [706. Design HashMap](https://leetcode.com/problems/design-hashmap/)
#### 10/03/2023
Pawan 
```python=
# cheesed solution 
class MyHashMap:

    def __init__(self):
        self.values = [-1] * (10**6 + 1)

    def put(self, key: int, value: int) -> None:
        self.values[key] = value 

    def get(self, key: int) -> int:
        return self.values[key]

    def remove(self, key: int) -> None:
        self.values[key] = -1

```
Victor
```c++
class MyHashMap {
public:
    MyHashMap() {
        hashTableLen_ = 8;
        hashTable_ = new LLNode*[hashTableLen_]{};
        numElements_ = 0;
    }

    ~MyHashMap() {
        delete[] hashTable_;
    }

    // should also have copy constructor, copy assignment operator, move constructor, and move assignment operator
    // but I won't waste time on those for this leetcode.
    
    void put(int key, int value) {
        LLNode **node = find(key);
        if (*node) {
            (**node).value = value;
        } else {
            *node = new LLNode{
                .next = NULL,
                .key = key,
                .value = value,
            };
            numElements_++;
        }
        if (numElements_ > (hashTableLen_ << 1)) {
            reallocate();
        }
    }
    
    int get(int key) {
        LLNode **node = find(key);
        if (*node == NULL) {
            return kNoData;
        }
        return (**node).value;
    }
    
    void remove(int key) {
        LLNode **nodePtr = find(key);
        LLNode *node = *nodePtr;
        if (node == NULL) {
            return;
        }
        *nodePtr = node->next;
        delete node;
        numElements_--;
    }
private:
    const static int kNoData = -1; // ok according to the constraints of the data
    struct LLNode {
        LLNode *next;
        int key;
        int value;
    };
    LLNode **hashTable_;
    size_t hashTableLen_;
    size_t numElements_;

    LLNode **find(int key) {
        int hash = key & (hashTableLen_ - 1);
        LLNode **it = hashTable_ + hash;
        while (*it != NULL) {
            if ((**it).key == key) {
                break;
            }
            it = &((**it).next);
        }
        return it;
    }

    void reallocate() {
        size_t originalLen = hashTableLen_;
        hashTableLen_ <<= 1;
        LLNode **newHashTable = new LLNode*[hashTableLen_]{};
        for (int i = 0; i < originalLen; i++) {
            LLNode *node;
            while (node = hashTable_[i]) {
                int hash = node->key & (hashTableLen_ - 1);
                newHashTable[hash] = new LLNode{
                    .next = newHashTable[hash],
                    .key = node->key,
                    .value = node->value,
                };
                hashTable_[i] = node->next;
                delete node;
            }
        }
        delete[] hashTable_;
        hashTable_ = newHashTable;
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */
```
Shang-Yi 
```python
class MyHashMap:

    def __init__(self):
        self.data = [None] * (10 ** 6 + 1)

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key] if self.data[key] != None else -1

    def remove(self, key: int) -> None:
        self.data[key] = None
        


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)
```
Aishwarya 
```python
class MyHashMap:

    def __init__(self):
        self.hmap = [-1] * (10**6 + 1)
        

    def put(self, key: int, value: int) -> None:
        self.hmap[key] = value
        

    def get(self, key: int) -> int:
        return self.hmap[key]

    def remove(self, key: int) -> None:
        self.hmap[key] = -1
```

## [1512. Number of Good Pairs](https://leetcode.com/problems/number-of-good-pairs/description/?envType=daily-question&envId=2023-10-03)
#### 10/02/2023
Pawan 
```python
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        return sum([nums[i] == nums[j] for i in range(len(nums)) for j in range(i+1, len(nums))])
```
Victor
```python
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        count_before = [0]*101
        for n in nums:
            ans += count_before[n]
            count_before[n] += 1
        return ans
```
```c++
#define lambda(p,e) ([&]p{return (e);})
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        return accumulate(nums.begin(),nums.end(),0,lambda((auto c),lambda((auto a,auto n),a+c[n]++))(vector<int>(101)));
    }
};
```
Shang-Yi 
```python
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        d = {}
        ctr = 0
        for num in reversed(nums):
            if num not in d:
                d[num] = 1
            else:
                ctr += d[num]
                d[num] += 1
        return ctr
```
Aishwarya 
```python
class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        hmap = collections.defaultdict(int)

        for num in nums:
            hmap[num] += 1
        
        res = 0
        for key in hmap:
            if hmap[key]>1:
                res += (hmap[key]*(hmap[key]-1))//2
        
        return res
```


## [2038. Remove Colored Pieces if Both Neighbors are the Same Color](https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/)
#### 10/01/2023
Pawan 
```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        n = len(colors)
        aliceTurns = sum([colors[i:i+3] == "AAA" for i in range(0,n-2)]) 
        bobTurns = sum([colors[i:i+3] == "BBB" for i in range(0,n-2)])  
        return aliceTurns > bobTurns 

```
Victor
```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        a_moves = Solution.getNumOverlappingOccurrences('AAA', colors)
        b_moves = Solution.getNumOverlappingOccurrences('BBB', colors)
        return a_moves > b_moves

    def getNumOverlappingOccurrences(needle, haystack):
        i = -1
        result = 0
        while True:
            i = haystack.find(needle, i+1)
            if i < 0:
                return result
            result += 1

# A=0, B=0+ -> False
# A=1+, B=0 -> True
# A=1, B=1+ -> False
# A=2+, B=1 -> True
```
> @Shang-Yi, I would have implemented your solution in the following way.
> I find the `[i:i+3]` easier to read, and the `range(len(colors - 3))` easier to read.
> Also, doing the string slicing once instead of twice will improve runtime in this tight inner loop by about 33% https://gist.github.com/vszabo2/54255b8e16dde833a1afcfc22ebac161.
> [name=Victor][time=Sun, Oct 1, 2023 10:56 PM]
> > Thank you! I'll do `colors[i] == colors[i + 1] == colors[i + 2] == "A"`` then :D
> > [name=Shang-Yi]
```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        a = 0
        b = 0
        for i in range(len(colors) - 3):
            c = colors[i:i+3]
            if c == "AAA":
                a += 1
            elif c == "BBB":
                b += 1
        return a > b
```

Shang-Yi 
```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        # like hint 1 said, there is no moving dependency between Alice and Bob
        # because the removal criteria should be both its neightors are the same
        # so simply count the steps of Alice and Bob then compare
        a = 0
        b = 0

        for i in range(1, len(colors) - 1):
            if colors[i-1:i+2] == "AAA":
                a += 1
            if colors[i-1:i+2] == "BBB":
                b += 1
        return a > b


```
Aishwarya 
```python
class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        ac, bc = 0, 0
        for i in range(1,len(colors)-1):
            if colors[i]=='A' and colors[i-1]=='A' and colors[i+1]=='A':
                ac +=1
            if colors[i]=='B' and colors[i+1]=='B' and colors[i-1]=='B':
                bc +=1
        if ac>bc:
            return True
        else:
            return False
```


## [557. Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/description/?envType=daily-question&envId=2023-10-01)
#### 09/30/2023
Pawan 
```python
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([x[::-1] for x in s.split()])
```
Victor
```python
import re
class Solution:
    def reverseWords(self, s: str) -> str:
        return re.sub('[^\\s]+',(lambda m:m.group()[::-1]),s)
```
```c++
class Solution {
public:
    string reverseWords(string s) {
        vector<char> result(s.size());
        auto out_it = result.begin();
        auto word_start = s.end();
        for (auto it = s.begin(); it != s.end(); ++it) {
            if (*it == ' ') {
                if (word_start != s.end()) {
                    for (auto jt = it-1; jt >= word_start; jt--) {
                        *(out_it++) = *jt;
                    }
                    word_start = s.end();
                }
                *(out_it++) = *it;
            } else if (word_start == s.end()) {
                    word_start = it;
            }
        }
        if (word_start != s.end()) {
            for (auto jt = s.end()-1; jt >= word_start; jt--) {
                *(out_it++) = *jt;
            }
        }
        assert(out_it == result.end());
        return string(result.begin(), result.end());
    }
};
```
Shang-Yi 
```python
class Solution:
    def reverseWords(self, s: str) -> str:
        word_list = s.split()
        acc = []
        for word in word_list:
            acc.append(word[::-1])
        return " ".join(acc)
```
Aishwarya 
```python
class Solution:
    def reverseWords(self, s: str) -> str:
        res = ""
        stack = []
        for ch in s:
            if ch!=" ":
                stack.append(ch)
            else:
                while stack:
                    res += stack.pop()
                res += " "
        while stack:
            res += stack.pop()
        return res
```

## [132 Pattern](https://leetcode.com/problems/132-pattern/description/?envType=daily-question&envId=2023-09-30)
09/29/2023
Pawan 
```python=
# Brute Force, TLE after 89/103 
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:

        def findSecond(first, i):
            if i >= len(nums): 
                return False 
            if nums[i] > first and findThird(first, nums[i], i+1):
                return True 
            return findSecond(first, i+1)
        
        def findThird(first, second, i):
            if i >= len(nums):
                return False 
            if nums[i] > first and nums[i] < second: 
                return True 
            return findThird(first, second, i+1)
        
        for i in range(len(nums)):
            if findSecond(nums[i], i+1):
                return True 
        
        return False 
    
    
# my solution 1 year ago that I forgot, passes all 
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        
        stack = []
        curMin = nums[0]

        for n in nums[1:]:
            while stack and stack[-1][0] <= n:
                stack.pop()
            
            if stack and n > stack[-1][1]:
                return True 
            
            stack.append((n, curMin))
            curMin = min(curMin, n)
        
        return False 


```
Victor
```python
# I followed the editorial
```
Shang-Yi 
```python
# give up :P
```
Aishwarya 
```python
class Solution:
    def find132pattern(self, nums: List[int]) -> bool:

       stack, j = [], float('-inf')

       for i in range(len(nums)-1, -1, -1):
           if nums[i]<j:
               return True
           while stack and stack[-1]<nums[i]:
                j = stack.pop()
           stack.append(nums[i])
            
       return False
```


## [896. Monotonic Array](https://leetcode.com/problems/monotonic-array/description/?envType=daily-question&envId=2023-09-29)
09/28/2023

Pawan 
```python
class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        if len(nums) <= 1 :
            return True 
        
        pattern = '' 
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                continue 
            if nums[i] > nums[i-1]:
                if pattern == "desc":
                    return False 
                pattern = "asc"
            if nums[i] < nums[i-1]:
                if pattern == 'asc':
                    return False 
                pattern = 'desc'
        return True 
```
Victor
```python
class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        d=[i-j for i,j in zip(nums,nums[1:])]
        return not d or 0<=min(d)or 0>=max(d)
```
Shang-Yi 
```python
class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        def is_inc(nums):
            for i in range(1, len(nums)):
                if nums[i - 1] > nums[i]:
                    return False
            return True
        
        def is_dec(nums):
            for i in range(1, len(nums)):
                if nums[i - 1] < nums[i]:
                    return False
            return True
        
        return is_inc(nums) or is_dec(nums)
```
Aishwarya 
```python
class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        i, j =0, 1
        if len(nums)>1:
            while i<len(nums) and j<len(nums) and nums[i] == nums[j]:
                i +=1
                j +=1
        if len(nums)>1 and j<len(nums) and nums[i]<nums[j]:
            i=2
            while i<len(nums):
                if nums[i]<nums[i-1]:
                    return False
                i +=1
        elif len(nums)>1 and j<len(nums) and nums[i]>=nums[j]:
            i = 2
            while i<len(nums):
                if nums[i]>nums[i-1]:
                    return False
                i +=1
        return True
```


## [905. Sort Array By Parity](https://leetcode.com/problems/sort-array-by-parity/description/?envType=daily-question&envId=2023-09-28)
09/27/2023 
Pawan 
```python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        
        j = 0 
        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1 
        return nums 

```
Victor
```python
# SY: mind blowing lol
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        b,c=[],[]
        for i in nums:
            [b,c][i&1].append(i)
        return b+c
```
Victor recommends you read Two-pointer solution as well: https://leetcode.com/problems/sort-array-by-parity/solutions/4098143/96-32-two-pointer-one-line/?envType=daily-question&envId=2023-09-28 SY: This two ptrs is really good! <3
Shang-Yi 
```python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        ans = []

        for num in nums:
            if num % 2 == 0:
                ans.append(num)
        
        for num in nums:
            if num % 2 != 0:
                ans.append(num)
        
        return ans
```
Aishwarya 
```python
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        res = [-1]*len(nums)
        i, j = 0, len(nums)-1

        for num in nums:
            if num%2==0:
                res[i] = num
                i +=1
            else:
                res[j] = num
                j -=1
        
        return res
```


## [880. Decoded String at Index](https://leetcode.com/problems/decoded-string-at-index/description/?envType=daily-question&envId=2023-09-27)
09/26/2023 
Pawan 
My idea, to loop back and forth within the string, but I think I entered an impossibe situation that I tried to debug for too long 
```python=
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        
        p = 0 
        i = 0 

        s = list(s)
        while True: 
            while s[i] == '1':
                i += 1
            if p == k-1:
                return s[i]
            if s[i].isdigit():
                s[i] = str(int(s[i])-1)
                i = 0
            else:    
                i += 1 
                p += 1
        
```
Victor
```python
# SY: This is great!
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        """tape structure of s="leet2code3a"
        C(C(C(None, 0, "leet", l=4), 2, "code", l=12), 3, "a", l=37)
        or flat:
        lengths = [4, 12, 37]
        words = ["leet", "code", "a"]
        """
        lengths = [0]
        words = [[]]
        for c in s:
            if "0" <= c <= "9":
                lengths.append(lengths[-1] * int(c))
                words.append([])
            else:
                words[-1].append(c)
                lengths[-1] += 1
        k -= 1
        while True:
            if k >= lengths[-1] - len(words[-1]):
                # not repeated
                return words[-1][k - (lengths[-1] - len(words[-1]))]
            else:
                # repeated
                lengths.pop()
                words.pop()
                k %= lengths[-1]

```
Shang-Yi 
```python
# credit: Editorial

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        acc_len = 0

        for char in s:
            if char.isdigit():
                acc_len *= int(char)
            else:
                acc_len += 1
        
        # if actually build up acc str will result in MLE.
        # therefore traverse backwards to reduce k by acc len 
        for char in reversed(s):
            k %= acc_len
            if k == 0 and char.isalpha():
                return char
            
            if char.isdigit():
                acc_len /= int(char)
            else:
                acc_len -= 1

# 1st thought -> MLE
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        acc = ""
        cur_acc_len = 0

        for char in s:
            if char.isdigit():
                acc += acc * (int(char) - 1)
                cur_acc_len *= int(char)
            else:
                acc += char
                cur_acc_len += 1
            
            if cur_acc_len > k:
                return acc[k - 1]
        
        return acc[k - 1]
```
Aishwarya 
```python=
class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:x
        l = 0
        for i in range(len(s)):
            if s[i]>="a" and s[i]<="z":
                l += 1
                if l==k:
                    return s[i]
            else:
                l = l*int(s[i])
            if l>=k:
                break
        while i>0:
            if s[i]>="2" and s[i]<="9":
                l = l//int(s[i])
                k = k%l
            else:
                if k==l or k==0:
                    return s[i]
                l -=1
            i -=1
        return s[i]

```



## [316. Remove Duplicate Letters](https://leetcode.com/problems/remove-duplicate-letters/?envType=daily-question&envId=2023-09-26)
09/25/2023 
Pawan 

First solution with backtracking,  TLE @ 271
```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:

        max_str = "z" * len(s)
        res = []
        n = len(set(list(s)))

        dp = {} 
        def rec(i, visited, curSet):
            key = "".join(visited)
            # print(dp)
            if key in dp: 
                return dp[key]
            
            if len(visited) == n:
                dp[key] = key
                return dp[key]
            
            if i == len(s):
                dp[key] = max_str
                return max_str
            
            if s[i] in curSet: 
                dp[key] = rec(i+1, visited, curSet)
                return dp[key]

            visited.append(s[i])
            curSet.add(s[i])
            include = rec(i+1, visited, curSet)
            
            visited.pop()
            curSet.remove(s[i])
            exclude = rec(i+1, visited, curSet)
             
            dp[key] = min(include, exclude)

            return dp[(key)]

        return rec(0, [], set())


```
Second, after looking at Shang-Yi's solution
```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:

        lastIndex = {
            c: i for i, c in enumerate(s)
        }
        
        seen = set()
        stack = []
        
        for i, c in enumerate(s):
            if c in seen:
                continue 
            
            while stack and c < stack[-1] and i < lastIndex[stack[-1]]:
                seen.remove(stack.pop())
            
            stack.append(c)
            seen.add(c)
        
        return "".join(stack)
    
```
Victor

I got a bit lost. I implemented this inefficient backtracking algorithm and got Time Limit Exceeded on Test Case 271.
```python
import bisect

class Solution:
    num_letters_in_alphabet = ord('z') - ord('a') + 1 # const

    def removeDuplicateLetters(self, s: str) -> str:
        letter_positions = [[] for i in range(Solution.num_letters_in_alphabet)]
        for i, c in enumerate(s):
            letter_positions[ord(c) - ord('a')].append(i)
        
        # each element: (letter_index, index_in_s, letters_remaining, count_tried_letters)
        stack = [(None, -1, tuple(i for i, x in enumerate(letter_positions) if x), 0)]
        while True:
            print(len(stack))
            _, last_index, letters_remaining, count_tried_letters = stack[-1]
            if len(letters_remaining) == 0:
                return "".join(chr(ord("a") + i) for i,_,_,_ in stack[1:])
            if count_tried_letters < len(letters_remaining):
                letter = letters_remaining[count_tried_letters]
                positions_of_letter = letter_positions[letter]
                index = Solution.find_first_greater_than_or_equal(positions_of_letter, last_index)
                if index < len(positions_of_letter):
                    stack.append((letter, positions_of_letter[index], (*letters_remaining[:count_tried_letters], *letters_remaining[count_tried_letters+1:]), 0))
                else:
                    Solution.advanceTopToNextLetter(stack)
            else:
                stack.pop()
                Solution.advanceTopToNextLetter(stack)

    def advanceTopToNextLetter(stack):
        letter_index, index_in_s, letters_remaining, count_tried_letters = stack[-1]
        stack[-1] =  (letter_index, index_in_s, letters_remaining, count_tried_letters + 1)

    def find_first_greater_than_or_equal(arr, x):
        return bisect.bisect_left(arr, x)
```
My second solution, after reading you guys', somewhat C-style with arrays:
```python
import numpy as np

class Solution:
    ord_a = ord('a')
    num_letters_in_alphabet = ord('z') - ord_a + 1 # const

    def removeDuplicateLetters(self, s: str) -> str:
        last_position = np.empty((Solution.num_letters_in_alphabet,), dtype=np.int16)
        for i, c in enumerate(s):
            last_position[ord(c) - Solution.ord_a] = i
        result_needs = np.ones((Solution.num_letters_in_alphabet,), dtype=bool)
        result = []
        for i, c_str in enumerate(s):
            c = ord(c_str) - Solution.ord_a
            if result_needs[c]:
                # First, remove all letters in result that could come later
                while result and c < result[-1] and last_position[result[-1]] > i:
                    result_needs[result.pop()] = True
                # Then, append this letter
                result.append(c)
                result_needs[c] = False
        return "".join(chr(Solution.ord_a + i) for i in result)

```
Shang-Yi 
```python
# credit: Editorial

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        last_pos = {}
        for i, char in enumerate(s):
            last_pos[char] = i
        
        def char_shows_later(idx, char):
            nonlocal last_pos
            if idx < last_pos[char]:
                return True
            return False


        for i, char in enumerate(s):
            if char not in stack:
                # If top of stack is greater than incoming char, append it later (if possible)
                # will produce an optimal solution.
                while stack and char < stack[-1] and char_shows_later(i, stack[-1]):
                    stack.pop()

                stack.append(char)
            
        return "".join(stack)
```
Aishwarya 
```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        res, visited = [], set()
        dp = {s[i]: i for i in range(len(s))}

        for i in range(len(s)):
            if s[i] not in visited:
                while res and s[i]<res[-1] and i<dp[res[-1]]:
                    visited.remove(res.pop())
                visited.add(s[i])
                res.append(s[i])
        return "".join(res)
        

```



## [389. Find the Difference](https://leetcode.com/problems/find-the-difference/submissions/?envType=daily-question&envId=2023-09-25)
09/24/2023 
Pawan 
```python
from collections import Counter 
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:

        s_c = Counter(s)
        t_c = Counter(t)

        for k, v in t_c.items():
            t_c[k] -= s_c[k]
            if t_c[k] != 0 :
                return k
        
        for k, v in t_c.items():
            if v != 0:
                return k 
```
Victor
```python
from collections import Counter
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return next(iter(Counter(t) - Counter(s)))
```
Shang-Yi 
```python
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s_ctr = Counter(s)
        t_ctr = Counter(t)

        for k, v in t_ctr.items():
            if s_ctr[k] != v :
                return k
```
Aishwarya 
```
```

# Template 
## [Problem Name](Problem URL)
#### MM/DD/YYYY 
Pawan 
```python

```
Victor
```python
```
Shang-Yi 
```python
```
Aishwarya 
```python
```
