{x}
blog image

Display Table of Food Orders in a Restaurant

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.

Solution Explanation: Display Table of Food Orders in a Restaurant

This problem requires generating a formatted table summarizing food orders by table number. The solution involves several steps: data aggregation, sorting, and table construction.

Approach:

  1. Data Aggregation: We use a hash map (dictionary in Python, HashMap in Java, etc.) to store the food orders for each table. The keys of this map represent table numbers (converted to integers), and the values are maps (or dictionaries) themselves, where keys are food items, and values are their counts for that table. Simultaneously, we maintain a set to track all unique food items.

  2. Sorting: We sort the unique food items alphabetically to ensure consistent column order in the output table. We also sort the table numbers numerically to maintain order in the rows.

  3. Table Construction: The final output table is built row by row. The first row is the header, consisting of "Table" followed by the sorted food items. Subsequent rows represent individual tables, starting with the table number and then listing the count of each food item (in the same order as in the header). If a table didn't order a particular food item, a 0 is added.

Code Implementation (Python):

from collections import defaultdict, Counter
 
class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        tables = defaultdict(list)  # Table number -> list of food items
        items = set()  # Set to store unique food items
        for customer, table, item in orders:
            tables[int(table)].append(item)
            items.add(item)
 
        sorted_items = sorted(list(items))  # Sort food items alphabetically
        ans = [["Table"] + sorted_items]  # Header row
 
        for table in sorted(tables.keys()):  # Iterate through tables, sorted
            counts = Counter(tables[table])  # Count occurrences of each item
            row = [str(table)]
            for item in sorted_items:
                row.append(str(counts[item]))
            ans.append(row)
 
        return ans

Time Complexity Analysis:

  • Data Aggregation: O(N), where N is the number of orders. We iterate through the orders list once.
  • Sorting: O(M log M + K log K), where M is the number of unique food items and K is the number of unique table numbers. Sorting the food items and table numbers takes logarithmic time.
  • Table Construction: O(K * M), We iterate through each table (K) and then through each food item (M) to create the rows.

Overall Time Complexity: O(N + M log M + K log K + K * M). In most cases, K and M will be significantly smaller than N, so the overall complexity is effectively dominated by O(N).

Space Complexity Analysis:

  • tables: O(K * M) in the worst case (each table orders all food items).
  • items: O(M)
  • ans: O(K * M) to store the final table.

Therefore, the overall space complexity is O(K * M). Again, in practice, K and M are usually much smaller than N.

The solutions in other languages (Java, C++, Go, TypeScript) follow the same algorithmic approach, with variations only in the syntax and data structures used. The time and space complexity remain the same.