Summary
Solved problems list
- Kth Smallest Element in a Sorted Matrix
- All Nodes Distance K in Binary Tree
- Total Hamming Distance
- Binary Search Tree Iterator
- Binary Tree Level Order Traversal
- Maximum Length of Pair Chain
- Kth Largest Element in an Array
Several other things interrupted this week.
- Team building: CS like game
- It is really funny and we are tired. Besides everyone got a little drunk at the supper that night.
- Mid-autumn festival
Highlight
Total Hamming Distance
At the first sight, it seems that it is an easy problem. But a naive solution will take O(n^2) time
complexity. Recall that Single Number problem, which every number appears three times except one.
That problem needs some bit manipulations. This problem’s solution is similar.
In order to reduce the complexity, the distance in one bit is the number of zero multiplied by the
number of one.
Kth Largest Element in an Array
We can solve it by sorting the array and return size - K element. The time complexity is O(nlogn).
It is the complexity of the sorting operation.
The complexity can be reduced to O(n) using the method we use in quick sort, partition. After
each partition, we divide the array into three groups: elements less than the pivot, element equal to
the pivot, elements larger than the pivot. K can be reduced to a smaller number according to
this information.
Maximum Length of Pair Chain
Customized sort.
Kth Smallest Element in a Sorted Matrix
Be careful with the existing condition. It occurs to me that this problem is like merge K sorted
list. We use a prority_queue to track each row and pop the smallest element each time until K
reachs zero. This solution does not take advantage of the information: each column is sorted.