3203. Find Minimum Diameter After Merging Two Trees | Weekly Leetcode 404

[@beeramrahulreddy11]

Hey, can you also touch upon today's 3rd problem of weekly contest?

[@tommyshelby6277]

I will try to explain, inviting @codingmohan for review and optimizations possible FIRST:: Consider it as an LIS problem where your goal is to find the longest increasing subsequence so pseudo code becomes like: for i in range(n): for j in range(i): dp[i]=max(dp[i], dp[j]+1) # easy SECOND:: Now the contraint added is your j'th element should be having a property, that element at index j, and element at index i, their sum and then remainder must be having same value , say `rem`, where the previous subsequence ended at index j, with sum and then remainder, `rem` If you see closely, we just added another dimension `rem` whose value ranges from 0 to k-1(both inclusive) for i in range(n): for j in range(i): rem = (nums[i]+nums[j])%k dp[i][rem]=max(dp[i][rem], dp[j][rem]+1) # easy! BASE CASE:: just like LIS, every subsequence can start from that element itself, so for i in range(n): for ck in range(k): dp[i][ck]=1 # DONE!!! JUST PRINT THE MAX VALUE IN ENTIRE DP ARRAY!

[@codingmohan]

I think DP is not required at all. kzbin.info/www/bejne/jJDFh594lrebY9U