1418. Display Table of Food Orders in a Restaurant

MediumArrayHash TableStringOrdered SetSorting
Leetcode Link

Problem Description

The problem presents a scenario in which we're managing the orders in a restaurant. We have an array called orders, where each entry is a list with three elements: the name of the customer, the table number they're sitting at, and the food item they've ordered. Our task is to organize this data into a "display table".

The "display table" is effectively a two-dimensional array where each row represents a table in the restaurant, and each column represents a different food item. The top-left cell is labeled "Table", and the first row lists all the unique food items in alphabetical order, excluding this top-left cell. The first column lists the table numbers in ascending order. The rest of the cells in the table display the count of each food item ordered at each table.

The final output should not include customer names, and should be sorted by table number first, then by food item names alphabetically.

Intuition

To solve this problem, we must aggregate the orders for each table, and then count how many times each food item appears for each table.

Here's the step-by-step approach to do this:

  1. Identify Unique Elements: We need to collect all unique table numbers and food items. The table numbers will form the rows of our display table, and the food items will form the columns.

  2. Count Ordered Items: For each order, we count the number of times a food item is ordered per table. This is best done using a data structure like a dictionary or, in the case of Python, a Counter which is efficient for this kind of tallying.

  3. Initialize the Display Table: Create the display table's header by adding "Table" followed by the sorted list of unique food items. This becomes the first row of our final result.

  4. Populate the Display Table: Iterate through the sorted list of table numbers. For each table, create a new row starting with the table number. Then for each food item, add the count for that item at the current table. If the item hasn't been ordered at the table, the count is 0.

  5. Sort the Data: Ensure that the table numbers and food items are sorted before creating the display table. Table numbers should be sorted numerically and food items alphabetically.

This approach guarantees that the final data representation matches the required format: a table sorted by table number with each type of food item ordered listed in alphabetical order, showing the quantity ordered at each table.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Solution Approach

The solution utilizes Python's standard library to effectively manage and compute the required output. The process includes:

  1. Data Storage: Two Python set data structures are used to store unique table numbers (tables) and unique food items (foods) encountered in the list of orders. As sets, they will ignore any duplicate entries automatically.

  2. Counting with Counter: The Counter from the collections module in Python is a subclass of the dictionary specifically designed for counting hashable objects. It is used here to tally the occurrences of food item per table number. The key is designed as a string with the format 'table.food', concatenating the table number and food item with a delimiter.

  3. Sorting and Conversion to List: Once we have all unique table numbers and food items, these are sorted using Python's built-in sorted function. They are also converted to lists to prepare for iterating through them to produce the final display table format.

  4. Building the Display Table: The display table is initialized with its header — a list beginning with Table followed by the sorted list of food items. For every table number in the sorted tables list, a new row is created starting with the table number in string format. Subsequently, for each food item in the sorted foods list, the number of times the food item was ordered at the table is retrieved from the Counter and converted to a string before being appended to the current row.

  5. Constructing the Final Output: The final result (res) is a list of lists that mimics the tabular form. It starts with the header row and is followed by one row for each table displaying the counts for each food item.

The pattern followed here is straightforward:

  • Use sets to derive uniqueness.
  • Use Counter for efficient counting of items.
  • Convert and sort the sets to list data structures for ordered access.
  • Build the desired output in the format of a two-dimensional list, iterating through all table numbers and food items and using the tallies from the Counter.

This algorithm is effective as it breaks the problem down into simpler steps, each clearly executed with appropriate Python data structures and library functions. The use of the Counter particularly simplifies the problem of tracking and counting the number of food items per table number. The resulting implementation is clean, easy to understand, and performs the required task efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's consider a small set of orders given to us in the following format: [["David", "3", "Cesar Salad"], ["Alice", "3", "Chicken Sandwich"], ["Alice", "3", "Cesar Salad"], ["David", "2", "Pasta"]]. Here's how the solution approach will handle this data:

  1. Identify Unique Elements:

    • Unique table numbers: {"3", "2"}
    • Unique food items: {"Cesar Salad", "Chicken Sandwich", "Pasta"}

  2. Count Ordered Items:

    • We count each food item ordered at each table. For example, "Cesar Salad" is ordered twice at table "3". We use a Counter to track this, resulting in a dictionary that may look something like {"3.Cesar Salad": 2, "3.Chicken Sandwich": 1, "2.Pasta": 1}.

  3. Initialize the Display Table:

    • The header row is created as ["Table", "Cesar Salad", "Chicken Sandwich", "Pasta"], based on the sorted list of unique food items.

  4. Populate the Display Table:

    • Create a row for table "2": ["2", "0", "0", "1"] which means table "2" didn't order "Cesar Salad" or "Chicken Sandwich", but ordered "Pasta" once.
    • Create a row for table "3": ["3", "2", "1", "0"] indicating the counts of "Cesar Salad", "Chicken Sandwich", and "Pasta" respectively.

  5. Constructing the Final Output:

    • The resulting display table is: 
      1[ ["Table", "Cesar Salad", "Chicken Sandwich", "Pasta"], 
2  ["2", "0", "0", "1"], 
3  ["3", "2", "1", "0"] ]
    • This table is in the correct format, showing the counts of food items ordered at each table.

