[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
```
Google Drive
Gist
Clipboard
Sign in with Wallet
