LeetCode 1418 - Display Table of Food Orders in a Restaurant

The problem gives a list of restaurant orders. Each order contains three pieces of information: - Customer name - Table number - Food item An order looks like this: The goal is to build a display table that summarizes how many times each food item was ordered at every table.

leetcodemediumarrayhash-tablestringsortingordered-set

LeetCode Problem 1418

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting, Ordered Set

Solution

Problem Understanding

The problem gives a list of restaurant orders. Each order contains three pieces of information:

  • Customer name
  • Table number
  • Food item

An order looks like this:

[customerName, tableNumber, foodItem]

The goal is to build a display table that summarizes how many times each food item was ordered at every table.

The output format is important:

  • The first row is a header row.
  • The first column of the header is "Table".
  • The remaining columns are all unique food items sorted alphabetically.
  • Every remaining row represents one table.
  • The first value in each row is the table number.
  • The remaining values are counts of each food item ordered at that table.
  • Table rows must be sorted numerically by table number.

For example, if table 3 ordered "Ceviche" twice and "Fried Chicken" once, its row should contain:

["3", "2", "1"]

in the correct food-column order.

The customer names are irrelevant for the final result. They only appear in the input format.

The constraints are important:

  • There can be up to 5 * 10^4 orders.
  • Table numbers range from 1 to 500.
  • Food names are strings.

These constraints strongly suggest that we need an efficient counting solution. Repeated scanning of the entire order list for every table and food combination would be unnecessarily expensive.

There are several important edge cases:

  • Multiple customers at the same table may order the same item.
  • Food items may appear at only one table.
  • Some tables may order only one food item.
  • Table numbers are strings in the input, but sorting must be numerical, not lexicographical. For example, "10" must come after "5", not before "2".
  • The same customer may appear multiple times, but customer identity does not matter.

Approaches

Brute Force Approach

A brute force solution would first collect all unique tables and all unique food items. Then, for every table and every food item, we could scan the entire order list and count how many matching orders exist.

The process would look like this:

  1. Extract all unique food items and sort them.
  2. Extract all unique tables and sort them numerically.
  3. For every table:

  • For every food item:

  • Scan all orders and count matches.

This works because every count is computed directly from the input data. However, it is inefficient because the order list is repeatedly scanned many times.

If:

  • T is the number of tables,
  • F is the number of food items,
  • N is the number of orders,

then the counting phase alone costs O(T * F * N).

With up to 50,000 orders, this becomes unnecessarily expensive.

Optimal Approach

The key observation is that we only need to process each order once.

Instead of repeatedly scanning the input, we can build a frequency table while iterating through the orders.

We use:

  • A set to collect unique food items.

  • A nested hash map to store counts:

  • Outer map key = table number

  • Inner map key = food item

  • Value = count

Example structure:

table_orders = {
    "3": {
        "Ceviche": 2,
        "Fried Chicken": 1
    }
}

After processing all orders:

  1. Sort food items alphabetically.
  2. Sort table numbers numerically.
  3. Build the final display table using the stored counts.

This avoids repeated scanning and gives an efficient solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(T * F * N) O(T + F) Repeatedly scans all orders for every table-food pair
Optimal O(N + F log F + T log T + T * F) O(T * F + F) Uses hash maps to count orders in one pass

Algorithm Walkthrough

  1. Create a set to store all unique food items.

We need the food columns in alphabetical order. A set allows efficient collection of unique food names. 2. Create a nested hash map for table counts.

The outer map stores table numbers, and the inner map stores counts for each food item.

Example:

table_counts["3"]["Ceviche"] = 2
  1. Iterate through every order.

For each order:

  • Ignore the customer name.
  • Extract the table number and food item.
  • Add the food item to the food set.
  • Increment the count for that table and food item.
  1. Sort all food items alphabetically.

The problem explicitly requires food columns to appear in alphabetical order. 5. Sort table numbers numerically.

Since table numbers are stored as strings, we must convert them to integers during sorting. 6. Build the header row.

The header begins with "Table" followed by all sorted food items. 7. Build each table row.

For every sorted table:

  • Start the row with the table number.

  • For each food item:

  • Retrieve the count from the hash map.

  • Use 0 if the food was never ordered at that table.

  1. Return the completed display table.

Why it works

The algorithm processes every order exactly once and records the exact frequency of each food item for every table. Because all food names are globally collected and sorted, every row uses the same consistent column order. Sorting table numbers numerically guarantees the required row ordering. Since every count is directly accumulated from the input data, the final table accurately represents all restaurant orders.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        food_items = set()

        table_counts = defaultdict(lambda: defaultdict(int))

        for _, table_number, food_item in orders:
            food_items.add(food_item)
            table_counts[table_number][food_item] += 1

        sorted_foods = sorted(food_items)
        sorted_tables = sorted(table_counts.keys(), key=int)

        result = [["Table"] + sorted_foods]

        for table in sorted_tables:
            row = [table]

            for food in sorted_foods:
                row.append(str(table_counts[table].get(food, 0)))

            result.append(row)

        return result

