Problem
Given the array orders
, which represents the orders that customers have done in a restaurant. More specifically
orders[i]=[customerNamei,tableNumberi,foodItemi]
where customerNamei
is the name of the customer, tableNumberi
is the table customer sit at, and
foodItemi
is the item customer orders.
Return the restaurant ’s “display table “. The “display table " is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is “Table”, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.
Examples
Example 1
|
|
Example 2
|
|
Example 3
|
|
Constraints
1 <= orders.length <= 5 * 10^4
orders[i].length == 3
1 <= customerNamei.length, foodItemi.length <= 20
customerNamei
andfoodItemi
consist of lowercase and uppercase English letters and the space character.tableNumberi
is a valid integer between1
and500
.
Solution
Method 1 – Table and Food Mapping with Sorting
Intuition
We need to count how many of each food item each table ordered, then display the table in the required format. This involves mapping table numbers to food counts and collecting all unique food items for the header.
Approach
- Use a set to collect all unique food items.
- Use a map to count, for each table, how many of each food item was ordered.
- Sort the food items alphabetically for the header.
- Sort the table numbers numerically for the rows.
- For each table, build a row with the table number and the counts of each food item in header order.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n + n * m)
, where n is the number of orders and m is the number of unique food items. - 🧺 Space complexity:
O(n * m)
, for storing the table and food counts.