```class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
s1Dict = {}

for char in s1:
if char not in s1Dict:
s1Dict[char] = 1
else:
s1Dict[char] += 1

left = 0

compareDict = {}

for right in range((left + (len(s1) - 1)), len(s2)):
if s2[left] in s1:
compare = s2[left:right + 1] #makes a list of chars from left to right pointers
for char in compare:
if char not in compareDict:
compareDict[char] = 1
else:
compareDict[char] += 1
if compareDict == s1Dict:
return True
else:
compareDict.clear()
left += 1
continue

else:
left += 1

return False ```
```class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1

maxArea = 0

while left < right:
heightOne = height[left]
heightTwo = height[right]

area = min(heightOne, heightTwo) * (right - left)
maxArea = max(area, maxArea)

if heightTwo >= heightOne: #if heights are equal, it doesn't matter if you move left or right pointer
left += 1
elif heightTwo < heightOne:
right -= 1

return maxArea

# BRUTE FORCE
#         maxArea = 0

#         for i in range(len(height)):
#             for secondI in range(i + 1, len(height)):
#                 heightOne = height[i]
#                 heightTwo = height[secondI]
#                 area = min(heightOne, heightTwo) * (secondI - i)
#                 maxArea = max(area, maxArea)

#         return maxArea ```
```class Solution:
def characterReplacement(self, s: str, k: int) -> int:
count = {}

result = 0

left = 0

for right in range(len(s)):
#add s[right] to count dictionary
count[s[right]] = 1 + count.get(s[right], 0) #if s[right] does not exist in count hashmap, then set default value to 0

#make sure current window is valid
#while (windowLength - length of most frequent char in count hashmap) > k
while (right - left + 1) - max(count.values()) > k: #this statement means window is no longer valid
#need to remove one from s[left]
count[s[left]] -= 1
left += 1

result = max(result, right - left + 1)

return result ```
```class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = []

nums.sort()

for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]: #this is so you don't reuse same value twice to avoid duplicates at end
continue

#next part is basically two sum

l, r = i + 1, len(nums) - 1

while l < r:
threeSum = a + nums[l] + nums[r]

if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
result.append([a, nums[l], nums[r]])
#only need to shift left pointer as right pointer will be moved by code above
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1

return result

#two sum solutions below for reference

def twoSum(numbers, target):
left = 0
right = len(numbers) - 1
compare = 0

for i in range(0, len(numbers)):
compare = numbers[left] + numbers[right]
if compare > target:
right -= 1
elif compare < target:
left += 1
elif compare == target:
return [left + 1, right + 1]

def twoSum(self, nums: List[int], target: int) -> List[int]:
num_dictionary = {}
for i in range(0, len(nums)):
number = nums[i]
if target - number not in num_dictionary:
#number will be key and index (i) will be value
#adding number to dictionary AFTER checking 1st value
#if [2, 1, 3] and target = 4, 4 -2 = 2 and 2 will be present in dictionary but we cannot use 2 + 2
num_dictionary[number] = i
elif target - number in num_dictionary:
return [i, num_dictionary[target - number]]

```
```class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numlist = set(nums)
#you need set or else it's too slow
longest = 0

#the concept is you are checking to see if there is a left neighbor. If not, then there is a new sequence of conseuctive numbers.

for n in nums:
if (n - 1) not in numlist:
length = 0
while (n + length) in numlist:
length += 1
longest = max(length, longest)
return longest ```
```class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
#if there were no time complexity restriction, you can use nested for loops and just continue if index of first for loop == index of second for loop
#if there were no divsion restriction, you can just find prod(nums) len(nums) times and divide by num[i] and append to result

res =  * len(nums)

prefix = 1

for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
res[i] *= postfix
postfix *= nums[i]
return res

#must be in O(N) time, O(1) space, and not use divide operator

```
```class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
def Remove(lst): #to remove repeats at end
return ([list(i) for i in {*[tuple(sorted(i)) for i in lst]}])

result = []
for i in range(0, len(strs)):
anagram_subset = [strs[i]]
sorted_string = sorted(strs[i])
for d in range(0, len(strs)):
#to avoid repeat
#maybe change to start, end pointers to avoid making duplicate in first place?
if d == i:
continue
if sorted(strs[d]) == sorted_string:
anagram_subset.append(strs[d])
anagram_subset.sort()
result.append(anagram_subset)
anagram_subset = []
return Remove(result)

#Big O is n * n * n log N lol

#more efficient solution

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list) #map charCount to list of anagrams

for s in strs:
count =  * 26 # a ... z

for c in s:
count[ord(c) - ord("a")] += 1 #mapping to ASCII and then adding 1 so that a = 1, b = 2, etc.

res[tupule(count)].append(s)

return res.values()

#big O(m * n * 26) which is just (m * n)```
```class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-s for s in stones]
heapq.heapify(stones)

while len(stones) > 1:
first = abs(heapq.heappop(stones)) #linear time for python
second = abs(heapq.heappop(stones))

if first > second:
heapq.heappush(stones, second - first) #remember that since it's a minHeap we need negative numbers so it's second - first

#edge case to account if stones is empty whether originally or after smashing
stones.append(0)

return abs(stones)```
```class KthLargest:

#Big O: n
def __init__(self, k: int, nums: List[int]):
#minHeap with k largest integers

self.minHeap, self.k = nums, k
heapq.heapify(self.minHeap)

while len(self.minHeap) > k:
heapq.heappop(self.minHeap)

#Big O: log N
def add(self, val: int) -> int:
heapq.heappush(self.minHeap, val)

if len(self.minHeap) > self.k:
heapq.heappop(self.minHeap)

return self.minHeap

#Total big O: n log n

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)```
```class Solution:
def binarySearch(self, nums, target):
start, end = 0, len(nums) - 1

while start <= end:
middle = (start + end) // 2
current = nums[middle]

if target > current:
start = middle + 1
elif target < current:
end = middle - 1
else:
return middle
#return current if you want value instead of index
return -1

def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0:
return -1
elif len(nums) == 1:
if nums != target:
return -1
else:
return 0
else:
rotated = False
lastIdx = len(nums) - 1

if nums[lastIdx] < nums:
rotated = True

if rotated == False:
return self.binarySearch(nums, target)
else:
previous = nums
rotateIdx = 0
for i in range(1, len(nums)):
if nums[i] < previous:
rotateIdx = i
previous = nums[i]

array1 = nums[:rotateIdx]
array1Length = len(array1)
array2 = nums[rotateIdx:]

if self.binarySearch(array1, target) == -1 and self.binarySearch(array2, target) != -1:
return array1Length + self.binarySearch(array2, target)
return self.binarySearch(array1, target)
```
```class Solution:
#number of permutations = n!
def permute(self, nums: List[int]) -> List[List[int]]:
result = []

if len(nums) == 1:
return [nums[:]]

for i in range(len(nums)):
#pop off first element
n = nums.pop(0)

#numswill now have one less value, will append popped value later
perms = self.permute(nums)

for perm in perms:
perm.append(n)

result.extend(perms)
nums.append(n)

return result
```
```class Solution:

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []

#i is index of candidates
def dfs(i, current, total):
if total == target:
#if you do not add .copu() it will append empty arrays
result.append(current.copy())
return
if i >= len(candidates) or total > target:
return

#decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index

#1) try adding candidates[i]
current.append(candidates[i])
dfs(i, current, total + candidates[i])
#2) move on to next index
current.pop()
dfs(i + 1, current, total)

dfs(0, [], 0)
return result ```
```class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = []
result = []

#i is index of subset
def dfs(i):
if i >= len(nums):
result.append(subset.copy())
return

#decision to include nums[i]
subset.append(nums[i])
#this recursive call will be given filled subset
dfs(i + 1)

#decision NOT to include nums[i]
subset.pop()
#this recursive call will be given empty subset
dfs(i + 1)

dfs(0)

return result

```
```class Tree(object):
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right

tx = Tree(4, Tree(1, Tree(-2, None, Tree(3, None, None))), Tree(3, Tree(1, None, None), Tree(2, Tree(-4, None, None), Tree(-3, None, None))))

def find_paths(root, required_sum):
allPaths = []

def find_paths_recursive(currentNode, required_sum, currentPath, allPaths):
if currentNode is None:
return

# add the current node to the path
currentPath.append(currentNode.val)

# if the current node is a leaf and its value is equal to required_sum, save the current path
if currentNode.val == required_sum and currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub-tree
find_paths_recursive(currentNode.left, required_sum -
currentNode.val, currentPath, allPaths)
# traverse the right sub-tree
find_paths_recursive(currentNode.right, required_sum -
currentNode.val, currentPath, allPaths)

# remove the current node from the path to backtrack,
# we need to remove the current node while we are going up the recursive call stack.
del currentPath[-1]

find_paths_recursive(root, required_sum, [], allPaths)

return allPaths

find_paths(tx, 5)```
```# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
#order of first two conditionals is important
if not subRoot: return True
if not root: return False
if self.sameTree(root, subRoot): return True

return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

def sameTree(self, s, t):
if not s and not t: return True
if s and t and s.val == t.val:
return self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)

return False

```
```# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q: return True
if not p or not q: return False
if p.val != q.val: return False

return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
```
star