The implementation begins by creating a set called food_items to store every distinct food name. This ensures uniqueness and later allows alphabetical sorting.

The table_counts structure uses nested defaultdict objects. The outer dictionary maps table numbers to another dictionary, while the inner dictionary stores food counts.

During the single traversal of orders, the code ignores the customer name because it is irrelevant to the output. Every food item is added to the set, and the appropriate count is incremented.

After processing all orders, the food items are sorted alphabetically. Table numbers are sorted numerically using key=int because they are stored as strings.

The result table is then constructed row by row. The header row contains "Table" followed by all sorted foods. Each table row appends the count for every food item, converting counts to strings because the output format requires strings.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func displayTable(orders [][]string) [][]string {
	foodSet := make(map[string]bool)
	tableCounts := make(map[string]map[string]int)

	for _, order := range orders {
		table := order[1]
		food := order[2]

		foodSet[food] = true

		if _, exists := tableCounts[table]; !exists {
			tableCounts[table] = make(map[string]int)
		}

		tableCounts[table][food]++
	}

	var foods []string
	for food := range foodSet {
		foods = append(foods, food)
	}

	sort.Strings(foods)

	var tables []string
	for table := range tableCounts {
		tables = append(tables, table)
	}

	sort.Slice(tables, func(i, j int) bool {
		a, _ := strconv.Atoi(tables[i])
		b, _ := strconv.Atoi(tables[j])
		return a < b
	})

	result := [][]string{}

	header := append([]string{"Table"}, foods...)
	result = append(result, header)

	for _, table := range tables {
		row := []string{table}

		for _, food := range foods {
			count := tableCounts[table][food]
			row = append(row, strconv.Itoa(count))
		}

		result = append(result, row)
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python solution.

A map[string]bool is used as a set for food items because Go does not provide a built in set type. Nested maps are used for storing table-food frequencies.

Go requires explicit slice construction and sorting. Table sorting uses sort.Slice with strconv.Atoi to ensure numerical ordering instead of lexicographical ordering.

Unlike Python's defaultdict, Go maps must be initialized manually before use. Therefore, the implementation checks whether a table already exists in the map before incrementing counts.

Worked Examples

Example 1

Input:

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

Step 1: Process Orders

Order food_items table_counts
["David","3","Ceviche"] {"Ceviche"} {"3": {"Ceviche": 1}}
["Corina","10","Beef Burrito"] {"Ceviche", "Beef Burrito"} {"3": {"Ceviche": 1}, "10": {"Beef Burrito": 1}}
["David","3","Fried Chicken"] add "Fried Chicken" {"3": {"Ceviche": 1, "Fried Chicken": 1}}
["Carla","5","Water"] add "Water" {"5": {"Water": 1}}
["Carla","5","Ceviche"] unchanged {"5": {"Water": 1, "Ceviche": 1}}
["Rous","3","Ceviche"] unchanged {"3": {"Ceviche": 2, "Fried Chicken": 1}}

Final structures:

food_items = {
    "Beef Burrito",
    "Ceviche",
    "Fried Chicken",
    "Water"
}

table_counts = {
    "3": {
        "Ceviche": 2,
        "Fried Chicken": 1
    },
    "5": {
        "Water": 1,
        "Ceviche": 1
    },
    "10": {
        "Beef Burrito": 1
    }
}

Step 2: Sort

sorted_foods = [
    "Beef Burrito",
    "Ceviche",
    "Fried Chicken",
    "Water"
]

sorted_tables = ["3", "5", "10"]

Step 3: Build Output

Header:

["Table", "Beef Burrito", "Ceviche", "Fried Chicken", "Water"]

Row for table 3:

["3", "0", "2", "1", "0"]

Row for table 5:

["5", "0", "1", "0", "1"]

Row for table 10:

["10", "1", "0", "0", "0"]

Final output:

[
    ["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],
    ["3","0","2","1","0"],
    ["5","0","1","0","1"],
    ["10","1","0","0","0"]
]

Example 2

Input:

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

After processing:

table_counts = {
    "12": {
        "Fried Chicken": 3
    },
    "1": {
        "Canadian Waffles": 2
    }
}

Sorted foods:

["Canadian Waffles", "Fried Chicken"]

Sorted tables:

["1", "12"]

Final output:

[
    ["Table","Canadian Waffles","Fried Chicken"],
    ["1","2","0"],
    ["12","0","3"]
]

Example 3

Input:

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

After processing:

table_counts = {
    "2": {
        "Bean Burrito": 1,
        "Beef Burrito": 1,
        "Soda": 1
    }
}

Final output:

[
    ["Table","Bean Burrito","Beef Burrito","Soda"],
    ["2","1","1","1"]
]

Complexity Analysis

Measure Complexity Explanation
Time O(N + F log F + T log T + T * F) One pass through orders, sorting foods and tables, then building the final matrix
Space O(T * F + F) Stores counts for table-food combinations and all unique food names

The dominant work comes from constructing the final table, which may require visiting every table-food combination. The algorithm is efficient because each order is processed only once, and all later operations work on compact aggregated data rather than rescanning the original input repeatedly.

Test Cases

from typing import List

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        from collections import defaultdict

        food_items = set()
        table_counts = defaultdict(lambda: defaultdict(int))

        for _, table_number, food_item in orders:
            food_items.add(food_item)
            table_counts[table_number][food_item] += 1

        sorted_foods = sorted(food_items)
        sorted_tables = sorted(table_counts.keys(), key=int)

        result = [["Table"] + sorted_foods]

        for table in sorted_tables:
            row = [table]

            for food in sorted_foods:
                row.append(str(table_counts[table].get(food, 0)))

            result.append(row)

        return result

solution = Solution()

# Example 1 from problem statement
assert solution.displayTable([
    ["David","3","Ceviche"],
    ["Corina","10","Beef Burrito"],
    ["David","3","Fried Chicken"],
    ["Carla","5","Water"],
    ["Carla","5","Ceviche"],
    ["Rous","3","Ceviche"]
]) == [
    ["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],
    ["3","0","2","1","0"],
    ["5","0","1","0","1"],
    ["10","1","0","0","0"]
]

# Example 2 from problem statement
assert solution.displayTable([
    ["James","12","Fried Chicken"],
    ["Ratesh","12","Fried Chicken"],
    ["Amadeus","12","Fried Chicken"],
    ["Adam","1","Canadian Waffles"],
    ["Brianna","1","Canadian Waffles"]
]) == [
    ["Table","Canadian Waffles","Fried Chicken"],
    ["1","2","0"],
    ["12","0","3"]
]

# Example 3 from problem statement
assert solution.displayTable([
    ["Laura","2","Bean Burrito"],
    ["Jhon","2","Beef Burrito"],
    ["Melissa","2","Soda"]
]) == [
    ["Table","Bean Burrito","Beef Burrito","Soda"],
    ["2","1","1","1"]
]

# Single order case
assert solution.displayTable([
    ["Alice","1","Pizza"]
]) == [
    ["Table","Pizza"],
    ["1","1"]
]

# Multiple identical orders at same table
assert solution.displayTable([
    ["A","2","Burger"],
    ["B","2","Burger"],
    ["C","2","Burger"]
]) == [
    ["Table","Burger"],
    ["2","3"]
]

# Numerical sorting of tables
assert solution.displayTable([
    ["A","10","Soup"],
    ["B","2","Soup"]
]) == [
    ["Table","Soup"],
    ["2","1"],
    ["10","1"]
]

# Multiple foods with alphabetical sorting
assert solution.displayTable([
    ["A","1","Water"],
    ["B","1","Apple Pie"],
    ["C","1","Burger"]
]) == [
    ["Table","Apple Pie","Burger","Water"],
    ["1","1","1","1"]
]

# Different tables ordering different foods
assert solution.displayTable([
    ["A","1","Tea"],
    ["B","2","Coffee"]
]) == [
    ["Table","Coffee","Tea"],
    ["1","0","1"],
    ["2","1","0"]
]
Test Why
Example 1 Validates general multi-table multi-food behavior
Example 2 Verifies repeated counting of the same food
Example 3 Tests a single table with multiple foods
Single order case Smallest valid input
Multiple identical orders Ensures counts accumulate correctly
Numerical sorting of tables Confirms numeric rather than lexicographic sorting
Alphabetical food sorting Verifies correct food column order
Different tables with different foods Ensures missing foods are represented as zero

Edge Cases

One important edge case is numerical table sorting. Since table numbers are provided as strings, a naive lexicographical sort would place "10" before "2". This would violate the problem requirements. The implementation explicitly sorts using integer conversion, ensuring correct numerical ordering.

Another important edge case occurs when a table never ordered a particular food item. If the implementation directly accesses missing keys without handling defaults, it could raise errors or produce incomplete rows. The solution safely uses .get(food, 0) in Python and relies on Go's zero value behavior for missing map entries.

A third important edge case is repeated orders of the same food at the same table. Multiple customers may order identical items, and the algorithm must accumulate counts correctly instead of overwriting them. The nested hash map structure increments counts for every occurrence, guaranteeing accurate totals.

A fourth edge case involves having only one table or only one food item. Some implementations accidentally assume multiple rows or columns exist. This solution dynamically constructs the table from the collected data, so it works correctly even for minimal inputs.