2408. Design SQL

MediumDesignArrayHash TableString
Leetcode Link

Problem Description

In this problem, we are asked to simulate the basic functionalities of SQL tables using a class. Firstly, we have an array of table names names and another array columns representing the number of columns in each corresponding table. Our SQL class should support three main operations:

  1. Insert a row: We need to be able to insert a new row into a specified table. Each row should have a unique auto-incremented id, with the first row having an id of 1. Further inserted rows should increment from the id of the last inserted row.

  2. Delete a row: We need to be able to remove a row from a specified table based on its id. It's worth noting that deleting a row does not impact the ids of future rows.

  3. Select a cell: We should be able to select and return the value from a specified cell in a table, given the table name, the row id, and the column id.

The operation insertRow should add a row to an existing table, deleteRow should remove a row by its id, and selectCell should return the value of a cell based on its table name, row id, and column id.


The main idea behind the solution is to use data structures that allow us to simulate the behavior of a SQL database. We can use Python's defaultdict to represent each table and manage the rows. We choose defaultdict because it helps us handle the case where a table might not exist already.

Here is the intuition for handling the operations:

  1. Initialization (__init__ method): To represent our tables, we can use a dictionary (defaultdict of list) where each key is a table name and the value is a list of rows. We don't need to use the columns array directly, as the number of elements in each inserted row will inherently match the number of columns.

  2. Insert a row (insertRow method): To insert a row, we append the new row at the end of the corresponding table's list. Here, the table's list acts as a stack of rows, where the id of each row is implicitly defined by its position in the list.

  3. Delete a row (deleteRow method): The provided code snippet does not implement this method, however, the intuition is that we'd need to identify the row by its id (index in the list) and remove it from the list. This operation needs to keep track of the ids of removed rows, particularly for auto-incrementing new row ids even after deletions.

  4. Select a cell (selectCell method): To access a specific cell, we use the row id and column id to index into the list of rows (adjusting for the fact that ids are 1-based while indices are 0-based).

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following is a min heap?

Solution Approach

The solution involves implementing the SQL class with the methods corresponding to the operations that need to be performed on the SQL tables.

Here is an overview of the implementation details:

  1. Initialization (__init__ method): Since Python lists maintain the order of elements, we use them to represent rows in each table. We map the names of tables to a list of rows using a defaultdict to ensure that any non-existent key accessed returns an empty list by default.

    1def __init__(self, names: List[str], columns: List[int]):
    2    self.tables = defaultdict(list)

    self.tables is the main data structure holding table data mapped by table names. The columns argument is not used as the length of row lists will inherently enforce the number of columns.

  2. Insert a row (insertRow method): Inserting a row does not require an id to be explicitly stored. Instead, each row's position in the list gives us the id implicitly (id of the row is the index of the row in the list + 1).

    1def insertRow(self, name: str, row: List[str]) -> None:
    2    self.tables[name].append(row)

    When insertRow is called, we simply append the new row (row) to the list of existing rows in the table referred to by name.

  3. Delete a row (deleteRow method): While the provided solution snippet does not complete this method, an ideal implementation would find the row at the given rowId and remove it from the list. One potential way to implement it could look like this:

    1def deleteRow(self, name: str, rowId: int) -> None:
    2    if rowId <= len(self.tables[name]):
    3        self.tables[name].pop(rowId - 1)

    This implementation uses the .pop() method to remove an element from the list at the given index. rowId - 1 is used to convert the row id to a 0-based index.

  4. Select a cell (selectCell method): The selection of a cell is a straightforward index operation. Since Python lists are zero-indexed, we subtract 1 from both rowId and columnId to get the correct indices.

    1def selectCell(self, name: str, rowId: int, columnId: int) -> str:
    2    return self.tables[name][rowId - 1][columnId - 1]

    The selectCell method retrieves the value at the specified rowId and columnId by indexing into the list of rows and then the individual row.

In general, the approach utilizes the convenient properties of Python's lists and defaultdict to simulate the storage and access patterns of a relational database table. A real SQL database would need more complex logic for indexing, storing data efficiently, handling types and constraints, and many other operations. However, for the problem's simplified requirements, this approach is sufficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;

