LeetCode 1179 - Reformat Department Table

The problem is asking us to take a table Department that records revenue per department per month in a vertical format and convert it into a horizontal format, often called a "pivot" table. In the input, each row contains a department id, a revenue value, and a month.

leetcodeeasydatabase

LeetCode Problem 1179

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to take a table Department that records revenue per department per month in a vertical format and convert it into a horizontal format, often called a "pivot" table. In the input, each row contains a department id, a revenue value, and a month. The primary key ensures there is at most one revenue entry per department per month, so there will not be duplicates to handle.

The expected output is a table with one row per department, where each column corresponds to a month (from January to December) and contains that department’s revenue for the month. If there is no revenue recorded for a month, the column should contain NULL. The output must include all twelve months, regardless of whether revenue exists. The result can be returned in any order.

Important constraints include the guarantee that (id, month) is unique, which simplifies aggregation, and the fixed month values, which makes it possible to explicitly name the output columns. Edge cases include departments that only have revenue for a subset of months, months with no revenue at all, or an empty input table.

Approaches

The brute-force approach would be to iterate through all departments and months manually, building a result table row by row. For each department, you would scan the entire table to find revenue for each month. This approach is correct but inefficient because for D departments and R records, it requires O(D * 12 * R) lookups, which is unnecessary.

The optimal approach leverages SQL’s CASE expressions to pivot the table in a single pass. For each month, we create a column using SUM(CASE WHEN month = 'Jan' THEN revenue END) AS Jan_Revenue. Grouping by id ensures that each department produces one row. This approach is efficient because it only scans the table once and produces all output columns in a single query.

Approach Time Complexity Space Complexity Notes
Brute Force O(D * 12 * R) O(D * 12) Nested loops over departments and months; slow for large inputs
Optimal O(R) O(D * 12) Single-pass SQL aggregation using CASE and GROUP BY

Algorithm Walkthrough

  1. Start by selecting all records from the Department table.
  2. For each month from January to December, create a column using a CASE expression. If the row corresponds to the current month, return the revenue; otherwise, return NULL.
  3. Use SUM() to aggregate the revenue per department. Since (id, month) is unique, SUM() will simply return the revenue or NULL.
  4. Group the results by department id to collapse multiple rows into a single row per department.
  5. Return the resulting table. The output will have one row per department and one column per month.

Why it works: By using CASE expressions inside aggregation functions, we effectively pivot the rows into columns. Grouping by department ensures that all months are aligned in the same row. The uniqueness of (id, month) guarantees that no aggregation conflicts occur, so the result matches the expected format.

Python Solution

class Solution:
    def reformatDepartmentTable(self, department: list[dict]) -> list[dict]:
        import pandas as pd

        if not department:
            return []

        df = pd.DataFrame(department)
        months = ["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"]
        
        pivot_df = df.pivot(index='id', columns='month', values='revenue')
        
        # Rename columns
        pivot_df = pivot_df.reindex(columns=months)
        pivot_df.columns = [f"{month}_Revenue" for month in pivot_df.columns]
        pivot_df = pivot_df.reset_index()
        
        # Convert DataFrame to list of dicts
        result = pivot_df.to_dict(orient='records')
        return result

In this implementation, we first load the input into a pandas DataFrame. We then pivot the table so that each month becomes a column. Missing months automatically produce NaN, which pandas will convert to None when using to_dict(orient='records'). Finally, we rename the columns to match the _Revenue naming convention and reset the index so id becomes a column.

Go Solution

package main

type Department struct {
    Id      int
    Revenue int
    Month   string
}

type Result struct {
    Id          int
    JanRevenue  *int
    FebRevenue  *int
    MarRevenue  *int
    AprRevenue  *int
    MayRevenue  *int
    JunRevenue  *int
    JulRevenue  *int
    AugRevenue  *int
    SepRevenue  *int
    OctRevenue  *int
    NovRevenue  *int
    DecRevenue  *int
}

func reformatDepartmentTable(departments []Department) []Result {
    monthMap := map[string]func(r *Result, val int){
        "Jan": func(r *Result, val int) { r.JanRevenue = &val },
        "Feb": func(r *Result, val int) { r.FebRevenue = &val },
        "Mar": func(r *Result, val int) { r.MarRevenue = &val },
        "Apr": func(r *Result, val int) { r.AprRevenue = &val },
        "May": func(r *Result, val int) { r.MayRevenue = &val },
        "Jun": func(r *Result, val int) { r.JunRevenue = &val },
        "Jul": func(r *Result, val int) { r.JulRevenue = &val },
        "Aug": func(r *Result, val int) { r.AugRevenue = &val },
        "Sep": func(r *Result, val int) { r.SepRevenue = &val },
        "Oct": func(r *Result, val int) { r.OctRevenue = &val },
        "Nov": func(r *Result, val int) { r.NovRevenue = &val },
        "Dec": func(r *Result, val int) { r.DecRevenue = &val },
    }

    resMap := make(map[int]*Result)
    for _, d := range departments {
        if _, exists := resMap[d.Id]; !exists {
            resMap[d.Id] = &Result{Id: d.Id}
        }
        monthMap[d.Month](resMap[d.Id], d.Revenue)
    }

    result := make([]Result, 0, len(resMap))
    for _, v := range resMap {
        result = append(result, *v)
    }
    return result
}

In Go, we need to use pointers for optional int values to represent nulls. We maintain a map from month names to setter functions to assign revenue to the correct field. Each department is stored in a map by id to ensure one row per department.

Worked Examples

Input Table:

id revenue month
1 8000 Jan
2 9000 Jan
3 10000 Feb
1 7000 Feb
1 6000 Mar

Step-by-Step Pivoting:

  1. Initialize an empty map resMap.
  2. Process row (1, 8000, Jan): create Result for id 1, set JanRevenue = 8000.
  3. Process row (2, 9000, Jan): create Result for id 2, set JanRevenue = 9000.
  4. Process row (3, 10000, Feb): create Result for id 3, set FebRevenue = 10000.
  5. Process row (1, 7000, Feb): update Result for id 1, set FebRevenue = 7000.
  6. Process row (1, 6000, Mar): update Result for id 1, set MarRevenue = 6000.

Final resMap corresponds to the output table.

Complexity Analysis

Measure Complexity Explanation
Time O(R) We iterate over all rows once to populate the pivot table
Space O(D * 12) We store a Result object per department with 12 months

The complexity is linear in the number of input rows. The space grows with the number of departments, which is manageable because each department stores a fixed number of 12 month columns.

Test Cases

# test cases
assert Solution().reformatDepartmentTable([]) == []  # empty input
assert Solution().reformatDepartmentTable([
    {"id":1,"revenue":8000,"month":"Jan"},
    {"id":2,"revenue":9000,"month":"Jan"},
    {"id":3,"revenue":10000,"month":"Feb"},
    {"id":1,"revenue":7000,"month":"Feb"},
    {"id":1,"revenue":6000,"month":"Mar"},
]) == [
    {'id': 1, 'Jan_Revenue': 8000, 'Feb_Revenue': 7000, 'Mar_Revenue': 6000, 'Apr_Revenue': None, 'May_Revenue': None, 'Jun_Revenue': None, 'Jul_Revenue': None, 'Aug_Revenue': None, 'Sep_Revenue': None, 'Oct_Revenue': None