1418. Display Table of Food Orders in a Restaurant
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:
-
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.
-
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. -
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.
-
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.
-
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.
Solution Approach
The solution utilizes Python's standard library to effectively manage and compute the required output. The process includes:
-
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. -
Counting with Counter: The
Counter
from thecollections
module in Python is a subclass of the dictionary specifically designed for counting hashable objects. It is used here to tally the occurrences offood item
pertable number
. The key is designed as a string with the format'table.food'
, concatenating the table number and food item with a delimiter. -
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. -
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 sortedtables
list, a new row is created starting with the table number in string format. Subsequently, for each food item in the sortedfoods
list, the number of times the food item was ordered at the table is retrieved from theCounter
and converted to a string before being appended to the current row. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Identify Unique Elements:
- Unique table numbers:
{"3", "2"}
- Unique food items:
{"Cesar Salad", "Chicken Sandwich", "Pasta"}
- Unique table numbers:
-
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}
.
- We count each food item ordered at each table. For example, "Cesar Salad" is ordered twice at table "3". We use a
-
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.
- The header row is created as
-
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.
- Create a row for table "2":
-
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.
- The resulting display table is:
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
Time and Space Complexity
Time Complexity
The time complexity of the code can be broken down into several parts:
- Iterating through the list of orders: This takes
O(N)
time, whereN
is the total number of orders. - Adding items to and creating the
foods
andtables
sets: Insertions takeO(1)
on average, so forN
orders, the complexity isO(N)
. - The Counter updates (
mp[f'{table}.{food}'] += 1
) also occurN
times, and they takeO(1)
time each, thusO(N)
in total. - Sorting the
foods
list takesO(F log F)
time, whereF
is the number of unique foods. - Sorting the
tables
list takesO(T log T)
time, whereT
is the number of unique tables. - Building the
res
list involves a double loop which iteratesT
times outside andF
times inside, leading toO(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:
- The
tables
andfoods
sets, which takeO(T + F)
space. - The
mp
counter, which will store at mostN
key-value pairs, henceO(N)
space. - The
res
list, which contains aT+1
byF
matrix, thus takingO(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.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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