0x0FFF
BAN USERIf a single node can be considered as a subtree the solution is trivial - just check duplicated leaf nodes. If the "subtree" should have at least 2 nodes, then we are ok to check all the triplets of "node, left child, right child" when both left and right children are either leafs or missing (but not both missing). Here's some code:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def isleaf(node):
if node is None:
return True
else:
if node.left is None and node.right is None:
return True
return False
def get_triplets(node):
res = []
if node.left is None:
res.append(None)
else:
res.append(node.left.value)
res.append(node.value)
if node.right is None:
res.append(None)
else:
res.append(node.right.value)
return ['|'.join([str(x) for x in res]), '|'.join([str(x) for x in res[::-1]])]
def find_triplets(node):
if node is None or isleaf(node):
return []
if isleaf(node.left) and isleaf(node.right):
return get_triplet(node)
return find_triplets(node.left) + find_triplets(node.right)
def hasdup(node):
unique = set()
for tr in find_triplets(node):
if tr in unique:
return True
unique.add(tr)
return False
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
d = TreeNode(1)
e = TreeNode(2)
f = TreeNode(5)
d.left = f
d.right = e
g = TreeNode(0)
g.left = a
g.right = d
print hasdup(g)
Your solution for n/4 is incorrect. If you check for k*n/8 elements, there is a probability that you would find 2 sequential equal elements, while the total count of these element is only n/8 or n/8+1. While having 3 elements of the same value from this sample array is a corner case when a group of n/4 elements starts with the point where you sample at.
There is no solution with O(1) for the problem as it is stated, because having k*n/8 samples you have to check the exact size of each group having two n/8 sequential equal sample values. Corner case is when "all the other elements of the array except by repeating one are unique" - then yes, you can use sampling solution
Its important to consider that the smaller subarray might be both on the left and on the right hand from the split point. Here's a code:
def max_subarray(el,max_sf,max_eh,func):
if max_eh is None:
max_eh = el
max_sf.append(el)
else:
max_eh = func(el, max_eh + el)
max_sf.append(func(max_sf[-1], max_eh))
return max_eh
def maxsum(l):
min_sf,max_sf = [], []
min_eh,max_eh = None, None
for i in range(len(l)-1):
min_eh = max_subarray(l[i],min_sf,min_eh,min)
max_eh = max_subarray(l[-i-1],max_sf,max_eh,max)
max_sf = max_sf[::-1]
maxdiff = max_sf[-1] - min_sf[0]
for i in range(len(l)-1):
if max_sf[i] - min_sf[i] > maxdiff:
maxdiff = max_sf[i] - min_sf[i]
return maxdiff
def metamaxsum(l):
return max(maxsum(l),maxsum(l[::-1]))
print metamaxsum([1,1,1,-1,-5,100])
print metamaxsum([2,-1,-2,1,-4,2,8])
print metamaxsum([-10,7,-3,2,2,-20,1])
Here's a simple Python solution with memorization
- 0x0FFF January 25, 2016