LeetCode #1418 — MEDIUM

Display Table of Food Orders in a Restaurant

Move from brute-force thinking to an efficient approach using array strategy.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Hash Map · Segment Tree

Example 1

[["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]

Example 2

[["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]

Example 3

[["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]

Step 02

Core Insight

What unlocks the optimal approach

Keep the frequency of all pairs (tableNumber, foodItem) using a hashmap.
Sort rows by tableNumber and columns by foodItem, then process the resulted table.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1418: Display Table of Food Orders in a Restaurant
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;
    }
}

// Accepted solution for LeetCode #1418: Display Table of Food Orders in a Restaurant
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
}

# Accepted solution for LeetCode #1418: Display Table of Food Orders in a Restaurant
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

// Accepted solution for LeetCode #1418: Display Table of Food Orders in a Restaurant
struct Solution;
use std::collections::BTreeSet;
use std::collections::HashMap;

impl Solution {
    fn display_table(orders: Vec<Vec<String>>) -> Vec<Vec<String>> {
        let mut tables: BTreeSet<i32> = BTreeSet::new();
        let mut foods: BTreeSet<&str> = BTreeSet::new();
        let mut counts: HashMap<i32, HashMap<&str, usize>> = HashMap::new();
        for order in &orders {
            let table = order[1].parse::<i32>().unwrap();
            let food = &order[2];
            tables.insert(table);
            foods.insert(food);
            *counts.entry(table).or_default().entry(food).or_default() += 1;
        }
        let mut res = vec![vec!["Table".to_string()]];
        for food in foods.iter() {
            res[0].push((*food).to_string());
        }
        for table in tables {
            let mut row = vec![table.to_string()];
            for food in &foods {
                if let Some(counts) = counts.get(&table) {
                    if let Some(count) = counts.get(food) {
                        row.push(count.to_string());
                    } else {
                        row.push("0".to_string());
                    }
                } else {
                    row.push("0".to_string());
                }
            }
            res.push(row);
        }
        res
    }
}

#[test]
fn test() {
    let orders = vec_vec_string![
        ["David", "3", "Ceviche"],
        ["Corina", "10", "Beef Burrito"],
        ["David", "3", "Fried Chicken"],
        ["Carla", "5", "Water"],
        ["Carla", "5", "Ceviche"],
        ["Rous", "3", "Ceviche"]
    ];
    let res = vec_vec_string![
        ["Table", "Beef Burrito", "Ceviche", "Fried Chicken", "Water"],
        ["3", "0", "2", "1", "0"],
        ["5", "0", "1", "0", "1"],
        ["10", "1", "0", "0", "0"]
    ];
    assert_eq!(Solution::display_table(orders), res);
    let orders = vec_vec_string![
        ["James", "12", "Fried Chicken"],
        ["Ratesh", "12", "Fried Chicken"],
        ["Amadeus", "12", "Fried Chicken"],
        ["Adam", "1", "Canadian Waffles"],
        ["Brianna", "1", "Canadian Waffles"]
    ];
    let res = vec_vec_string![
        ["Table", "Canadian Waffles", "Fried Chicken"],
        ["1", "2", "0"],
        ["12", "0", "3"]
    ];
    assert_eq!(Solution::display_table(orders), res);
    let orders = vec_vec_string![
        ["Laura", "2", "Bean Burrito"],
        ["Jhon", "2", "Beef Burrito"],
        ["Melissa", "2", "Soda"]
    ];
    let res = vec_vec_string![
        ["Table", "Bean Burrito", "Beef Burrito", "Soda"],
        ["2", "1", "1", "1"]
    ];
    assert_eq!(Solution::display_table(orders), res);
}

// Accepted solution for LeetCode #1418: Display Table of Food Orders in a Restaurant
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;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n + m × log m + k × log k + m × k)

Space

O(n + m + k)

Approach Breakdown

BRUTE FORCE

O(n × q) time

O(1) space

For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.

SEGMENT TREE

O(n + q log n) time

O(n) space

Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.

Shortcut: Build O(n), query/update O(log n) each. When you need both range queries AND point updates.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.