Snippets Collections
def generateParenthesis(n):
    #only add parentehsis if openN < n 
    #only add close parenthesis if closeN < openN 
    #valid if open == closed == n 

    stack = []
    res = []
    
    def backtrack(openN, closeN): 
        if openN == closeN == n: 
            res.append("".join(stack))
            return 
        if openN < n: 
            stack.append('(')
            backtrack(openN + 1, closeN)
            stack.pop()
        if closeN < openN: 
            stack.append(")")
            backtrack(openN, closeN + 1)
            stack.pop()
        #stack.pop() is necessary to clean up stack and come up with other solutions 
        
    backtrack(0, 0)
    #concept is you build openN, closeN but initially, they are at 0 
    return res 

generateParenthesis(3)
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 
def length_of_longest_substring(str1, k):
    window_start, max_length, max_repeat_letter_count = 0, 0, 0 
    
    frequency_map = {} 
    
    #try to extend window [window_start, window_end] 
    for window_end in range(len(str1)): 
        right_char = str1[window_end]
        if right_char not in frequency_map: 
            frequency_map[right_char] = 1 
        else: 
            frequency_map[right_char] += 1 
    
        #we don't need to place the maxRepeatLetterCount under the below 'if'
        #while shrinking window, we don't need to update maxRepeatLetterCount 
        #since we are only interested in longest valid substring, our sliding windows do not have to shrink even if a window may cover an invalid substring 
        max_repeat_letter_count = max(max_repeat_letter_count, frequency_map[right_char]) 
        
        #determine if window is still valid 
        #if remaining letters are more than k, it is time to shrink window as we are not allowed to replace more than k letters 
        evaluate_window = window_end - window_start + 1 - max_repeat_letter_count
        if evaluate_window > k: 
            left_char = str1[window_start] 
            frequency_map[left_char] -= 1 
            window_start += 1 
        
        max_length = max(max_length, window_end - window_start + 1) 
    
    return max_length 

length_of_longest_substring("aabccbb", 2)








#alternate solution 
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 = [1] * 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 = [0] * 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[0])
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[0]
    

#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[0] != target: 
                return -1 
            else: 
                return 0 
        else: 
            rotated = False
            lastIdx = len(nums) - 1 

            if nums[lastIdx] < nums[0]: 
                rotated = True 

            if rotated == False: 
                return self.binarySearch(nums, target) 
            else: 
                previous = nums[0]
                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)
            #adding popped back 
            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

Tue Sep 27 2022 02:03:10 GMT+0000 (Coordinated Universal Time) https://leetcode.com/problems/generate-parentheses/

#python #neetcode #parenthesis #open #close
star

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

#python #neetcode #hashmap
star

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

#python #neetcode #pointer #two
star

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

#python #neetcode
star

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

#python #neetcode #twosum
star

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

#python #neetcode #sort
star

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

#python #neetcode #sort
star

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

#python #neetcode #sort
star

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

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

Sat Aug 13 2022 21:49:52 GMT+0000 (Coordinated Universal Time) 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 (Coordinated Universal Time) 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 (Coordinated Universal Time) https://leetcode.com/problems/permutations/submissions/

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

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

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

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

#python #tree #recursion #dfs #neetcode

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension