leetcode-009

Alpha

Binary Tree Right Side View
*Flatten Nested List Iterator
*The Skyline Problem
Nested List Weight Sum II
Reverse Nodes in k-Group

UTF-8 Validation
Task Scheduler
*Basic Calculator
Longest Valid Parentheses
Validate Binary Search Tree

Beta

EQ-1

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Input: [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]

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
# 199. Binary Tree Right Side View

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

class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if not root:
return []
right = self.rightSideView(root.right)
left = self.rightSideView(root.left)
return [root.val] + right + left[len(right):]

# Solution 1: Recursive, combine right and left: 5 lines, 56 ms
# Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.


class Solution2:
def rightSideView(self, root):
def collect(node, depth):
if node:
if depth == len(view):
view.append(node.val)
collect(node.right, depth+1)
collect(node.left, depth+1)
view = []
collect(root, 0)
return view

# Solution 2: Recursive, first come first serve: 9 lines, 48 ms
# DFS-traverse the tree right-to-left, add values to the view whenever we first reach a new record depth. This is O(n).


class Solution3:
def rightSideView(self, root):
view = []
if root:
level = [root]
while level:
view += level[-1].val,
level = [kid for node in level for kid in (node.left, node.right) if kid]
return view

# Solution 3: Iterative, level-by-level: 7 lines, 48 ms
# Traverse the tree level by level and add the last value of each level to the view. This is O(n).
Solution 1: Recursive, combine right and left:

5 lines, 56 ms
Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.

Solution 1: Recursive, combine right and left:

5 lines, 56 ms
Compute the right view of both right and left left subtree, then combine them. For very unbalanced trees, this can be O(n^2), though.

Solution 3: Iterative, level-by-level:

7 lines, 48 ms
Traverse the tree level by level and add the last value of each level to the view. This is O(n).

https://leetcode.com/problems/binary-tree-right-side-view/discuss/56064/5-9-Lines-Python-48%2B-ms

EQ-2 *

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list – whose elements may also be integers or other lists.

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
# 341. Flatten Nested List Iterator

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def isInteger(self) -> bool:
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# """
#
# def getInteger(self) -> int:
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# """
#
# def getList(self) -> [NestedInteger]:
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# """

class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.ls = self.flatten(nestedList)
self.ls = self.ls[::-1]

def flatten(self, ls):
res = []
for item in ls:
if item.isInteger():
res.append(item.getInteger())
else:
res.extend(self.flatten(item.getList()))
return res

def next(self) -> int:
return self.ls.pop()

def hasNext(self) -> bool:
return len(self.ls) > 0

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

EQ-3 *

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
# 218. The Skyline Problem

class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
from heapq import heappush, heappop
events = [(l, -h, r) for l, r, h in buildings]
events += list({(r, 0, 0) for _, r, _ in buildings})
events.sort()
res = [[0, 0]]
live = [(0, float('inf'))]
for l, negH, r in events:
if negH:
heappush(live, (negH, r))
while live[0][1] <= l:
heappop(live)
if res[-1][1] != -live[0][0]:
res += [[l, -live[0][0]]]
return res[1:]


class Solution_dcq:
def getSkyline(self, buildings: 'List[List[int]]') -> 'List[List[int]]':
"""
Divide-and-conquer algorithm to solve skyline problem,
which is similar with the merge sort algorithm.
"""

n = len(buildings)
# The base cases
if n == 0:
return []
if n == 1:
x_start, x_end, y = buildings[0]
return [[x_start, y], [x_end, 0]]

