leetcode-014

Alpha

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 647. Palindromic Substrings

class Solution:
def countSubstrings(self, s: str) -> int:
result = 0
memo = []
i = 0

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

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

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

return result


class Solution1:
def countSubstrings(self, s: str) -> int:
N = len(s)
ans = 0
for center in range(2*N - 1):
left = center // 2
right = left + center % 2
while left >= 0 and right < N and s[left] == s[right]:
ans += 1
left -= 1
right += 1
return ans

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 863. All Nodes Distance K in Binary Tree

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

class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 12. Integer to Roman

class Solution:
def intToRoman(self, num: int) -> str:
M = ["", "M", "MM", "MMM"];
C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
return M[num//1000] + C[(num%1000)//100] + X[(num%100)//10] + I[num%10]

class Solution1:
def intToRoman(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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 314. Binary Tree Vertical Order Traversal

# 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, i in 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 498. Diagonal Traverse

class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []

m, n = len(matrix), len(matrix[0])
direction = 0
res = []
x = y = 0
while x< m and y < n:

if not direction:
res.append(matrix[x][y])
while x-1>= 0 and y+1 < n:
x -= 1
y += 1
res.append(matrix[x][y])

if y + 1 < n:
y += 1
else:
x += 1
else:
res.append(matrix[x][y])
while x+1 < m and y-1 >= 0:
x += 1
y -= 1
res.append(matrix[x][y])
if x + 1 < m:
x += 1
else:
y += 1
direction = 1 - direction
return res


class Solution1:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
result = [ ]
dd = collections.defaultdict(list)
if not matrix:
return result

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

for k in sorted(dd.keys()):
if k%2==1: dd[k].reverse()
result += dd[k]
return result

# 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].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# 34. Find First and Last Position of Element in Sorted Array

class Solution1:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not 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:
return mid
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:
return mid
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.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 695. Max Area of Island

class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])

def dfs_area(x, y):
ans, grid[x][y] = 1, 0
if x > 0 and grid[x - 1][y] == 1: ans += dfs_area(x - 1, y)
if x < R-1 and grid[x + 1][y] == 1: ans += dfs_area(x + 1, y)
if y > 0 and grid[x][y - 1] == 1: ans += dfs_area(x, y - 1)
if y < C-1 and grid[x][y + 1] == 1: ans += dfs_area(x, y + 1)
return ans

max_area = 0
for r in range(R):
for c in range(C):
if grid[r][c] == 1:
max_area = max(max_area, dfs_area(r, c))
return max_area

EQ-8 *

Given preorder and inorder traversal of a tree, construct the binary tree.
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 105. Construct Binary Tree from Preorder and Inorder Traversal

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

class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

def build(stop):
if inorder and inorder[-1] != stop:
root = TreeNode(preorder.pop())
root.left = build(root.val)
inorder.pop()
root.right = build(stop)
return root

preorder.reverse()
inorder.reverse()

return build(None)

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/

EQ-9 *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 755. Pour Water

class Solution:
def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
if not heights or len(heights) == 0 or V == 0:
return heights

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

return heights

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)

And then read line by line: “PAHNAPLSIIGYIR”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 6. ZigZag Conversion

class Solution:
def convert(self, s: str, numRows: int) -> str:
#n strings and add 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 == 1 or numRows >= len(s):
return s

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

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

return ''.join(L)

Sigma

Feb 12, 2020
La Jolla, CA

Omega

https://leetcode.com/