Palindromic Substrings All Nodes Distance K in Binary Tree Integer to Roman Binary Tree Vertical Order Traversal Diagonal Traverse

Find First and Last Position of Element in Sorted Array Max Area of Island Construct Binary Tree from Pre-order and In-order Traversal Pour Water ZigZag Conversion

Beta

EQ-1

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

classSolution: defcountSubstrings(self, s: str) -> int: result = 0 memo = [] i = 0

whilei < len(s): j = i whilej < len(s) and s[j] == s[i]: result+= j - i + 1 j+= 1 memo.append((i,j - 1)) i = j

forleft, right in memo: left-= 1; right += 1

whileleft >= 0 and right < len(s) and s[left] == s[right]: result+= 1; left -= 1; right += 1

returnresult

classSolution1: defcountSubstrings(self, s: str) -> int: N = len(s) ans = 0 forcenter in range(2*N - 1): left = center // 2 right = left + center % 2 whileleft >= 0 and right < N and s[left] == s[right]: ans+= 1 left-= 1 right+= 1 returnans

EQ-2 *

We are given a binary tree (with root node root), a target node, and an integer value K. Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

def annotateParent(root, par): if not root: return root.par = par annotateParent(root.left, root) annotateParent(root.right, root)

annotateParent(root, None) q = collections.deque([(target, 0)]) seen = {target} ans = [] while q: node, d = q.popleft() if d == K: ans.append(node.val) for nxtNode in (node.left, node.right, node.par): if nxtNode and nxtNode not in seen: q.append((nxtNode, d+1)) seen.add(nxtNode) return ans

EQ-3

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

classSolution1: defintToRoman(self, num: int) -> str: values = [ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 ] numerals = [ "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" ] res = "" for i, v in enumerate(values): res += (num//v) * numerals[i] num %= v return res

EQ-4

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None

class Solution: def verticalOrder(self, root: TreeNode) -> List[List[int]]: if root is None: return [] q = [(root, 0)] res = collections.defaultdict(list) while q: node, idx = q.pop(0) res[idx].append(node.val) if node.left: q.append((node.left, idx-1)) if node.right: q.append((node.right, idx+1)) return [res[k] for k in sorted(res)]

class Solution1: def verticalOrder(self, root: TreeNode) -> List[List[int]]: cols = collections.defaultdict(list) queue = [(root, 0)] for node, iin queue: if node: cols[i].append(node.val) queue += (node.left, i - 1), (node.right, i + 1) return [cols[i] for i in sorted(cols)]

EQ-5

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

fori in range(0, len(matrix)): forj in range(0, len(matrix[0])): dd[i+j+1].append(matrix[i][j])

fork in sorted(dd.keys()): ifk%2==1: dd[k].reverse() result+= dd[k] returnresult # Step 1: Numbers are grouped by the diagonals. # Numbers in same diagonal have same value of row+col # starting indices from 1, hence i+j+1. # Step 2: Place diagonals in the result list. # But remember to reverse numbers in odd diagonals.

EQ-6

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].

# 34. Find First and Last Position of Element in Sorted Array

class Solution1: def searchRange(self, nums: List[int], target: int) -> List[int]: ifnot nums: return [-1, -1] left = bisect.bisect_left(nums, target) if left >= len(nums) or nums[left] != target: return [-1, -1] right = bisect.bisect_right(nums, target) return [left, right-1]

# Will do 2 binary searches, one for the upper index of the target and one for # the lower index of the target.

# Go to the middle point # if the middle point is your target check value on the right # if it is also target then recurse on the right # else return this index # else recurse on the left # TODO: Look into turning this bin search to work for lower and upper.

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

def findUpperBinSearch(lo, hi): # invalid inputs if lo > hi: return-1 mid = (lo + hi) // 2 if nums[mid] == target: if (mid + 1 < len(nums)) and (nums[mid+1] == target): return findUpperBinSearch(mid+1, hi) else: returnmid elif nums[mid] < target: if (mid + 1 < len(nums)): return findUpperBinSearch(mid + 1, hi) else: return-1 else: # nums[mid] > target if (mid - 1 >= 0): return findUpperBinSearch(lo, mid-1) else: return-1

def findLowerBinSearch(lo, hi): # invalid inputs if lo > hi: return-1 mid = (lo + hi) // 2 if nums[mid] == target: if (mid - 1 >= 0) and (nums[mid - 1] == target): return findLowerBinSearch(lo, mid - 1) else: returnmid elif nums[mid] < target: if (mid + 1 < len(nums)): return findLowerBinSearch(mid + 1, hi) else: return-1 else: # nums[mid] > target if (mid - 1 >= 0): return findLowerBinSearch(lo, mid-1) else: return-1

lo = 0 hi = len(nums) - 1 upperIndex = findUpperBinSearch(lo, hi) # If first such search fails, return [-1, -1] don't bother with another search. if upperIndex == -1: return [-1, -1] lowerIndex = findLowerBinSearch(lo, hi) return [lowerIndex, upperIndex]

EQ-7

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

classSolution: defpourWater(self, heights: List[int], V: int, K: int) -> List[int]: ifnot heights or len(heights) == 0 or V == 0: returnheights

cur = K whileV > 0: whilecur > 0 and heights[cur-1] <= heights[cur]: cur-= 1 whilecur < len(heights)-1 and heights[cur] >= heights[cur+1]: cur+= 1 whilecur > K and heights[cur] >= heights[cur-1]: cur-= 1 heights[cur]+= 1 V-= 1

returnheights

EQ-10

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

class Solution: def convert(self, s: str, numRows:int) -> str: #n strings andadd them together listy = [''] * numRows sign, counter = 1, 0 if numRows == 1: return s else: for i in s: listy[counter] += i counter = counter + sign if counter == numRows - 1: sign = -1 if counter == 0: sign = 1

finalStr = ''.join(listy) return finalStr

class Solution1: def convert(self, s: str, numRows:int) -> str: if numRows == 1or numRows >= len(s): return s

L = [''] * numRows index, step = 0, 1

forx in s: L[index] += x ifindex == 0: step = 1 elif index == numRows -1: step = -1 index += step