One thing to notice when using Morris Traversal is that: you are modifying the tree structure. Therefore, it's very important that you REVERSE the change back.
dragonmigo
@dragonmigo
Posts made by dragonmigo

RE: My solution using Morris Traverse, time complexity?

RE: Are duplicates allowed for the final answer?
That makes sense actually if you think about it.
Id in Employee table might be the primary key, while Name column can simply contain duplicates. It's common for two employees to have the same first name.

Accepted solution using InnerJoin and GroupBy
SELECT Scores.Score, COUNT(Ranking.Score) AS RANK FROM Scores , ( SELECT DISTINCT Score FROM Scores ) Ranking WHERE Scores.Score <= Ranking.Score GROUP BY Scores.Id, Scores.Score ORDER BY Scores.Score DESC;

RE: Don't treat it as a 2D matrix, just treat it as a sorted list
There is actually a third reason why this method is not the optimal: Cache hit rate. This method is not as cache friendly as doing the row>column 2 binary search way.

RE: Why MLE? I think i freed both stacks in the end
There are multiple places to be modified.

top() and getMin() returns nothing for empty stack, which does not make sense. Return some error code instead.

when you push() for the first time, this part of code does not deal with top_min very well:
struct node * min_p = new node; min_p > val = x; if (top_min != NULL){ min_p > next = top_min; } top_min = min_p;
Notice that the first created min_p is not initialized properly, which means min_p>next could be anything. This could cause problem when you pop last node, and min_p will be some unknown value.


RE: Share my O(n) time, O(1) space solution
No, it is O(n). There is a nested loop there, but think it this way: in the inner loop, we are doing swap for each A[i] ONLY if A[i1] != i, otherwise the loop breaks. And for outer loop, we are just iterating through the array. Therefore, we will do swap for each A[i] for at most 1 time. :)

RE: A simple recursive solution
You're right about point 1. Using DP will require additional structure for sure, like array. But the trees generated will take the same amount of memory no matter what algorithm we use. Array used in DP itself won't take two much space. However about point 2. If you are doing deep copy while using DP, then what's the point of using DP anyway? For any SubTree[start, end]. If you need a copy of it whenever you want to use it, then using DP is not benefiting you after all, IMHO.

RE: A simple recursive solution
Using DP causes two problems:
 It consumes lots of space, so possible running out of heap space for large n
 Using DP means you are reusing Subtree[start, end] solution. Which means if two unique BST both contains Subtree[3, 5], you are using the same saved subtree in two different BST. It is not a completely deep copy.

RE: Is this a cheating solution ??
This is clearly an average O(n) solution. Using binary search gives you O(log(n)) average solution with worst case O(n). (when whole array contains same number)

RE: In my opinion, the answer is O(log(m)+log(n)),not O(log(m+n))
You are completely right. In case anyone is curious, here is the mathematical proof :)
O(log(m) + log(n)) = O(log(mn)) <= O(log((m+n)^2/4)) <= O(log(m+n)^2) <= O(2*log(m+n)) = O(log(m+n))