# Display Table of Food Orders in a Restaurant **Difficulty:** MEDIUM [External](https://leetcode.com/problems/display-table-of-food-orders-in-a-restaurant) Canonical: https://scaleengineer.com/dsa/problems/display-table-of-food-orders-in-a-restaurant **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table, String, Ordered Set **Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Nordstrom](https://scaleengineer.com/companies/nordstrom) --- ## 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. **Example 1:** **Input:** orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]] **Output:** [["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] **Explanation:** The displaying table looks like: **Table,Beef Burrito,Ceviche,Fried Chicken,Water** 3 ,0 ,2 ,1 ,0 5 ,0 ,1 ,0 ,1 10 ,1 ,0 ,0 ,0 For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche". For the table 5: Carla orders "Water" and "Ceviche". For the table 10: Corina orders "Beef Burrito". **Example 2:** **Input:** orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]] **Output:** [["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] **Explanation:** For the table 1: Adam and Brianna order "Canadian Waffles". For the table 12: James, Ratesh and Amadeus order "Fried Chicken". **Example 3:** **Input:** orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]] **Output:** [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]] **Constraints:** * `1 <= orders.length <= 5 * 10^4` * `orders[i].length == 3` * `1 <= customerNamei.length, foodItemi.length <= 20` * `customerNamei` and `foodItemi` consist of lowercase and uppercase English letters and the space character. * `tableNumberi `is a valid integer between `1` and `500`. # Approaches ## Brute-Force with Multiple Passes and Linear Scans This approach involves multiple iterations over the input data. First, it collects all unique food items and table numbers. Then, it sorts them to establish the structure of the output table. Finally, it iterates through the orders again to populate the counts, using inefficient linear searches to find the correct row and column for each order. **Time:** O(N * (T + U)), where N is the number of orders, T is the number of unique tables, and U is the number of unique food items. The final pass to populate counts dominates, as each of the N orders requires searching through T tables and U food items. · **Space:** O(T * U + U*L_f + T*L_t), where T is the number of unique tables, U is the number of unique food items, and L_f/L_t are average string lengths. The dominant term is `O(T * U)` for storing the result table. **Pros:** Conceptually simple and breaks the problem down into easy-to-understand steps. **Cons:** Highly inefficient due to multiple passes over the data.; The final step of populating counts involves linear searches within a loop, leading to a poor time complexity of `O(N * (T + U))`, which will likely result in a 'Time Limit Exceeded' error for large inputs. ### Explanation The brute-force method tackles the problem in a straightforward but inefficient manner. It separates the problem into distinct phases: data collection, sorting, table initialization, and data population. The main drawback is the final population step. For every single order in the input, it searches for the correct table row and food column by scanning through the previously created lists of sorted tables and foods. This repeated searching process makes the algorithm very slow as the number of orders, tables, or food items increases. ```java import java.util.*; import java.util.stream.Collectors; class Solution { public List> displayTable(List> orders) { // Step 1: Collect unique food items and table numbers Set foodSet = new HashSet<>(); Set tableSet = new HashSet<>(); for (List order : orders) { tableSet.add(order.get(1)); foodSet.add(order.get(2)); } // Step 2: Sort headers and rows List foodHeader = new ArrayList<>(foodSet); Collections.sort(foodHeader); List sortedTables = new ArrayList<>(tableSet); Collections.sort(sortedTables, Comparator.comparingInt(Integer::parseInt)); // Step 3: Initialize result table List> displayTable = new ArrayList<>(); List headerRow = new ArrayList<>(); headerRow.add("Table"); headerRow.addAll(foodHeader); displayTable.add(headerRow); for (String table : sortedTables) { List row = new ArrayList<>(Collections.nCopies(foodHeader.size() + 1, "0")); row.set(0, table); displayTable.add(row); } // Step 4: Populate counts with linear scans (inefficient) for (List order : orders) { String table = order.get(1); String food = order.get(2); int rowIndex = sortedTables.indexOf(table) + 1; // Linear scan int colIndex = foodHeader.indexOf(food) + 1; // Linear scan List targetRow = displayTable.get(rowIndex); int currentCount = Integer.parseInt(targetRow.get(colIndex)); targetRow.set(colIndex, String.valueOf(currentCount + 1)); } return displayTable; } } ``` ### Algorithm - **Step 1: Collect Unique Items:** - Create a `HashSet` for food items and another `HashSet` for table numbers. - Iterate through the `orders` list once to populate both sets with all unique values. - **Step 2: Sort Headers and Rows:** - Convert the food item set to a `List` and sort it alphabetically. This list will form the column headers. - Convert the table number set to a `List`, parse the string numbers to integers, sort them numerically, and store the sorted list. - **Step 3: Initialize Result Table:** - Create the final result `List>`. - Add the header row, which consists of "Table" followed by the sorted food items. - For each sorted table number, add a new row to the result. This row will start with the table number, followed by "0" for each food item count. - **Step 4: Populate Counts:** - Iterate through the original `orders` list a second time. - For each `order`, find its corresponding row and column in the result table by performing a linear search on the sorted table list and sorted food list. - Once the correct cell is located, parse its string value to an integer, increment it, and update the cell with the new count as a string. - **Step 5: Return Result:** - Return the fully populated table. ## Single Pass Data Aggregation using Sorted Maps This approach improves upon the brute-force method by using data structures that automatically maintain sorted order, namely `TreeMap` and `TreeSet`. It processes all orders in a single pass to aggregate the data, and then directly constructs the final table from these sorted structures. This avoids both multiple passes and expensive manual sorting steps after data collection. **Time:** O(N * (log T + log U) + T * U). The first term comes from iterating through N orders and performing insertions into a `TreeMap` (O(log T)) and a `TreeSet` (O(log U)). The second term comes from building the final `T x U` table. · **Space:** O(N + T * U + U*L_f), where N is the number of orders, T is unique tables, U is unique foods, and L_f is food name length. `O(N)` for the map storing counts (at most N unique table-food pairs), `O(U*L_f)` for the food set, and `O(T*U)` for the final result table. **Pros:** Aggregates data in a single pass.; Simplifies the code by using data structures that handle sorting implicitly.; Avoids expensive re-sorting or searching after the initial data pass. **Cons:** The logarithmic factor on every insertion during the main loop (`O(N * (log T + log U))`) can be slower than a simple `O(N)` pass followed by explicit sorting, especially when N is large. ### Explanation By leveraging `TreeSet` and `TreeMap`, this method integrates the sorting process into the data aggregation phase. A `TreeSet` is used to collect all unique food items, and because it's a balanced binary search tree, it keeps the items in alphabetical order. Similarly, a `TreeMap` is used to store the food counts for each table. By using the integer representation of the table number as the key, the `TreeMap` automatically keeps the table entries sorted numerically. After a single pass through all the orders, the food items and table numbers are already collected and sorted. The final step is to simply iterate through these sorted structures to build the display table. ```java import java.util.*; class Solution { public List> displayTable(List> orders) { // Use TreeSet to keep food items sorted alphabetically Set foodSet = new TreeSet<>(); // Use TreeMap to keep tables sorted numerically // Key: Table number (Integer), Value: Map of food items to their counts Map> tableOrders = new TreeMap<>(); for (List order : orders) { int tableNumber = Integer.parseInt(order.get(1)); String foodItem = order.get(2); foodSet.add(foodItem); tableOrders.computeIfAbsent(tableNumber, k -> new HashMap<>()).merge(foodItem, 1, Integer::sum); } // Prepare the header row List header = new ArrayList<>(); header.add("Table"); header.addAll(foodSet); // Prepare the result list List> displayTable = new ArrayList<>(); displayTable.add(header); // Populate the data rows from the sorted TreeMap for (Map.Entry> entry : tableOrders.entrySet()) { Integer tableNumber = entry.getKey(); Map foodCounts = entry.getValue(); List row = new ArrayList<>(); row.add(String.valueOf(tableNumber)); for (String food : foodSet) { row.add(String.valueOf(foodCounts.getOrDefault(food, 0))); } displayTable.add(row); } return displayTable; } } ``` ### Algorithm - **Step 1: Initialize Sorted Data Structures:** - Initialize a `TreeSet` to store unique food items. The `TreeSet` will automatically keep them sorted alphabetically. - Initialize a `TreeMap>` to store the counts. The `TreeMap` will keep table numbers (parsed to `Integer`) sorted numerically. - **Step 2: Aggregate Data:** - Iterate through the `orders` list once. For each order `[name, table, food]`: - Add the `food` to the `TreeSet`. - Parse the `table` string to an integer. - Use `computeIfAbsent` on the `TreeMap` to get or create the inner `Map` for the table. - Increment the count for the `food` in the inner `Map`. - **Step 3: Construct the Output Table:** - Create the header row: start with "Table", then add all items from the `TreeSet` (which are already sorted). - Add the header to the result list. - Iterate through the entries of the `TreeMap`. Since it's a `TreeMap`, the tables are already sorted by number. - For each `(tableNumber, foodCounts)` entry, create a new row. - Start the row with the `tableNumber` (converted back to a string). - Iterate through the sorted food items from the `TreeSet`. For each food item, get its count from the `foodCounts` map (or 0 if not present) and add it to the row. - Add the completed row to the result list. - **Step 4: Return Result:** - Return the final list. ## Optimized Single Pass with HashMaps and Explicit Sorting This is the most efficient approach. It uses `HashMap` and `HashSet` for fast `O(1)` average time data aggregation in a single pass. After collecting all the necessary data, it performs sorting on the much smaller sets of unique table numbers and food items just once. This separation of concerns—fast aggregation followed by efficient sorting—yields the best overall performance. **Time:** O(N + U log U + T log T + T * U). `O(N)` for the initial pass. `O(U log U)` to sort food items. `O(T log T)` to sort table numbers. `O(T * U)` to build the final table. This is generally faster than other approaches because the expensive `log` operations are not performed inside the main `N`-sized loop. · **Space:** O(N + T * U + U*L_f), where N is the number of orders, T is unique tables, U is unique foods, and L_f is food name length. `O(N)` for the map storing counts, `O(U*L_f)` for the food set, and `O(T*U)` for the final result table. **Pros:** Fastest approach due to `O(1)` average time for data aggregation.; Efficiently separates the `O(N)` data processing from the sorting of smaller, unique sets of items (`T` and `U`).; Scales best with a large number of orders (`N`). **Cons:** Requires explicit sorting steps after the aggregation phase, which can add a small amount of code complexity compared to the `TreeMap`/`TreeSet` approach. ### Explanation This optimized approach prioritizes speed during the most intensive part of the algorithm: processing the initial list of `N` orders. By using `HashMap` and `HashSet`, each order can be processed in average constant time, `O(1)`. The entire aggregation phase completes in `O(N)` time. Only after this fast pass are the sorting operations performed. Since the number of unique tables (`T`) and unique food items (`U`) is typically much smaller than the total number of orders (`N`), sorting these smaller collections (`O(T log T)` and `O(U log U)`) is significantly more efficient than incurring a logarithmic cost for every one of the `N` orders, as seen in the `TreeMap` approach. This makes it the best-performing solution in practice. ```java import java.util.*; import java.util.stream.Collectors; class Solution { public List> displayTable(List> orders) { // Step 1 & 2: Use HashMap/HashSet for fast O(1) aggregation Set foodSet = new HashSet<>(); Map> tableOrders = new HashMap<>(); for (List order : orders) { String tableNumber = order.get(1); String foodItem = order.get(2); foodSet.add(foodItem); tableOrders.computeIfAbsent(tableNumber, k -> new HashMap<>()).merge(foodItem, 1, Integer::sum); } // Step 3: Sort the collected unique items List sortedFood = new ArrayList<>(foodSet); Collections.sort(sortedFood); List sortedTables = tableOrders.keySet().stream() .map(Integer::parseInt) .sorted() .collect(Collectors.toList()); // Step 4: Construct the final table List header = new ArrayList<>(); header.add("Table"); header.addAll(sortedFood); List> displayTable = new ArrayList<>(); displayTable.add(header); for (Integer tableNum : sortedTables) { String tableNumStr = String.valueOf(tableNum); List row = new ArrayList<>(); row.add(tableNumStr); Map foodCounts = tableOrders.get(tableNumStr); for (String food : sortedFood) { row.add(String.valueOf(foodCounts.getOrDefault(food, 0))); } displayTable.add(row); } return displayTable; } } ``` ### Algorithm - **Step 1: Initialize Hash-Based Data Structures:** - Initialize a `HashSet` to store unique food items. - Initialize a `HashMap>` to store the counts per table. - **Step 2: Aggregate Data:** - Iterate through the `orders` list once. This pass is very fast, with an average time complexity of `O(N)`. - For each order `[name, table, food]`: - Add the `food` to the `HashSet`. - Use `computeIfAbsent` on the outer `HashMap` to get or create an inner `HashMap` for the `table`. - Increment the count for the `food` in the inner map. - **Step 3: Sort Keys:** - After the loop, create a `List` of food items from the `HashSet` and sort it alphabetically. - Create a `List` of table numbers from the `HashMap`'s key set. Convert the strings to integers, sort them numerically, and store the result. - **Step 4: Construct Final Table:** - Create the header row using "Table" and the sorted food item list. - Add the header to the result list. - Iterate through the sorted list of table numbers. For each table number: - Create a new row, starting with the table number (as a string). - Iterate through the sorted list of food items. For each food, retrieve its count from the map for the current table (defaulting to 0 if absent). - Add the count as a string to the row. - Add the completed row to the result. - **Step 5: Return Result:** - Return the final list. # Solutions ### Java ```java class Solution { public List> displayTable(List> orders) { Set tables = new HashSet<>(); Set foods = new HashSet<>(); Map mp = new HashMap<>(); for (List order : orders) { int table = Integer.parseInt(order.get(1)); String food = order.get(2); tables.add(table); foods.add(food); String key = table + "." + food; mp.put(key, mp.getOrDefault(key, 0) + 1); } List t = new ArrayList<>(tables); List f = new ArrayList<>(foods); Collections.sort(t); Collections.sort(f); List> res = new ArrayList<>(); List title = new ArrayList<>(); title.add("Table"); title.addAll(f); res.add(title); for (int table : t) { List tmp = new ArrayList<>(); tmp.add(String.valueOf(table)); for (String food : f) { tmp.add(String.valueOf(mp.getOrDefault(table + "." + food, 0))); } res.add(tmp); } return res; } } ``` ### Python ```python class Solution: def displayTable(self, orders: List[List[str]]) -> List[List[str]]: tables = set() foods = set() mp = Counter() for _, table, food in orders: tables . add(int(table)) foods . add(food) mp[f ' { table } . { food } '] += 1 foods = sorted(list(foods)) tables = sorted(list(tables)) res = [['Table'] + foods] for table in tables: t = [str(table)] for food in foods: t . append(str(mp[f ' { table } . { food } '])) res . append(t) return res ``` ### CPP ```cpp class Solution { public: vector> displayTable(vector> &orders) { unordered_set tables; unordered_set foods; unordered_map mp; for (auto &order : orders) { int table = stoi(order[1]); string food = order[2]; tables.insert(table); foods.insert(food); ++mp[order[1] + "." + food]; } vector t; t.assign(tables.begin(), tables.end()); sort(t.begin(), t.end()); vector f; f.assign(foods.begin(), foods.end()); sort(f.begin(), f.end()); vector> res; vector title; title.push_back("Table"); for (auto e : f) title.push_back(e); res.push_back(title); for (int table : t) { vector tmp; tmp.push_back(to_string(table)); for (string food : f) { tmp.push_back(to_string(mp[to_string(table) + "." + food])); } res.push_back(tmp); } return res; } }; ```