@ww884203 I can understand your general idea. But could you elaborate on how you would actually proceed to code it up. I think it would not be easy to find the union nodes.
ayushpatwari
@ayushpatwari
Posts made by ayushpatwari

RE: Union of two binary trees (if they share common nodes)

RE: Given a (0,1) grid and coordinates (x,y) find the circumference (perimeter) of the enclosing island of 1's
@dat.vikash The problem is to find the perimeter, not the number of surrounding one's. I think drawing a diagram and marking out the island will help. Also you can check this problem which was added recently : https://leetcode.com/problems/islandperimeter/

RE: Given a (0,1) grid and coordinates (x,y) find the circumference (perimeter) of the enclosing island of 1's
@SergeyTachenov
This seems like a really good approach to me. However I am unclear why the 3rd example has circumference of 5. Shouldn't it be 13 ? Also, i was assuming that with this approach you are going to pad the entire matrix with 0's all around (or at least logically). I am not sure if you have implemented that way. But that would definitely work.Here is how I solved it:
Key Observation:
In an island how many units can a single 1 contribute ?0000 0100 0000
In this case the only 1 contributes 4 (= the actual circumference)
0000 0110 0000
In this case the each 1 contributes 3 (the actual circumference = 6)
0000 0110 0010
In this case the two 1's contributes 3 and one of them contributes 2 (the actual circumference = 8)
Lastly,
0010 0111 0010
In this case the all 1's contributes 3 and the middle one contributes 0 (the actual circumference = 12)
Now, contribution for any 1 = max degree (=4)  actual outdegree (You can confirm that from all the examples)
So basically algorithm is :
 Perform dfs/bs
 while visiting each node count its outdegree and compute contribution => add it to total circumference

RE: Given a (0,1) grid and coordinates (x,y) find the circumference (perimeter) of the enclosing island of 1's
@SergeyTachenov You are correct in understanding the coordinate system and the values. I have edited the post with the correct values! (posted in a hurry and hence the mistakes in values)

Given a (0,1) grid and coordinates (x,y) find the circumference (perimeter) of the enclosing island of 1's
E.g
01110 00110 11001 01010 (2,3) : circumference = 10 (3, 5) or (4,4) : circumference = 4 (4, 2): circumference = 8

Union of two binary trees (if they share common nodes)
e.g
Tree 1: Tree 2: A B / \ / \ B C D E /  / \ \ D ... C F G Union: A / \ B C / \  D E ... / \ \ C F G
The union of the two trees should be returned if there is an overlap. We don't know which tree might be a subtree of the other. The result should be a new tree [inputs should not be modified]
I proposed a recursive solution which would work if we knew that Tree2 could be a subtree of the other. If this is not assumed how do I go about it ?

Share my Python Simple Solution Dict + BackTracking
class Solution(object): def calcEquation(self, equations, values, queries): from collections import defaultdict dens = defaultdict(list) for i, eq in enumerate(equations): dens[eq[0]].append((eq[1], values[i])) dens[eq[1]].append((eq[0], 1 / values[i])) def searchfrac(cur, sv, frac): if cur not in dens or sv not in dens or visited[cur]: return 1.0 if cur == sv: return frac visited[cur] = True f = 1.0 for den, val in dens[cur]: f = searchfrac(den, sv, frac * val) if f != 1.0: break visited[cur] = False return f visited = {var : False for var in dens.keys()} ans = [searchfrac(q[0], q[1], 1.0) for q in queries] for i in range(len(ans)): if ans[i] == 1.0: ans[i] = searchfrac(queries[i][1], queries[i][0], 1.0) return ans

Share Slightly Different Concise DP Approach, O(n*k), O(k) memory (beats 99%)
class Solution(object): def maxProfit(self, k, prices): if len(prices) < 2: return 0 if k < len(prices) / 2: buy = [1e18] * (k + 1) sell = [0] * (k + 1) for price in prices: for i in range(1, k + 1): sell[i] = max(sell[i], buy[i] + price) buy[i] = max(buy[i], sell[i  1]  price) return max(sell) else: prof = 0 for i in range(1, len(prices)): if prices[i] > prices[i  1]: prof += prices[i]  prices[i  1] return prof
I formulated this idea based on the solution for Buy and Sell Stock III where some solutions explained a state machine. We define the following dp functions:
buy[i][j] = Maximum profit at to buy stock at index i while making j'th buy tranxn sell[i][j] = Maximum profit at to buy stock at index i while making j'th sell tranxn
DP equations:
sell[i][j] = max(sell[i][j], buy[i  1][j] + price[i]) buy[i][j] = max(buy[i][j], sell[i][j  1]  price[i])
Since state for each j depends on only previous state (i  1)
For each price:sell[j] = max(sell[j], buy[j] + price) buy[j] = max(buy[j], sell[j  1]  price)
For the case k > len / 2 I follow similar approach as by the best answers to calculate maximum profit by collecting all possible increase in stock price.

RE: Share my Python Stack Simple Solution (Easy to understand)
@StefanPochmann well honestly I didn't know I could do that (I am just starting to get a hang of python syntactic sugar). I have edited the post now :)

Share My One Pass Python Solution
class Solution(object): def validUtf8(self, data): i = 0 while i < len(data): # compute length of current encoding numb = 0 for msb in range(0, 8)[::1]: if (1 & data[i] >> msb): numb += 1 else: break # number of msb 1's can be 0, 2, 3, 4 if numb == 1 or numb > 4 or i + (numb  1) >= len(data): return False elif numb > 0: # process current encoding and return false if cannot numb = 1 for j in range(i + 1, i + numb + 1): if (data[j] >> 6 != 2): return False i += numb i += 1 return True