Thu Sep 22 2022 20:42:29 GMT+0000 (UTC) https://leetcode.com/problems/permutation-in-string/

#python #neetcode #hashmap
star

Thu Sep 22 2022 18:45:49 GMT+0000 (UTC) https://leetcode.com/problems/container-with-most-water/submissions/

#python #neetcode #pointer #two
star

Thu Sep 22 2022 03:51:20 GMT+0000 (UTC) https://leetcode.com/problems/longest-repeating-character-replacement/

#python #neetcode
star

Thu Sep 22 2022 01:29:14 GMT+0000 (UTC) https://leetcode.com/problems/3sum/submissions/

#python #neetcode #twosum
star

Tue Sep 20 2022 04:14:22 GMT+0000 (UTC) https://leetcode.com/problems/longest-consecutive-sequence/

#python #neetcode #sort
star

Tue Sep 20 2022 00:26:15 GMT+0000 (UTC) https://leetcode.com/problems/product-of-array-except-self/

#python #neetcode #sort
star

Mon Sep 19 2022 22:07:04 GMT+0000 (UTC) https://leetcode.com/problems/group-anagrams/

#python #neetcode #sort
star

Tue Aug 16 2022 06:14:12 GMT+0000 (UTC) https://leetcode.com/problems/last-stone-weight/

#python #neetcode #minheap #maxheap #pop #push #heapify
star

Sat Aug 13 2022 21:49:52 GMT+0000 (UTC) https://leetcode.com/problems/kth-largest-element-in-a-stream/

#python #leetcode #neetcode #stream #heap
star

Fri Aug 12 2022 22:53:09 GMT+0000 (UTC) https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/

#python #binary #search #leetcode #neetcode
star

Tue Aug 09 2022 20:11:11 GMT+0000 (UTC) https://leetcode.com/problems/permutations/submissions/

#python #depth #first #search #recursive #neetcode
star

Tue Aug 09 2022 19:43:50 GMT+0000 (UTC) https://leetcode.com/problems/combination-sum/submissions/

#python #depth #first #search #recursive #neetcode
star

Tue Jul 19 2022 00:13:34 GMT+0000 (UTC)

#python #tree #recursion #dfs #neetcode
star

Mon Jul 18 2022 23:05:55 GMT+0000 (UTC)

#python #tree #recursion #dfs #neetcode
star

Mon Jul 18 2022 22:17:42 GMT+0000 (UTC) https://leetcode.com/problems/same-tree/submissions/

#python #tree #recursion #dfs #neetcode

#### Save snippets that work with our extensions   