### 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.