Example Walkthrough

Let's illustrate the solution approach using a hypothetical SQL class to manage a small dataset with two tables: employees and salaries. Assume the employees table has 2 columns for simplicity (name and position), and the salaries table has just 1 column (amount). We'll walk through each of the class's operations using this example data.


We start by initializing an SQL object. The names list contains table names ['employees', 'salaries'], and the columns list would be [2, 1] for the number of columns in each table respectively.

1sql = SQL(['employees', 'salaries'], [2, 1])

What happens here is that an internal tables dictionary is created, where each table name is a key that maps to an empty list for the rows. The columns information is, for now, unnecessary.

Insert a Row

Next, we want to add rows to our tables. Let's add an employee named "John Doe" with the position "Developer".

1sql.insertRow('employees', ['John Doe', 'Developer'])

After this operation, the internal structure for the employees table contains one row: [["John Doe", "Developer"]]. This row has an implicit id of 1.

Now, let's assume we add another employee and a salary entry:

1sql.insertRow('employees', ['Jane Smith', 'Manager'])
2sql.insertRow('salaries', ['60000'])

After these insertions, employees has two rows, and salaries has one row, each with their corresponding implicit IDs.

Delete a Row

We discover that we need to remove an employee's record. Let's remove the employee with id 1, which is John Doe.

1sql.deleteRow('employees', 1)

After this command, the internal list for employees will have just one row left: [["Jane Smith", "Manager"]].

Select a Cell

Finally, we want to see the position of the employee with id 1, which, after deletion, is now Jane Smith.

1position = sql.selectCell('employees', 1, 2)
2print(position)  # Output: Manager

To retrieve this, the method accesses the first row of the employees table and the second column, yielding "Manager".

In this example, the insert, delete, and select functionalities of a basic SQL table were simulated using the provided solution approach, which utilizes Python's defaultdict and lists. It demonstrates how each operation works and how the class maintains the table state after each operation.

Solution Implementation

