# Review list 3

117. Populating Next Right Pointers in Each Node II

For the code below, the space complexity is O(n)

"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root is None:return root
nodes = collections.defaultdict(list)
def bfs(node, layer):
from collections import deque
Q = deque([(node,layer)])
while Q:
node, layer = Q.popleft()
nodes[layer].append(node)
if node.left:Q.append((node.left, layer+1))
if node.right:Q.append((node.right, layer+1))
bfs(root, 0)
for l in nodes:
for i in range(len(nodes[l])-1):
nodes[l][i].next = nodes[l][i+1]
return root

117. Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/518932/From-an-example-to-understand-the-code

class Solution:
def connect(self, root: 'Node') -> 'Node':
upper_tail = root
while upper_tail:
dummy_head = Node(-1)
this_tail = dummy_head
while upper_tail:
if upper_tail.left:
this_tail.next = upper_tail.left
this_tail = upper_tail.left
if upper_tail.right:
this_tail.next = upper_tail.right
this_tail = upper_tail.right
upper_tail = upper_tail.next
upper_tail = dummy_head.next
return root

https://leetcode.com/problems/odd-even-linked-list/

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
dummy1 = odd = ListNode(-1)
dummy2 = even = ListNode(-1)
tail = head
while tail:
odd.next = tail
even.next =tail.next
odd = odd.next
even = even.next
if even:
tail = even.next
else:break
odd.next = dummy2.next
return dummy1.next

https://leetcode.com/problems/find-k-closest-elements/

Bisect and by cases. Using deque instead of list can speed up the code from 780ms to 336 ms.

class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
i = bisect.bisect_left(arr, x)
used = 0
res =collections.deque([])
if k>=len(arr):return arr
l, r = i-1, i
while True:
if l>=0 and r<len(arr):
if abs(arr[l]-x)<=abs(arr[r]-x):
res.appendleft(arr[l])
l -= 1
used += 1
else:
res.append(arr[r])
r += 1
used += 1
if used ==k:break
elif l>=0:
res.appendleft(arr[l])
used += 1
l -= 1
if used ==k:break
else:
res.append(arr[r])
used += 1
r += 1
if used ==k:break
return list(res)
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums = [num for num in nums if num>0]
nums = sorted(set(nums))
if not nums:return 1
if nums[0]!=1:return 1
def good(m):return nums[m]==m+1
l, r= 0, len(nums)-1
while l<r:
m = (l+r+1)//2
if good(m):l=m
else:r =m-1
return l+1+1

The above code time complexity is O(nlogn) +O(logn) as we have sort and binary sort. It is required that we need O(n) time complexity and O(1) space complexity.

A smart solution can be found here

https://leetcode.com/problems/first-missing-positive/discuss/17080/Python-O(1)-space-O(n)-time-solution-with-explanation

class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums.append(0)
n = len(nums)
for i in range(len(nums)): #delete those useless elements
if nums[i]<0 or nums[i]>=n:
nums[i]=0
for i in range(len(nums)): #use the index as the hash to record the frequency of each number
#print(nums[i])
nums[nums[i]%n]+=n
for i in range(1,len(nums)):
if nums[i]//n==0:
return i
return n

https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/

My original naive solution

"""
# Definition for a Node.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if head is None:
new_head = Node(insertVal)
new_head.next = new_head
return new_head
min_node = tail = head
max_node = head
tail = head.next
while tail!=head:
if tail.val<min_node.val:
min_node = tail
elif tail.val>=max_node.val:
max_node = tail
tail = tail.next
new_node = Node(insertVal)
# print(min_node.val, max_node.val)
if max_node.val<=insertVal or min_node.val>=insertVal:
max_node.next = new_node
new_node.next = min_node
return head
tail = min_node
while True:
#print(tail.val)
if tail.next.val>=insertVal:
nxt = tail.next
tail.next = new_node
new_node.next = nxt
break
tail = tail.next
return head

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi