LEETCODE SOLUTIONS

572 .  Subtree of Another Tree Given the roots of two binary trees  root  and  subRoot , return  true  if there is a subtree of  root  with the same structure and node values of  subRoot  and  false  otherwise. A subtree of a binary tree  tree  is a tree that consists of a node in  tree  and all of this node's descendants. The tree  tree  could also be considered as a subtree of itself.   Example : Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true SOLUTION: class Solution: def isSubtree(self, r: Optional[TreeNode], sr: Optional[TreeNode]) -> bool: if not sr: return True if not r: return False if self.sameTree(r,sr): return True return (self.isSubtree(r.left, sr) or self.isSubtree(r.right, sr)) def sameTree(self, r, sr): if not r and not sr: return True if r and sr and r.val == sr.val: return (self.sameTree(r.left, sr.left) and self.same

4 49 .  Serialize and Deserialize BST Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a  binary search tree . There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible.   Example 1: Input: root = [2,1,3] Output: [2,1,3] Example 2: Input: root = [] Output: []   Constraints: The number of nodes in the tree is in the range  [0, 10 4 ] . 0 <= Node.val <= 10 4 The input tree is  guaranteed  to be a binary search tree. Solution : class Codec: def serialize(self, root: Optional[TreeNode]) -> str:

  435 .  Non-overlapping Intervals Given an array of intervals  intervals  where  intervals[i] = [start i , end i ] , return  the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping .   Example 1: Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2: Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. Example 3: Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.   Constraints: 1 <= intervals.length <= 10 5 intervals[i].length == 2 -5 * 10 4  <= start i  < end i  <= 5 * 10 4 Solution : class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort() ans = 0

  424 .  Longest Repeating Character Replacement You are given a string  s  and an integer  k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most  k  times. Return  the length of the longest substring containing the same letter you can get after performing the above operations .   Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.   Constraints: 1 <= s.length <= 10 5 s  consists of only uppercase English letters. 0 <= k <= s.length Solution :  class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0

417 .  Pacific Atlantic Water Flow There is an  m x n  rectangular island that borders both the  Pacific Ocean  and  Atlantic Ocean . The  Pacific Ocean  touches the island's left and top edges, and the  Atlantic Ocean  touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an  m x n  integer matrix  heights  where  heights[r][c]  represents the  height above sea level  of the cell at coordinate  (r, c) . The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is  less than or equal to  the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return  a  2D list  of grid coordinates  result  where  result[i] = [r i , c i ]  denotes that rain water can flow from cell  (r i , c i )  to  both  the Pacific and Atlantic oceans .   Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Top K Frequent Elements Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: 1 <= nums.length <= 10 5 -10 4  <= nums[i] <= 10 4 k  is in the range  [1, the number of unique elements in the array] . It is  guaranteed  that the answer is  unique .   Follow up:  Your algorithm's time complexity must be better than  O(n log n) , where n is the array's size. Solution : class Solution:     def topKFrequent(self, n: List[int], k: int) -> List[int]:                  # [1,1,1,2,2,3] &  k = 2                  f = [[] for i in range(len(n) + 1)]         # f = [[], [3], [2], [1], [], [], []]         cnt = {}         ans = []                           for i in n :             cnt[i] = 1 +  cnt.get(i,0)                  for i,j in cnt.items():             f[j].appen

Given an integer  n , return  an array  ans  of length  n + 1  such that for each  i   ( 0 <= i <= n ) ,  ans[i]  is the  number of  1 's  in the binary representation of  i .   Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101   Constraints: 0 <= n <= 10 5   Follow up: It is very easy to come up with a solution with a runtime of  O(n log n) . Can you do it in linear time  O(n)  and possibly in a single pass? Can you do it without using any built-in function (i.e., like  __builtin_popcount  in C++)?   Solution : class Solution:     def countBits(self, n: int) -> List[int]:         dp = [0] * (n+1)         c = 1                  for i in range(1, n+1):             if c * 2 == i :                 c = i             dp[i] = 1 + dp[i-c]                      return dp Explained :

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> int: p = [ i for i in range(n)] r = [1] * n def find(n1) : ans = n1 while ans != p[ans] : p[ans] = p[p[ans]] ans = p[a

322 .  Coin Change You are given an integer array  coins  representing coins of different denominations and an integer  amount  representing a total amount of money. Return  the fewest number of coins that you need to make up that amount . If that amount of money cannot be made up by any combination of the coins, return  -1 . You may assume that you have an infinite number of each kind of coin.   Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Example 3: Input: coins = [1], amount = 0 Output: 0   Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 2 31  - 1 0 <= amount <= 10 4   Solution : class Solution:     def coinChange(self, coins: List[int], amount: int) -> int:         dp = [amount + 1] * (amount + 1) #[0...7]         dp[0] = 0                  for  a in range(1, amount + 1) :             for c in coins:                 if a - c >= 0 :                     dp