# If there is more than one building,
# recursively divide the input into two subproblems.
left_skyline = self.getSkyline(buildings[: n // 2])
right_skyline = self.getSkyline(buildings[n // 2 :])

# Merge the results of subproblem together.
return self.merge_skylines(left_skyline, right_skyline)

def merge_skylines(self, left, right):
"""
Merge two skylines together.
"""

def update_output(x, y):
"""
Update the final output with the new element.
"""

# if skyline change is not vertical -
# add the new point
if not output or output[-1][0] != x:
output.append([x, y])
# if skyline change is vertical -
# update the last point
else:
output[-1][1] = y

def append_skyline(p, lst, n, y, curr_y):
"""
Append the rest of the skyline elements with indice (p, n)
to the final output.
"""

while p < n:
x, y = lst[p]
p += 1
if curr_y != y:
update_output(x, y)
curr_y = y

n_l, n_r = len(left), len(right)
p_l = p_r = 0
curr_y = left_y = right_y = 0
output = []

# while we're in the region where both skylines are present
while p_l < n_l and p_r < n_r:
point_l, point_r = left[p_l], right[p_r]
# pick up the smallest x
if point_l[0] < point_r[0]:
x, left_y = point_l
p_l += 1
else:
x, right_y = point_r
p_r += 1
# max height (i.e. y) between both skylines
max_y = max(left_y, right_y)
# if there is a skyline change
if curr_y != max_y:
update_output(x, max_y)
curr_y = max_y

# there is only left skyline
append_skyline(p_l, left, n_l, left_y, curr_y)

# there is only right skyline
append_skyline(p_r, right, n_r, right_y, curr_y)

return output

EQ-4

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list – whose elements may also be integers or other lists.
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

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
77
78
79
80
81
82
# 364. Nested List Weight Sum II

# """

# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """

class Solution1:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
total_sum, level_sum = 0, 0
while len(nestedList):
next_level_list = []
for x in nestedList:
if x.isInteger():
level_sum += x.getInteger()
else:
for y in x.getList():
next_level_list.append(y)
total_sum += level_sum
nestedList = next_level_list

return total_sum


class Solution_explain:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
def recursive(nestedList: List[NestedInteger]):
integer_sum = 0
list_sum = 0
cur_list = []

for e in nestedList:
if e.isInteger():
integer_sum += e.getInteger()
else:
cur_list += e.getList()

if not cur_list:
return 1, integer_sum
else:
level, list_sum = recursive(cur_list)
return level + 1, list_sum + integer_sum * (level + 1)

return recursive(nestedList)[1]

EQ-5

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, should return: 2->1->4->3->5
For k = 3, should return: 3->2->1->4->5

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
# 25. Reverse Nodes in k-Group

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
newhead = head
for i in range(k):
if newhead == None: # if not newhead:
return head
newhead = newhead.next

connect = cur = head
prev = None
for i in range(k):
cur.next, cur, prev = prev, cur.next, cur
connect.next = self.reverseKGroup(newhead, k)

return prev

# Use a dummy head, and
# l, r : define reversing range
# pre, cur : used in reversing, standard reverse linked linked list method
#jump : used to connect last node in previous k-group to first node in following k-group


class Solution1:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = jump = ListNode(0)
dummy.next = l = r = head

while True:
count = 0
while r and count < k: # use r to locate the range
r = r.next
count += 1
if count == k: # if size k satisfied, reverse the inner linked list
pre, cur = r, l
for _ in range(k):
cur.next, cur, pre = pre, cur.next, cur # standard reversing
jump.next, jump, l = pre, l, r # connect two k-groups
else:
return dummy.next

EQ-6

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  • For 1-byte character, the first bit is a 0, followed by its unicode code.
  • For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

1
2
3
4
5
6
7
Char. number range  | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

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
# 393. UTF-8 Validation

class Solution:
def validUtf8(self, data: List[int]) -> bool:
# 1B min = 0, max 127
# 2B min = 192, max 223
# 3B min = 224, max 239
# 4B min = 240, max 247
# FB min = 128, max 191

required_following = 0
x = 0
while x < len(data):
if 0 <= data[x] <= 127: required_following = 0
elif 192 <= data[x] <= 223: required_following = 1
elif 224 <= data[x] <= 239: required_following = 2
elif 240 <= data[x] <= 247: required_following = 3
else: return False

x += 1
while required_following != 0:
if x == len(data):
return False
if not (128 <= data[x] <= 191):
return False

required_following -= 1
x += 1

return True if required_following == 0 else False

EQ-7 *

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take to finish all the given tasks.

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
# 621. Task Scheduler

class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
task_counts = list(collections.Counter(tasks).values())
M = max(task_counts)
Mct = task_counts.count(M)
return max(len(tasks), (M - 1) * (n + 1) + Mct)

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
class Solution1:
def leastInterval(self, tasks: List[str], n: int) -> int:
max_freq = 0
num_task_max_freq = 0
all_freq = collections.Counter(tasks)

for letter, freq in all_freq.items():
if max_freq == freq:
num_task_max_freq += 1
elif max_freq < freq:
max_freq = freq
num_task_max_freq = 1

avaliable_slot = (n - num_task_max_freq + 1) * (max_freq - 1)
avaliable_task = len(tasks) - num_task_max_freq * max_freq
idle = max(0, avaliable_slot - avaliable_task)
return len(tasks) + idle

EQ-8

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

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
77
78
79
80
81
82
83
84
85
86
87
88
89
# 224. Basic Calculator

class Solution:
def calculate(self, s: str) -> int:
operand, sign, res = 0, 1, 0
stack = []

for ch in s:
if ch.isdigit():
operand = 10*operand + int(ch)
elif ch in "+-":
res += sign * operand
sign = 1 if ch == "+" else -1
operand = 0
elif ch == "(":
stack.append(res)
stack.append(sign)
res, sign = 0, 1
elif ch == ")":
res += operand * sign
operand = res
sign = stack.pop()
res = stack.pop()
return res + sign*operand


class Solution1_explain:
def calculate(self, s: str) -> int:

stack = []
operand = 0
res = 0 # For the on-going result
sign = 1 # 1 means positive, -1 means negative

for ch in s:
if ch.isdigit():

# Forming operand, since it could be more than one digit
operand = (operand * 10) + int(ch)

elif ch == '+':

# Evaluate the expression to the left,
# with result, sign, operand
res += sign * operand

# Save the recently encountered '+' sign
sign = 1

# Reset operand
operand = 0

elif ch == '-':

res += sign * operand
sign = -1
operand = 0

elif ch == '(':

# Push the result and sign on to the stack, for later
# We push the result first, then sign
stack.append(res)
stack.append(sign)

# Reset operand and result, as if new evaluation begins for the new sub-expression
sign = 1
res = 0

elif ch == ')':

# Evaluate the expression to the left
# with result, sign and operand
res += sign * operand

# ')' marks end of expression within a set of parenthesis
# Its result is multiplied with sign on top of stack
# as stack.pop() is the sign before the parenthesis
res *= stack.pop() # stack pop 1, sign

# Then add to the next operand on the top.
# as stack.pop() is the result calculated before this parenthesis
# (operand on stack) + (sign on stack * (result from parenthesis))
res += stack.pop() # stack pop 2, operand

# Reset the operand
operand = 0

return res + sign * operand

EQ-9

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

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
# 32. Longest Valid Parentheses

class Solution:
def longestValidParentheses(self, s):
dp = [0]*(len(s) + 1)
stack = []
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
if stack:
p = stack.pop()
dp[i + 1] = dp[p] + i + 1 - p
return max(dp)


class Solution1:
def longestValidParentheses(self, s: str) -> int:
return max(self.helper(s,'('), self.helper(s[::-1],')'))

def helper(self, s, left):
ans = 0
maxendinghere = 0
count = 0
for c in s:
if c == left: #when scan s from left to right, left is '(', otherwise is ')'
count += 1
maxendinghere += 1
else:
count -= 1
if count <0:
maxendinghere = 0
count = 0
else:
maxendinghere += 1
if count == 0:
ans = max(ans, maxendinghere)
return ans

EQ-10

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
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
# 98. Validate Binary Search 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 isValidBST(self, root: TreeNode) -> bool:
stack = []
current = root
last_num = float('-inf')
while stack or current:
while current:
stack.append(current)
current = current.left

current = stack.pop()
if last_num >= current.val:
return False
last_num = current.val
current = current.right
return True


class Solution1:
# def isValidBST(self, root: TreeNode) -> bool:
def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')):
if not root:
return True
if root.val <= largerThan or root.val >= lessThan:
return False
return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \
self.isValidBST(root.right, lessThan, max(root.val, largerThan))Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Sigma

Feb 10, 2020
La Jolla, CA

Omega

https://leetcode.com/