LeetCode 1077 - Project Employees III

LeetCode Problem 1077

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to find the most experienced employees in each project from two database tables, Project and Employee. The Project table contains a mapping of employee_ids to project_ids, indicating which employees work on which projects. The Employee table provides additional details for each employee, including name and experience_years.

The goal is to return, for each project, the employee(s) with the maximum experience_years. In cases where multiple employees share the highest experience in the same project, all of them must be included. The result does not need to be in any specific order.

Key points about the input: every employee_id in the Project table exists in the Employee table. There are no duplicate rows in Project, and each employee's experience is non-negative. Important edge cases include projects with only one employee, employees with identical experience values, and projects with multiple employees having the same maximum experience.

Approaches

The brute-force approach involves first joining the Project table with the Employee table to get the experience for each employee in each project. Then, for each project, we scan through all its employees to find the maximum experience, followed by another pass to select all employees that match this maximum. While correct, this approach is inefficient for large datasets, especially when implemented in SQL with multiple scans or nested loops, because it requires scanning each project’s employee list multiple times.

The optimal approach leverages a single join and a window function. By joining Project and Employee on employee_id, we have a table containing project_id, employee_id, and experience_years. We can then use the SQL MAX() window function partitioned by project_id to calculate the maximum experience for each project. Finally, we filter the rows where the employee’s experience matches this maximum. This approach is efficient because it avoids repeated scans and makes use of SQL’s analytical capabilities.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(P * E)	O(P * E)	Join then iterate per project twice: first to find max, then to select employees.
Optimal	O(P * E)	O(P * E)	Single join with window function to compute max per project and filter in one pass.

Algorithm Walkthrough

1. Perform an inner join between Project and Employee on employee_id to get a combined table with project_id, employee_id, and experience_years.
2. For each project_id, compute the maximum experience_years using a window function. This attaches a new column max_experience to every row of the combined table.
3. Filter the table to keep only rows where experience_years equals max_experience. These rows correspond to the most experienced employees in each project.
4. Select the final columns project_id and employee_id to form the result.

Why it works: The window function ensures that for each project, every row knows the maximum experience in that project. Filtering by equality guarantees that only employees with the highest experience are included. This invariant holds regardless of how many employees share the maximum experience.

Python Solution

import sqlite3
from typing import List, Tuple

def most_experienced_employees(conn: sqlite3.Connection) -> List[Tuple[int, int]]:
    query = """
    WITH ProjectExperience AS (
        SELECT 
            p.project_id,
            p.employee_id,
            e.experience_years,
            MAX(e.experience_years) OVER (PARTITION BY p.project_id) AS max_experience
        FROM Project p
        JOIN Employee e ON p.employee_id = e.employee_id
    )
    SELECT project_id, employee_id
    FROM ProjectExperience
    WHERE experience_years = max_experience
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

The Python implementation uses a sqlite3 connection to execute the SQL query. First, it joins the Project and Employee tables to obtain experience information. The window function MAX(...) OVER (PARTITION BY project_id) computes the maximum experience per project efficiently. Finally, it filters rows where the employee's experience matches the maximum and returns the resulting list of tuples containing project_id and employee_id.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func MostExperiencedEmployees(db *sql.DB) ([][2]int, error) {
    query := `
    WITH ProjectExperience AS (
        SELECT 
            p.project_id,
            p.employee_id,
            e.experience_years,
            MAX(e.experience_years) OVER (PARTITION BY p.project_id) AS max_experience
        FROM Project p
        JOIN Employee e ON p.employee_id = e.employee_id
    )
    SELECT project_id, employee_id
    FROM ProjectExperience
    WHERE experience_years = max_experience;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results [][2]int
    for rows.Next() {
        var projectID, employeeID int
        if err := rows.Scan(&projectID, &employeeID); err != nil {
            return nil, err
        }
        results = append(results, [2]int{projectID, employeeID})
    }
    return results, nil
}

The Go solution is structurally similar to the Python one. It executes the same SQL query and scans each row into a fixed-size array [2]int representing (project_id, employee_id). The key differences are handling errors explicitly and using slices for dynamic collection of results.

Worked Examples

For the first example:

Project table:

project_id	employee_id
1	1
1	2
1	3
2	1
2	4

Employee table:

employee_id	name	experience_years
1	Khaled	3
2	Ali	2
3	John	3
4	Doe	2

Step 1: Join Project and Employee:

project_id	employee_id	experience_years
1	1	3
1	2	2
1	3	3
2	1	3
2	4	2

Step 2: Compute max experience per project:

project_id	employee_id	experience_years	max_experience
1	1	3	3
1	2	2	3
1	3	3	3
2	1	3	3
2	4	2	3

Step 3: Filter where experience_years = max_experience:

project_id	employee_id
1	1
1	3
2	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(P * E)	Join operation and window function scan every row once, where P is number of projects and E is total employees.
Space	O(P * E)	Intermediate table stores joined rows plus a column for max experience.

The complexity arises from scanning each employee in each project exactly once and storing the intermediate results for filtering.

Test Cases

# test cases
assert most_experienced_employees(conn := sqlite3.connect(':memory:')) == []  # empty tables
# Example 1
conn.executescript("""
CREATE TABLE Employee(employee_id INT, name TEXT, experience_years INT);
CREATE TABLE Project(project_id INT, employee_id INT);
INSERT INTO Employee VALUES (1,'Khaled',3),(2,'Ali',2),(3,'John',3),(4,'Doe',2);
INSERT INTO Project VALUES (1,1),(1,2),(1,3),(2,1),(2,4);
""")
assert sorted(most_experienced_employees(conn)) == sorted([(1,1),(1,3),(2,1)])
# Single project single employee
conn.executescript("DELETE FROM Project; DELETE FROM Employee;")
conn.executescript("INSERT INTO Employee VALUES (1,'A',5); INSERT INTO Project VALUES (1,1);")
assert most_experienced_employees(conn) == [(1,1)]
# Multiple employees same experience
conn.executescript("DELETE FROM Project; DELETE FROM Employee;")
conn.executescript("INSERT INTO Employee VALUES (1,'A',5),(2,'B',5); INSERT INTO Project VALUES (1,1),(1,2);")
assert sorted(most_experienced_employees(conn)) == [(1,1),(1,2)]
# Multiple projects
conn.executescript("DELETE FROM Project; DELETE FROM