In summary, the example provided highlights the efficiency of the approach in organizing and presenting the data for a restaurant's order management system. Using Python's Counter, set, and sorting capabilities, we've transformed the list of orders into a display table that's easy to read and sorted accordingly.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
5        # Initialize sets for tables and food items to record unique items.
6        unique_tables = set()
7        unique_foods = set()
8      
9        # Use a Counter to keep track of the food orders per table.
10        food_order_count = Counter()
11      
12        # Iterate through each order and update sets and Counter.
13        for _, table_number, food_item in orders:
14            unique_tables.add(int(table_number))   # Convert table number to int for sorting.
15            unique_foods.add(food_item)            # Add the food item.
16            food_order_count[f'{table_number}.{food_item}'] += 1  # Increment count.
17      
18        # Sort the lists of unique food items and table numbers.
19        sorted_foods = sorted(list(unique_foods))
20        sorted_tables = sorted(list(unique_tables))
21      
22        # Prepare the result table header with 'Table' followed by the sorted food items.
23        result = [['Table'] + sorted_foods]
24      
25        # Populate the result table with counts per table.
26        for table in sorted_tables:
27            row = [str(table)]  # Start the row with the table number.
28            for food in sorted_foods:
29                # Append the string representation of the count of each food item for the table.
30                row.append(str(food_order_count[f'{table}.{food}']))
31            result.append(row)  # Add the completed row to the result.
32      
33        # Return the result table.
34        return result
35
1class Solution {
2
3    // This method will process a list of orders and display them as a table with food item counts.
4    public List<List<String>> displayTable(List<List<String>> orders) {
5        // Use TreeSet for automatic sorting
6        Set<Integer> tableNumbers = new TreeSet<>();
7        Set<String> menuItems = new TreeSet<>();
8
9        // This map holds the concatenation of table number and food item as a key, and their count as a value.
10        Map<String, Integer> itemCountMap = new HashMap<>();
11
12        // Processing each order to populate sets and the itemCountMap
13        for (List<String> order : orders) {
14            int table = Integer.parseInt(order.get(1));
15            String foodItem = order.get(2);
16
17            // Add the table number and food item to the respective sets
18            tableNumbers.add(table);
19            menuItems.add(foodItem);
20
21            // Create a unique key for each table-food pair
22            String key = table + "." + foodItem;
23            itemCountMap.put(key, itemCountMap.getOrDefault(key, 0) + 1);
24        }
25
26        // Prepare the result list, starting with the title row
27        List<List<String>> result = new ArrayList<>();
28        List<String> headers = new ArrayList<>();
29
30        // Adding "Table" as the first column header
31        headers.add("Table");
32        // Adding the rest of the food items as headers
33        headers.addAll(menuItems);
34        result.add(headers);
35
36        // Going through each table number and creating a row for the display table
37        for (int tableNumber : tableNumbers) {
38            List<String> row = new ArrayList<>();
39            // First column of the row is the table number
40            row.add(String.valueOf(tableNumber));
41            // The rest of the columns are the counts of each food item at this table
42            for (String menuItem : menuItems) {
43                // Forming the key to get the count from the map
44                String key = tableNumber + "." + menuItem;
45                // Adding the count to the row; if not present, add "0"
46                row.add(String.valueOf(itemCountMap.getOrDefault(key, 0)));
47            }
48            // Add the row to the result list
49            result.add(row);
50        }
51
52        // Return the fully formed display table
53        return result;
54    }
55}
56
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <unordered_map>
5#include <algorithm>
6
7// Definition for a solution class.
8class Solution {
9public:
10    // Function to display orders in a table format.
11    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
12      
13        // Use unordered sets to collect unique tables and food items.
14        unordered_set<int> tableNumbers;
15        unordered_set<string> foodItems;
16
17        // Use a map to keep count of orders for table and food combinations.
18        unordered_map<string, int> foodCount;
19
20        // Process orders to fill the collections.
21        for (const auto& order : orders) {
22            int tableNumber = stoi(order[1]);
23            const string& foodItem = order[2];
24
25            // Insert table numbers and food items to respective sets.
26            tableNumbers.insert(tableNumber);
27            foodItems.insert(foodItem);
28
29            // Increment count of the food item for a specific table.
30            ++foodCount[order[1] + "." + foodItem];
31        }
32
33        // Convert table number set to a sorted vector.
34        vector<int> sortedTables(tableNumbers.begin(), tableNumbers.end());
35        sort(sortedTables.begin(), sortedTables.end());
36
37        // Convert food items set to a sorted vector.
38        vector<string> sortedFoodItems(foodItems.begin(), foodItems.end());
39        sort(sortedFoodItems.begin(), sortedFoodItems.end());
40
41        // Prepare the result variable.
42        vector<vector<string>> result;
43
44        // Create title row with "Table" followed by sorted food items.
45        vector<string> titleRow {"Table"};
46        titleRow.insert(titleRow.end(), sortedFoodItems.begin(), sortedFoodItems.end());
47
48        // Add title row to the result.
49        result.push_back(titleRow);
50
51        // Loop over each table and create a row of counts per food item.
52        for (int table : sortedTables) {
53            vector<string> row;
54
55            // Add table number to the row.
56            row.push_back(to_string(table));
57
58            // Loop over each food item and add the count to the row.
59            for (const string& foodItem : sortedFoodItems) {
60                row.push_back(to_string(foodCount[to_string(table) + "." + foodItem]));
61            }
62
63            // Add the row to the result.
64            result.push_back(row);
65        }
66
67        // Return the filled result.
68        return result;
69    }
70};
71
1// Importing necessary collections from a library equivalent to C++ STL
2import { Vector, Set, Map } from 'typescript-collections';
3
4// Function to display orders in a table format.
5function displayTable(orders: Array<Array<string>>): Array<Array<string>> {
6  
7    // A set to collect unique tables and food item names.
8    const tableNumbers: Set<number> = new Set<number>();
9    const foodItems: Set<string> = new Set<string>();
10
11    // A map to keep count of the orders by table and food item
12    const foodCount: Map<string, number> = new Map<string, number>();
13
14    // Process each order to fill the sets and the map.
15    orders.forEach(order => {
16        const tableNumber: number = parseInt(order[1]);
17        const foodItem: string = order[2];
18
19        // Insert table numbers and food items into respective sets.
20        tableNumbers.add(tableNumber);
21        foodItems.add(foodItem);
22
23        // Construct a key to uniquely identify a table and food item combination.
24        const key: string = `${order[1]}.${foodItem}`;
25
26        // Increment the count for the food item at this table.
27        foodCount.set(key, (foodCount.getValue(key) || 0) + 1);
28    });
29
30    // Convert the table numbers and food items sets to sorted arrays.
31    const sortedTables: Array<number> = Array.from(tableNumbers).sort((a, b) => a - b);
32    const sortedFoodItems: Array<string> = Array.from(foodItems).sort();
33
34    // Prepare the result matrix to hold the data.
35    const result: Array<Array<string>> = [];
36
37    // Create the title row with "Table" followed by sorted food item names.
38    const titleRow: Array<string> = ['Table', ...sortedFoodItems];
39
40    // Add the title row to the result matrix.
41    result.push(titleRow);
42
43    // Create a row for each table with counts for each food item.
44    sortedTables.forEach(table => {
45        const row: Array<string> = [table.toString()];
46
47        // For each food item, retrieve the count and add it to the row.
48        sortedFoodItems.forEach(foodItem => {
49            const key: string = `${table}.${foodItem}`;
50            const count: number = foodCount.getValue(key) || 0;
51            row.push(count.toString());
52        });
53
54        // Add the completed row to the result matrix.
55        result.push(row);
56    });
57
58    // Return the completed result matrix.
59    return result;
60}
61
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into several parts:

  1. Iterating through the list of orders: This takes O(N) time, where N is the total number of orders.
  2. Adding items to and creating the foods and tables sets: Insertions take O(1) on average, so for N orders, the complexity is O(N).
  3. The Counter updates (mp[f'{table}.{food}'] += 1) also occur N times, and they take O(1) time each, thus O(N) in total.
  4. Sorting the foods list takes O(F log F) time, where F is the number of unique foods.
  5. Sorting the tables list takes O(T log T) time, where T is the number of unique tables.
  6. Building the res list involves a double loop which iterates T times outside and F times inside, leading to O(T * F).

Adding these up, the total time complexity is O(N) + O(N) + O(N) + O(F log F) + O(T log T) + O(T * F), which simplifies to O(N + F log F + T log T + T * F).

Space Complexity

The space complexity can also be dissected into:

  1. The tables and foods sets, which take O(T + F) space.
  2. The mp counter, which will store at most N key-value pairs, hence O(N) space.
  3. The res list, which contains a T+1 by F matrix, thus taking O(T * F) space.

Combining these, the overall space complexity is O(T + F + N + T * F). Since N can be at most T * F if every table orders every type of food once, the space complexity simplifies to O(T * F).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