1from collections import defaultdict
2from typing import List, Dict
4class SQL:
5    def __init__(self, names: List[str], columns: List[int]):
6        # Initialize a dictionary to store table data.
7        # The key is the table name, and the value is a list of rows, where each row is a list of strings.
8        self.tables: Dict[str, List[List[str]]] = defaultdict(list)
10        # We could perhaps create each table here with its column structure,
11        # but since this is not being used in the provided methods, this part is skipped.
13    def insert_row(self, name: str, row: List[str]) -> None:
14        """Insert a new row into the specified table."""
15        # Append the new row to the list of rows for the table with the given name.
16        self.tables[name].append(row)
18    def delete_row(self, name: str, row_id: int) -> None:
19        """Delete a row from the specified table based on the row ID."""
20        # Row ID is based on a 1-indexed list.
21        # Subtract 1 from the row_id to get the correct index for 0-indexed Python lists.
22        # Perform the delete operation only if the row_id is valid.
23        if 0 <= row_id - 1 < len(self.tables[name]):
24            # Remove the row at the specified index.
25            del self.tables[name][row_id - 1]
27    def select_cell(self, name: str, row_id: int, column_id: int) -> str:
28        """Return the value in the specified cell from the table."""
29        # Access the cell based on the row and column ID, adjusting for 1-indexing.
30        return self.tables[name][row_id - 1][column_id - 1]
33# Your SQL object will be instantiated and called as such:
34# obj = SQL(names, columns)
35# obj.insert_row(name, row)
36# obj.delete_row(name, row_id)
37# param_3 = obj.select_cell(name, row_id, column_id)
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
7Simulates basic operations of a SQL database in memory.
9class SQL {
11    // Map that holds the table names as keys and lists of rows (which are lists of strings) as values.
12    private Map<String, List<List<String>>> tables;
14    /*
15    Constructor initializes the map using the size of the list of table names.
16    @param names List<String> representing the names of the tables.
17    @param columns List<Integer> representing the number of columns in each corresponding table.
18    The columns list is currently not used in the implementation.
19    */
20    public SQL(List<String> names, List<Integer> columns) {
21        tables = new HashMap<>(names.size());
22        // Actual column information is not stored, which is a potential area for modification or extension.
23    }
25    /*
26    Inserts a new row into a specified table.
27    @param name The name of the table.
28    @param row The row data to insert as a list of Strings.
29    */
30    public void insertRow(String name, List<String> row) {
31        // If key is absent, initialize with new ArrayList, and then add the row to the table's list.
32        tables.computeIfAbsent(name, k -> new ArrayList<>()).add(row);
33    }
35    /*
36    Deletes a row from a specified table.
37    @param name The name of the table.
38    @param rowId The row identifier (1-indexed) specifying which row to delete.
39    */
40    public void deleteRow(String name, int rowId) {
41        // Accesses the table by name and removes the row at index (rowId - 1).
42        List<List<String>> rows = tables.get(name);
43        if (rows != null && rowId > 0 && rowId <= rows.size()) {
44            rows.remove(rowId - 1);
45        }
46    }
48    /*
49    Selects an individual cell's data from a specified table.
50    @param name The name of the table.
51    @param rowId The row identifier (1-indexed).
52    @param columnId The column identifier (1-indexed).
53    @return A string representing the data in the selected cell.
54    */
55    public String selectCell(String name, int rowId, int columnId) {
56        // Retrieves the specified cell from the table by accessing the correct row and column.
57        // Adjusts the indices since 'rowId' and 'columnId' are 1-indexed.
58        return tables.get(name).get(rowId - 1).get(columnId - 1);
59    }
63Code usage:
64SQL obj = new SQL(names, columns);
65obj.insertRow(name, row);
66obj.deleteRow(name, rowId);
67String cellData = obj.selectCell(name, rowId, columnId);
1#include <string>
2#include <vector>
3#include <unordered_map>
4using namespace std;
6// The SQL class provides a simulation of a simple SQL table management
7// system, storing tables and allowing insertions, deletions, and queries.
8class SQL {
10    // Stores the tables with each table name mapped to a vector of rows,
11    // where each row is a vector of strings (representing cells).
12    unordered_map<string, vector<vector<string>>> tables;
15    // Constructor to initialize the SQL object with table names and number of
16    // columns for each table. The input arrays `names` and `columns` are
17    // expected to be of the same size.
18    SQL(vector<string>& names, vector<int>& columns) {
19        for (size_t i = 0; i < names.size(); ++i) {
20            // Initialize each table with its name and with the specified 
21            // number of columns. Each row is initially an empty vector.
22            tables[names[i]] = vector<vector<string>>(0, vector<string>(columns[i], ""));
23        }
24    }
26    // Inserts a new row into the table corresponding to the specified name.
27    void insertRow(string name, vector<string> row) {
28        if (tables.find(name) != tables.end()) {
29            tables[name].push_back(row);
30        }
31        // If the table does not exist, the row is not inserted.
32    }
34    // Deletes a row from the table corresponding to the specified name at
35    // the given rowId. It is assumed rowId is 1-based index.
36    void deleteRow(string name, int rowId) {
37        if (tables.find(name) != tables.end() && rowId > 0 && rowId <= tables[name].size()) {
38            tables[name].erase(tables[name].begin() + (rowId - 1));
39        }
40        // If the table or rowId does not exist, no action is performed.
41    }
43    // Selects and returns the cell content from the specified table, rowId,
44    // and columnId. The rowId and columnId are 1-based indices.
45    string selectCell(string name, int rowId, int columnId) {
46        if (tables.find(name) != tables.end() &&
47            rowId > 0 && columnId > 0 &&
48            rowId <= tables[name].size() &&
49            columnId <= tables[name][rowId - 1].size()) {
50            return tables[name][rowId - 1][columnId - 1];
51        }
52        // If the table, rowId, or columnId do not exist, return an empty string.
53        return "";
54    }
57// Usage
58// vector<string> names = {"table1", "table2"};
59// vector<int> columns = {3, 4}; // assuming table1 has 3 columns and table2 has 4
60// SQL* obj = new SQL(names, columns);
61// obj->insertRow("table1", {"val1", "val2", "val3"});
62// obj->deleteRow("table1", 1);
63// string cell = obj->selectCell("table1", 1, 2);
1// Define an interface for the table structure, where each table is a dictionary.
2// The keys are strings (table names), and the values are 2D arrays of strings (table rows).
3interface Tables {
4  [tableName: string]: string[][];
7// Global object to store all the tables.
8let tables: Tables = {};
10// Function to initialize the tables with the given names and number of columns.
11function createTables(names: string[], columns: number[]): void {
12  names.forEach((name, index) => {
13    tables[name] = Array.from({ length: 0 }, () => new Array(columns[index]).fill(""));
14  });
17// Function to insert a new row into the specified table.
18function insertRow(tableName: string, row: string[]): void {
19  if (tables[tableName]) {
20    tables[tableName].push(row);
21  }
22  // If the table does not exist, the row is not inserted.
25// Function to delete a row from the specified table using a 1-based index.
26function deleteRow(tableName: string, rowId: number): void {
27  const table = tables[tableName];
28  if (table && rowId > 0 && rowId <= table.length) {
29    table.splice(rowId - 1, 1);
30  }
31  // If the table or rowId does not exist, no action is performed.
34// Function to select and return a cell content from the specified table.
35function selectCell(tableName: string, rowId: number, columnId: number): string {
36  const table = tables[tableName];
37  if (table &&
38      rowId > 0 && columnId > 0 &&
39      rowId <= table.length && 
40      columnId <= table[rowId - 1].length) {
41    return table[rowId - 1][columnId - 1];
42  }
43  // If the table, rowId, or columnId do not exist, return an empty string.
44  return "";
47// Example Usage:
48// createTables(["table1", "table2"], [3, 4]);
49// insertRow("table1", ["val1", "val2", "val3"]);
50// deleteRow("table1", 1);
51// const cell: string = selectCell("table1", 1, 2);
Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
20    bubble_up() {
21        let index = this.heap.length - 1;
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
65    peek() {
66        return this.heap[0];
67    }
69    size() {
70        return this.heap.length;
71    }
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;

Time and Space Complexity

Time Complexity

  • __init__(self, names: List[str], columns: List[int]): The initialization of the SQL class has a time complexity of O(1) since it only involves setting up a default dictionary, which is an instance of the data structure and does not depend on the input size.

  • insertRow(self, name: str, row: List[str]): The insertion of a row has a time complexity of O(1). Although appending to a list is technically an O(1) operation, there might be occasional resizing of the list when it needs to extend its capacity, which can cause an O(n) operation, but this is amortized O(1) over a sequence of insertions.

  • deleteRow(self, name: str, rowId: int): The code for this function is not provided, but if implemented properly using list.pop(index) (assuming rowId maps to index directly), it has a time complexity of O(n) where n is the number of rows in the table. This is because list.pop(index) needs to shift all elements after the index to fill the gap.

  • selectCell(self, name: str, rowId: int, columnId: int): Selecting a cell has a time complexity of O(1) because accessing an element in a list by index is a constant time operation.

Space Complexity

  • __init__(self, names: List[str], columns: List[int]): The space complexity is O(n) where n is the number of different table names possible as each name will eventually have a corresponding key in the default dictionary.

  • insertRow(self, name: str, row: List[str]): The space complexity for inserting a row is O(m) where m represents the length of the row being inserted. Over time, the total space complexity for all insertions will be O(n * m) where n is the number of rows and m is the average length of the rows across all tables.

  • deleteRow(self, name: str, rowId: int): This operation does not change the space complexity which is determined by the number and size of existing rows.

  • selectCell(self, name: str, rowId: int, columnId: int): Selecting a cell does not use additional space, so its space complexity is O(1).

Note: The deleteRow function is currently a placeholder and does not perform any action. If it was implemented, it could potentially decrease the space used; however, the space complexity analysis assumes that the lists' capacities are not reduced when elements are removed, as this is standard behavior for dynamic arrays in many programming languages including Python.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Recommended Readings

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