1418. Display Table of Food Orders in a Restaurant

Description

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerName_i,tableNumber_i,foodItem_i] where customerName_i is the name of the customer, tableNumber_i is the table customer sit at, and foodItem_i 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 <= customerName_i.length, foodItem_i.length <= 20
customerName_i and foodItem_i consist of lowercase and uppercase English letters and the space character.
tableNumber_i is a valid integer between 1 and 500.

Solutions

Solution 1: Hash Table + Sorting

We can use a hash table $\textit{tables}$ to store the dishes ordered at each table, and a set $\textit{items}$ to store all the dishes.

Traverse $\textit{orders}$, storing the dishes ordered at each table in $\textit{tables}$ and $\textit{items}$.

Then we sort $\textit{items}$ to get $\textit{sortedItems}$.

Next, we construct the answer array $\textit{ans}$. First, add the header row $\textit{header}$ to $\textit{ans}$. Then, traverse the sorted $\textit{tables}$. For each table, use a counter $\textit{cnt}$ to count the number of each dish, then construct a row $\textit{row}$ and add it to $\textit{ans}$.

Finally, return $\textit{ans}$.

The time complexity is $O(n + m \times \log m + k \times \log k + m \times k)$, and the space complexity is $O(n + m + k)$. Here, $n$ is the length of the array $\textit{orders}$, while $m$ and $k$ represent the number of dish types and the number of tables, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        tables = defaultdict(list)
        items = set()
        for _, table, foodItem in orders:
            tables[int(table)].append(foodItem)
            items.add(foodItem)
        sorted_items = sorted(items)
        ans = [["Table"] + sorted_items]
        for table in sorted(tables):
            cnt = Counter(tables[table])
            row = [str(table)] + [str(cnt[item]) for item in sorted_items]
            ans.append(row)
        return ans

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        TreeMap<Integer, List<String>> tables = new TreeMap<>();
        Set<String> items = new HashSet<>();
        for (List<String> o : orders) {
            int table = Integer.parseInt(o.get(1));
            String foodItem = o.get(2);
            tables.computeIfAbsent(table, k -> new ArrayList<>()).add(foodItem);
            items.add(foodItem);
        }
        List<String> sortedItems = new ArrayList<>(items);
        Collections.sort(sortedItems);
        List<List<String>> ans = new ArrayList<>();
        List<String> header = new ArrayList<>();
        header.add("Table");
        header.addAll(sortedItems);
        ans.add(header);
        for (Map.Entry<Integer, List<String>> entry : tables.entrySet()) {
            Map<String, Integer> cnt = new HashMap<>();
            for (String item : entry.getValue()) {
                cnt.merge(item, 1, Integer::sum);
            }
            List<String> row = new ArrayList<>();
            row.add(String.valueOf(entry.getKey()));
            for (String item : sortedItems) {
                row.add(String.valueOf(cnt.getOrDefault(item, 0)));
            }
            ans.add(row);
        }
        return ans;
    }
}

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        map<int, vector<string>> tables;
        set<string> sortedItems;
        for (auto& o : orders) {
            int table = stoi(o[1]);
            string foodItem = o[2];
            tables[table].push_back(foodItem);
            sortedItems.insert(foodItem);
        }
        vector<vector<string>> ans;
        vector<string> header = {"Table"};
        header.insert(header.end(), sortedItems.begin(), sortedItems.end());
        ans.push_back(header);
        for (auto& [table, items] : tables) {
            unordered_map<string, int> cnt;
            for (string& item : items) {
                cnt[item]++;
            }
            vector<string> row;
            row.push_back(to_string(table));
            for (const string& item : sortedItems) {
                row.push_back(to_string(cnt[item]));
            }
            ans.push_back(row);
        }
        return ans;
    }
};

func displayTable(orders [][]string) [][]string {
    tables := make(map[int]map[string]int)
    items := make(map[string]bool)
    for _, order := range orders {
        table, _ := strconv.Atoi(order[1])
        foodItem := order[2]
        if tables[table] == nil {
            tables[table] = make(map[string]int)
        }
        tables[table][foodItem]++
        items[foodItem] = true
    }
    sortedItems := make([]string, 0, len(items))
    for item := range items {
        sortedItems = append(sortedItems, item)
    }
    sort.Strings(sortedItems)
    ans := [][]string{}
    header := append([]string{"Table"}, sortedItems...)
    ans = append(ans, header)
    tableNums := make([]int, 0, len(tables))
    for table := range tables {
        tableNums = append(tableNums, table)
    }
    sort.Ints(tableNums)
    for _, table := range tableNums {
        row := []string{strconv.Itoa(table)}
        for _, item := range sortedItems {
            count := tables[table][item]
            row = append(row, strconv.Itoa(count))
        }
        ans = append(ans, row)
    }
    return ans
}

function displayTable(orders: string[][]): string[][] {
    const tables: Record<number, Record<string, number>> = {};
    const items: Set<string> = new Set();
    for (const [_, table, foodItem] of orders) {
        const t = +table;
        if (!tables[t]) {
            tables[t] = {};
        }
        if (!tables[t][foodItem]) {
            tables[t][foodItem] = 0;
        }
        tables[t][foodItem]++;
        items.add(foodItem);
    }
    const sortedItems = Array.from(items).sort();
    const ans: string[][] = [];
    const header: string[] = ['Table', ...sortedItems];
    ans.push(header);
    const sortedTableNumbers = Object.keys(tables)
        .map(Number)
        .sort((a, b) => a - b);
    for (const table of sortedTableNumbers) {
        const row: string[] = [table.toString()];
        for (const item of sortedItems) {
            row.push((tables[table][item] || 0).toString());
        }
        ans.push(row);
    }
    return ans;
}

1418. Display Table of Food Orders in a Restaurant

Description

Solutions

Solution 1: Hash Table + Sorting

Comments