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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5

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

1
2

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

Method 1 – Table and Food Mapping with Sorting

Intuition

We need to count how many of each food item each table ordered, then display the table in the required format. This involves mapping table numbers to food counts and collecting all unique food items for the header.

Approach

  1. Use a set to collect all unique food items.
  2. Use a map to count, for each table, how many of each food item was ordered.
  3. Sort the food items alphabetically for the header.
  4. Sort the table numbers numerically for the rows.
  5. For each table, build a row with the table number and the counts of each food item in header order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        set<string> foods;
        map<int, map<string, int>> table;
        for (auto& o : orders) {
            int t = stoi(o[1]);
            string f = o[2];
            foods.insert(f);
            table[t][f]++;
        }
        vector<string> header = {"Table"};
        header.insert(header.end(), foods.begin(), foods.end());
        vector<vector<string>> ans;
        ans.push_back(header);
        for (auto& [t, cnt] : table) {
            vector<string> row = {to_string(t)};
            for (int i = 1; i < header.size(); ++i) {
                row.push_back(to_string(cnt[header[i]]));
            }
            ans.push_back(row);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import "sort"
func displayTable(orders [][]string) [][]string {
    foodSet := map[string]struct{}{}
    table := map[int]map[string]int{}
    for _, o := range orders {
        t := 0
        for _, c := range o[1] { t = t*10 + int(c-'0') }
        f := o[2]
        foodSet[f] = struct{}{}
        if table[t] == nil { table[t] = map[string]int{} }
        table[t][f]++
    }
    foods := []string{}
    for f := range foodSet { foods = append(foods, f) }
    sort.Strings(foods)
    header := append([]string{"Table"}, foods...)
    ans := [][]string{header}
    tables := []int{}
    for t := range table { tables = append(tables, t) }
    sort.Ints(tables)
    for _, t := range tables {
        row := []string{fmt.Sprintf("%d", t)}
        for _, f := range foods {
            row = append(row, fmt.Sprintf("%d", table[t][f]))
        }
        ans = append(ans, row)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        Set<String> foods = new TreeSet<>();
        Map<Integer, Map<String, Integer>> table = new TreeMap<>();
        for (List<String> o : orders) {
            int t = Integer.parseInt(o.get(1));
            String f = o.get(2);
            foods.add(f);
            table.computeIfAbsent(t, k -> new HashMap<>()).merge(f, 1, Integer::sum);
        }
        List<String> header = new ArrayList<>();
        header.add("Table");
        header.addAll(foods);
        List<List<String>> ans = new ArrayList<>();
        ans.add(header);
        for (int t : table.keySet()) {
            List<String> row = new ArrayList<>();
            row.add(String.valueOf(t));
            for (int i = 1; i < header.size(); ++i) {
                row.add(String.valueOf(table.get(t).getOrDefault(header.get(i), 0)));
            }
            ans.add(row);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun displayTable(orders: List<List<String>>): List<List<String>> {
        val foods = sortedSetOf<String>()
        val table = sortedMapOf<Int, MutableMap<String, Int>>()
        for (o in orders) {
            val t = o[1].toInt()
            val f = o[2]
            foods.add(f)
            table.getOrPut(t) { mutableMapOf() }[f] = table.getOrPut(t) { mutableMapOf() }[f]?.plus(1) ?: 1
        }
        val header = listOf("Table") + foods
        val ans = mutableListOf<List<String>>()
        ans.add(header)
        for ((t, cnt) in table) {
            val row = mutableListOf(t.toString())
            for (f in foods) row.add(cnt[f]?.toString() ?: "0")
            ans.add(row)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def displayTable(self, orders: list[list[str]]) -> list[list[str]]:
        foods = set()
        table = {}
        for _, t, f in orders:
            t = int(t)
            foods.add(f)
            if t not in table:
                table[t] = {}
            table[t][f] = table[t].get(f, 0) + 1
        foods = sorted(foods)
        header = ["Table"] + foods
        ans = [header]
        for t in sorted(table):
            row = [str(t)] + [str(table[t].get(f, 0)) for f in foods]
            ans.append(row)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn display_table(orders: Vec<Vec<String>>) -> Vec<Vec<String>> {
        use std::collections::{BTreeSet, BTreeMap};
        let mut foods = BTreeSet::new();
        let mut table: BTreeMap<i32, BTreeMap<String, i32>> = BTreeMap::new();
        for o in &orders {
            let t = o[1].parse::<i32>().unwrap();
            let f = o[2].clone();
            foods.insert(f.clone());
            table.entry(t).or_default().entry(f).and_modify(|c| *c += 1).or_insert(1);
        }
        let mut header = vec!["Table".to_string()];
        header.extend(foods.iter().cloned());
        let mut ans = vec![header.clone()];
        for (t, cnt) in table.iter() {
            let mut row = vec![t.to_string()];
            for f in foods.iter() {
                row.push(cnt.get(f).unwrap_or(&0).to_string());
            }
            ans.push(row);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    displayTable(orders: string[][]): string[][] {
        const foods = new Set<string>();
        const table = new Map<number, Map<string, number>>();
        for (const [, t, f] of orders) {
            const tn = Number(t);
            foods.add(f);
            if (!table.has(tn)) table.set(tn, new Map());
            table.get(tn)!.set(f, (table.get(tn)!.get(f) ?? 0) + 1);
        }
        const foodList = Array.from(foods).sort();
        const header = ["Table", ...foodList];
        const ans: string[][] = [header];
        for (const t of Array.from(table.keys()).sort((a, b) => a - b)) {
            const row = [t.toString(), ...foodList.map(f => (table.get(t)!.get(f) ?? 0).toString())];
            ans.push(row);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + n * m), where n is the number of orders and m is the number of unique food items.
  • 🧺 Space complexity: O(n * m), for storing the table and food counts.