# [Leetcode][406. Queue Reconstruction by Height] Pattern of Data Pairs Problem: Sorting First then Greedy

**By Long Luo**

This article is the solution Pattern of Data Pairs Problem: Sorting First then Greedy of Problem 406. Queue Reconstruction by Height.

# Intuition

The **Data Pair** $\textit{people}[h, k]$, $h_i$ represents the i-th person of height $h_i$, $k_i$ represents the other people in front who have a height greater than or equal to $h_i$.

**Pattern**:

When face such kind of problem with **Data Pair**, sorting first will simplify the problem.

Usually, we will sort the first element in **ascending order**, while the second element in **descending order**, or sort the first element in **descending order** with the second element in **ascending order**.

# Greedy

We sort the $\textit{people}$ pairs first by $height$ in descending order, and $k$ in ascending order.

According to the descending order of $height$, for each person, the number of people before him is the number of people whose height is greater than or equal to him.

According to the ascending order of $k$, because the $k$ is increase later, which can reduce the number of insert operations.

Take the example:

After sorting:

1 | [7,0], [7,1], [6,1], [5,0], [5,2], [4,4] |

Insert one by one:

1 | [7,0] |

The code is as follows:

1 | public int[][] reconstructQueue(int[][] people) { |

## Analysis

**Time Complexity**: $O(nlogn)$.**Space Complexity**: $O(logn)$.

All suggestions are welcome.

If you have any query or suggestion please comment below.

Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