Problem Description

You are given a list of orders in a restaurant. Each order is represented as a list of three strings: [customerName, tableNumber, foodItem]. The goal is to display a "display table" of food orders for the restaurant in a specific format:

• The first row is a header row with "Table" followed by the names of all food items, in lexicographical (alphabetical) order.
• Each subsequent row corresponds to a table number (as a string), sorted numerically. For each food item, display the number of times it was ordered at that table.
• Each cell contains a string representation of the count (even if it's zero).

Constraints:

• Each order is valid and refers to an existing table and food item.
• Food items and table numbers are strings, but table numbers should be sorted numerically.
• Do not reuse elements; counts must be accurate per table and food item.

Thought Process

At first glance, the problem can be approached by iterating over the list of orders and counting how many times each food item is ordered at each table. A brute-force solution might involve scanning the entire list for every table and food item combination, but this would be inefficient.

Instead, we can optimize by:

• Collecting all unique food items and table numbers as we process the orders.
• Using a mapping (like a dictionary or hash map) to count food orders per table efficiently.
• Sorting food items lexicographically and tables numerically at the end for correct display order.

The key is to build a structure that allows quick lookups and updates for each table and food item combination, rather than repeatedly scanning the orders.

Solution Approach

Let’s break down the solution step by step:

1. Collect Unique Food Items and Table Numbers:
   • Iterate through each order.
   • Add food items to a set (to ensure uniqueness).
   • Add table numbers to a set (also for uniqueness).
2. Count Orders Per Table and Food Item:
   • Use a nested map or dictionary: the outer key is the table number, the inner key is the food item, and the value is the count.
   • For each order, increment the count for the corresponding table and food item.
3. Sort Food Items and Table Numbers:
   • Sort food items alphabetically (lexicographically).
   • Sort table numbers numerically (convert to int for sorting, but display as strings).
4. Build the Display Table:
   • First row: "Table" followed by sorted food items.
   • For each sorted table, build a row: first the table number, then the counts of each food item (as strings), defaulting to "0" if not ordered.
5. Return the Result:
   • Return the constructed table as a list of lists (or the appropriate structure in your language).

We use sets for uniqueness and dictionaries (hash maps) for efficient counting and lookup, ensuring the solution is both clean and efficient.

Example Walkthrough

Sample Input:

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

Step-by-step:

1. Collect food items: {"Ceviche", "Beef Burrito", "Fried Chicken", "Water"}
2. Collect table numbers: {"3", "5", "10"}
3. Count per table:
   • Table 3: "Ceviche" x2, "Fried Chicken" x1
   • Table 5: "Ceviche" x1, "Water" x1
   • Table 10: "Beef Burrito" x1
4. Sort food items: ["Beef Burrito", "Ceviche", "Fried Chicken", "Water"]
5. Sort tables numerically: ["3", "5", "10"]
6. Build table:

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

Each step builds toward the final table, with counts accurately reflecting the orders.

Time and Space Complexity

Brute-force Approach:
If we scanned all orders for every table-food pair, time complexity would be O(T * F * N), where T is the number of tables, F is the number of food items, and N is the number of orders.

Optimized Approach:

• Time Complexity: O(N + T log T + F log F), where N is the number of orders, T is the number of unique tables, and F is the number of unique food items. This is because:
  • O(N) to process all orders and build counts.
  • O(T log T) to sort the tables numerically.
  • O(F log F) to sort food items lexicographically.
• Space Complexity: O(T * F) for the count mapping, plus O(T + F) for storing unique tables and food items.

Summary

The solution efficiently builds a display table of food orders by leveraging sets for uniqueness and hash maps for quick counting. Sorting ensures the output matches the required format. This approach is both readable and efficient, making it a great example of using basic data structures to solve a real-world problem elegantly.

Code Implementation

class Solution:
    def displayTable(self, orders):
        from collections import defaultdict

        food_set = set()
        table_set = set()
        table_food_count = defaultdict(lambda: defaultdict(int))

        for customer, table, food in orders:
            food_set.add(food)
            table_set.add(table)
            table_food_count[table][food] += 1

        food_list = sorted(food_set)
        table_list = sorted(table_set, key=lambda x: int(x))

        result = []
        header = ["Table"] + food_list
        result.append(header)

        for table in table_list:
            row = [table]
            for food in food_list:
                row.append(str(table_food_count[table].get(food, 0)))
            result.append(row)

        return result
      

class Solution {
public:
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        set<string> foodSet;
        set<int> tableSet;
        unordered_map<int, unordered_map<string, int>> tableFoodCount;

        for (auto& order : orders) {
            string food = order[2];
            int table = stoi(order[1]);
            foodSet.insert(food);
            tableSet.insert(table);
            tableFoodCount[table][food]++;
        }

        vector<string> foodList(foodSet.begin(), foodSet.end());
        sort(foodList.begin(), foodList.end());

        vector<int> tableList(tableSet.begin(), tableSet.end());
        sort(tableList.begin(), tableList.end());

        vector<vector<string>> result;
        vector<string> header = {"Table"};
        header.insert(header.end(), foodList.begin(), foodList.end());
        result.push_back(header);

        for (int table : tableList) {
            vector<string> row;
            row.push_back(to_string(table));
            for (const string& food : foodList) {
                int count = tableFoodCount[table][food];
                row.push_back(to_string(count));
            }
            result.push_back(row);
        }
        return result;
    }
};
      

class Solution {
    public List<List<String>> displayTable(List<List<String>> orders) {
        Set<String> foodSet = new HashSet<>();
        Set<Integer> tableSet = new HashSet<>();
        Map<Integer, Map<String, Integer>> tableFoodCount = new HashMap<>();

        for (List<String> order : orders) {
            String food = order.get(2);
            int table = Integer.parseInt(order.get(1));
            foodSet.add(food);
            tableSet.add(table);
            tableFoodCount.putIfAbsent(table, new HashMap<>());
            Map<String, Integer> foodCount = tableFoodCount.get(table);
            foodCount.put(food, foodCount.getOrDefault(food, 0) + 1);
        }

        List<String> foodList = new ArrayList<>(foodSet);
        Collections.sort(foodList);

        List<Integer> tableList = new ArrayList<>(tableSet);
        Collections.sort(tableList);

        List<List<String>> result = new ArrayList<>();
        List<String> header = new ArrayList<>();
        header.add("Table");
        header.addAll(foodList);
        result.add(header);

        for (int table : tableList) {
            List<String> row = new ArrayList<>();
            row.add(String.valueOf(table));
            Map<String, Integer> foodCount = tableFoodCount.get(table);
            for (String food : foodList) {
                row.add(String.valueOf(foodCount.getOrDefault(food, 0)));
            }
            result.add(row);
        }
        return result;
    }
}
      

var displayTable = function(orders) {
    const foodSet = new Set();
    const tableSet = new Set();
    const tableFoodCount = {};

    for (const [customer, table, food] of orders) {
        foodSet.add(food);
        tableSet.add(table);
        if (!tableFoodCount[table]) tableFoodCount[table] = {};
        tableFoodCount[table][food] = (tableFoodCount[table][food] || 0) + 1;
    }

    const foodList = Array.from(foodSet).sort();
    const tableList = Array.from(tableSet).map(Number).sort((a, b) => a - b).map(String);

    const result = [];
    const header = ["Table", ...foodList];
    result.push(header);

    for (const table of tableList) {
        const row = [table];
        for (const food of foodList) {
            row.push(String(tableFoodCount[table]?.[food] || 0));
        }
        result.push(row);
    }
    return result;
};