LeetCode Problem 3580

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The task asks us to identify employees whose performance has consistently improved over their most recent three performance reviews. Each employee may have multiple reviews stored in the performance_reviews table, and we must focus only on the last three reviews per employee when ordered by review_date.

For each employee, we first determine whether they have at least three reviews. If they do, we extract their three most recent reviews and check whether the ratings form a strictly increasing sequence when ordered chronologically from oldest to newest within those three reviews. If the condition holds, the employee is included in the result.

We also compute an improvement score defined as the difference between the latest rating and the earliest rating among those three reviews. Finally, the output must include employee identifiers, names, and improvement scores, sorted by improvement score in descending order, and then by name in ascending order.

The key challenge is correctly isolating the last three reviews per employee and ensuring the correct temporal ordering before validating the monotonicity condition.

Edge cases include employees with fewer than three reviews, employees whose last three reviews are not strictly increasing even if earlier reviews were, and employees with repeated review dates requiring deterministic tie-breaking.

Approaches

The brute-force idea would be to group all reviews per employee, sort them in application memory or via a subquery, and then manually inspect the last three rows for each employee. While conceptually simple, this approach is inefficient because it does not leverage database window functions and may require expensive sorting and grouping operations outside optimized SQL execution paths.

The optimal solution uses window functions, specifically ROW_NUMBER() partitioned by employee and ordered by review date descending. This allows us to directly label the most recent reviews as rank 1, 2, and 3. We then filter to only these rows, pivot them into columns, and validate the strict ordering condition directly in SQL. This avoids per-row procedural computation and keeps the solution fully set-based, which is ideal for SQL engines.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n per employee)	O(n)	Sort per employee and manually inspect last three reviews
Optimal	O(n log n)	O(n)	Window functions isolate last 3 reviews efficiently

Algorithm Walkthrough

1. First, we assign a rank to each review within each employee group using ROW_NUMBER(), ordering by review_date in descending order. This ensures the most recent review is ranked 1, the second most recent is ranked 2, and the third most recent is ranked 3. This step is necessary to isolate the "last three reviews" without physically slicing arrays.
2. We filter the dataset to retain only rows where the rank is less than or equal to 3. At this stage, each employee may have up to three rows representing their most recent performance reviews. Employees with fewer than three total reviews will naturally be excluded later.
3. We join with the employees table to retrieve employee names, since the final output requires both identity and performance information.
4. We pivot the three ranked rows into a single row per employee using conditional aggregation. Specifically, we extract rating values for rank 1, rank 2, and rank 3 into separate columns. This transformation is essential because we need to compare the three values directly.
5. We filter out employees who do not have exactly three reviews by checking COUNT(*) = 3. This ensures we only evaluate complete triplets.
6. We enforce the strictly increasing condition by verifying that the oldest rating (rank 3) is less than the middle rating (rank 2), which is less than the newest rating (rank 1).
7. We compute the improvement score as the difference between the newest rating and the oldest rating.
8. Finally, we sort the result by improvement score in descending order and then by employee name in ascending order.

Why it works: The window function guarantees correct temporal ordering of the last three reviews. By transforming these into fixed positions (oldest, middle, newest), we reduce the problem to a deterministic comparison of three values per employee, ensuring correctness without ambiguity.

Python Solution

Although this is a database problem, we express the solution in executable SQL embedded in a Python block for LeetCode-style submission compatibility.

# This is a SQL solution written inside a Python string for LeetCode-style submission.

def solution():
    return """
    WITH ranked AS (
        SELECT
            pr.employee_id,
            pr.review_date,
            pr.rating,
            ROW_NUMBER() OVER (
                PARTITION BY pr.employee_id
                ORDER BY pr.review_date DESC, pr.review_id DESC
            ) AS rn
        FROM performance_reviews pr
    ),
    last_three AS (
        SELECT
            r.employee_id,
            e.name,
            r.rn,
            r.rating
        FROM ranked r
        JOIN employees e
            ON r.employee_id = e.employee_id
        WHERE r.rn <= 3
    ),
    pivoted AS (
        SELECT
            employee_id,
            name,
            MAX(CASE WHEN rn = 1 THEN rating END) AS r1,
            MAX(CASE WHEN rn = 2 THEN rating END) AS r2,
            MAX(CASE WHEN rn = 3 THEN rating END) AS r3,
            COUNT(*) AS cnt
        FROM last_three
        GROUP BY employee_id, name
    )
    SELECT
        employee_id,
        name,
        (r1 - r3) AS improvement_score
    FROM pivoted
    WHERE cnt = 3
      AND r3 < r2
      AND r2 < r1
    ORDER BY improvement_score DESC, name ASC;
    """

The ranked CTE assigns a deterministic ordering to reviews per employee. The last_three CTE restricts attention to the most recent three reviews. The pivoted CTE reshapes the data so comparisons can be performed horizontally. The final query filters valid improving sequences and computes the required score. The problem asks us to identify employees whose performance has consistently improved over their most recent three performance reviews. We are given two tables: one containing employee metadata and another containing multiple performance reviews per employee, each with a date and a rating from 1 to 5.

The key requirement is that we only consider the last three reviews for each employee when ordered by review_date. If an employee has fewer than three reviews, they are automatically excluded. For those with at least three reviews, we must check whether their ratings in chronological order (within those last three reviews) are strictly increasing, meaning each later review must have a strictly higher rating than the previous one.

For employees satisfying this condition, we compute an improvement score defined as the difference between the latest rating and the earliest rating among those last three reviews. Finally, results must be sorted by improvement score in descending order and then by employee name in ascending order.

The input consists of relational tables, so we are expected to solve this using SQL windowing and aggregation logic. The output is a filtered and ranked subset of employees with computed metrics.

Edge cases include employees with exactly three reviews, employees with more than three reviews where only the latest three matter, employees with non-monotonic trends in the last three reviews, and employees with ties in review dates (though the problem implies uniqueness via review_id and ordered dates). We also must ensure that ordering is strictly based on the most recent reviews, not all-time averages or trends.

Approaches

The brute-force approach would conceptually retrieve all reviews per employee, sort them by date in application memory, slice the last three, and then check whether the ratings are strictly increasing. While correct, this approach is inefficient in SQL contexts because it requires pulling all data into an external layer and performing per-employee sorting and filtering, which does not scale well.

The optimal approach uses SQL window functions. We first rank reviews per employee in descending order of date to isolate the last three reviews. Then we re-order those selected rows in ascending order to reconstruct the chronological sequence of the last three reviews. After that, we pivot these three rows into columns so we can directly compare ratings and compute both the strict increasing condition and the improvement score in a single grouped query.

The key insight is that window functions allow us to isolate a sliding subset (last 3 rows) without self-joins or procedural logic, and then a second ordering allows us to evaluate sequential constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n) per employee	O(n)	Extract and sort per employee externally
Optimal (Window Functions)	O(n log n) overall	O(n)	Uses ranking and conditional aggregation in SQL

Algorithm Walkthrough

The optimal solution proceeds as follows.

1. First, we assign a rank to each review within each employee partition, ordering by review_date in descending order. This allows us to identify the most recent reviews without manually sorting entire datasets per employee.
2. We filter this ranked dataset to keep only rows where the rank is less than or equal to 3. This ensures that we retain only the last three reviews per employee, regardless of how many total reviews exist.
3. We then re-rank these filtered rows per employee, but this time in ascending order of review_date. This step reconstructs the chronological order of the last three reviews, labeling them as first, second, and third.
4. We pivot these three ordered rows into columns using conditional aggregation so that each employee has three explicit rating values: r1, r2, and r3.
5. We filter out employees where r1, r2, and r3 do not form a strictly increasing sequence.
6. For valid employees, we compute the improvement score as r3 minus r1.
7. Finally, we join with the employees table to fetch names and sort the result by improvement score descending and name ascending.

The reason this works is that window functions guarantee correct extraction of the most recent three rows, and the second ordering ensures correct temporal reconstruction. The strict inequality check enforces monotonic improvement, and the pivoting ensures we can compare sequential values directly.

Python Solution

from typing import List

class Solution:
    def findConsistentlyImprovingEmployees(self) -> str:
        return """
        WITH ranked AS (
            SELECT
                e.employee_id,
                e.name,
                pr.rating,
                pr.review_date,
                ROW_NUMBER() OVER (
                    PARTITION BY pr.employee_id
                    ORDER BY pr.review_date DESC
                ) AS rn
            FROM employees e
            JOIN performance_reviews pr
                ON e.employee_id = pr.employee_id
        ),
        last_three AS (
            SELECT *
            FROM ranked
            WHERE rn <= 3
        ),
        ordered AS (
            SELECT
                employee_id,
                name,
                rating,
                review_date,
                ROW_NUMBER() OVER (
                    PARTITION BY employee_id
                    ORDER BY review_date ASC
                ) AS seq
            FROM last_three
        ),
        pivoted AS (
            SELECT
                employee_id,
                name,
                MAX(CASE WHEN seq = 1 THEN rating END) AS r1,
                MAX(CASE WHEN seq = 2 THEN rating END) AS r2,
                MAX(CASE WHEN seq = 3 THEN rating END) AS r3
            FROM ordered
            GROUP BY employee_id, name
        )
        SELECT
            employee_id,
            name,
            (r3 - r1) AS improvement_score
        FROM pivoted
        WHERE r1 < r2 AND r2 < r3
        ORDER BY improvement_score DESC, name ASC;
        """

The Python solution encapsulates the SQL query as a string, which is the standard way to submit database problems in environments where the execution engine runs SQL directly. The logic inside the query follows the algorithm precisely: ranking, filtering last three, reordering chronologically, pivoting into columns, and applying the strict increase constraint.

Go Solution

package main

func solution() string {
	return `
WITH ranked AS (
    SELECT
        pr.employee_id,
        pr.review_date,
        pr.rating,
        ROW_NUMBER() OVER (
            PARTITION BY pr.employee_id
            ORDER BY pr.review_date DESC, pr.review_id DESC
        ) AS rn
    FROM performance_reviews pr
),
last_three AS (
    SELECT
        r.employee_id,
        e.name,
        r.rn,
        r.rating
    FROM ranked r
    JOIN employees e
        ON r.employee_id = e.employee_id
    WHERE r.rn <= 3
),
pivoted AS (
    SELECT
        employee_id,
        name,
        MAX(CASE WHEN rn = 1 THEN rating END) AS r1,
        MAX(CASE WHEN rn = 2 THEN rating END) AS r2,
        MAX(CASE WHEN rn = 3 THEN rating END) AS r3,
        COUNT(*) AS cnt
    FROM last_three
    GROUP BY employee_id, name
)
SELECT
    employee_id,
    name,
    (r1 - r3) AS improvement_score
FROM pivoted
WHERE cnt = 3
  AND r3 < r2
  AND r2 < r1
ORDER BY improvement_score DESC, name ASC;
`
}

The Go version mirrors the Python approach exactly since the computation is entirely SQL-based. The only difference is syntactic wrapping. There are no concerns around memory management or numeric overflow because all computation is performed inside the database engine.

Worked Examples

For employee 1 (Alice Johnson), the ranking step produces:

rn	review_date	rating
1	2023-10-15	5
2	2023-07-15	4
3	2023-04-15	3

After pivoting:

• r1 = 5, r2 = 4, r3 = 3
• Strict condition holds: 3 < 4 < 5
• Improvement score = 5 - 3 = 2

For employee 2 (Bob Smith), the last three reviews after ranking are:

rn	rating
1	5
2	4
3	2

Strict condition holds: 2 < 4 < 5

Improvement score = 5 - 2 = 3

For employee 4 (David Wilson), the last three reviews are all 4:

rn	rating
1	4
2	4
3	4

This fails the strict inequality condition, so the employee is excluded. type Solution struct{}

func (s *Solution) FindConsistentlyImprovingEmployees() string { return WITH ranked AS ( SELECT e.employee_id, e.name, pr.rating, pr.review_date, ROW_NUMBER() OVER ( PARTITION BY pr.employee_id ORDER BY pr.review_date DESC ) AS rn FROM employees e JOIN performance_reviews pr ON e.employee_id = pr.employee_id ), last_three AS ( SELECT * FROM ranked WHERE rn <= 3 ), ordered AS ( SELECT employee_id, name, rating, review_date, ROW_NUMBER() OVER ( PARTITION BY employee_id ORDER BY review_date ASC ) AS seq FROM last_three ), pivoted AS ( SELECT employee_id, name, MAX(CASE WHEN seq = 1 THEN rating END) AS r1, MAX(CASE WHEN seq = 2 THEN rating END) AS r2, MAX(CASE WHEN seq = 3 THEN rating END) AS r3 FROM ordered GROUP BY employee_id, name ) SELECT employee_id, name, (r3 - r1) AS improvement_score FROM pivoted WHERE r1 < r2 AND r2 < r3 ORDER BY improvement_score DESC, name ASC; }

In Go, the main difference is simply how we return the SQL string. Unlike Python, Go requires explicit struct and method definitions. The SQL logic remains identical. String formatting uses raw string literals with backticks to preserve multiline SQL formatting cleanly without escaping characters.

## Worked Examples

For Alice Johnson (employee_id = 1), we first identify all reviews sorted by date descending, yielding ratings 5, 4, 3, 2. We keep only the last three reviews: 5 (2023-10-15), 4 (2023-07-15), and 3 (2023-04-15). Reordering them chronologically gives 3 → 4 → 5. Since 3 < 4 < 5, the employee qualifies. Improvement score is 5 - 3 = 2.

For Bob Smith (employee_id = 2), last three reviews are 2, 4, 5 in chronological order after filtering. The sequence is strictly increasing, so improvement score is 5 - 2 = 3.

For Carol Davis (employee_id = 3), last three reviews become 2 → 3 → 4, which is strictly increasing, yielding score 4 - 2 = 2.

For David Wilson (employee_id = 4), last three reviews are 4 → 4 → 4. Since values are not strictly increasing, the condition fails.

For Emma Brown (employee_id = 5), only two reviews exist after filtering, so the employee is excluded immediately at the `rn <= 3` stage due to insufficient data.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Window function requires sorting reviews per employee |
| Space | O(n) | Intermediate CTEs store up to all review rows |

The dominant cost is the `ROW_NUMBER()` computation, which requires ordering partitions of reviews by date. All subsequent operations are linear scans and aggregations.
| Time | O(n log n) | Sorting via window functions for ranking per employee dominates |
| Space | O(n) | Intermediate CTEs store subsets of review rows |

The complexity is driven primarily by the window function ordering operations, which require sorting partitions of the dataset. Each review is processed a constant number of times across CTE layers.

## Test Cases

Basic correctness using provided example structure

assert True # placeholder for SQL engine execution

Edge: employee with exactly 3 increasing reviews

assert True

Edge: employee with exactly 3 but not strictly increasing

assert True

Edge: employee with fewer than 3 reviews

assert True

Edge: multiple employees with same improvement score sorting by name

basic example structure validation

assert True # placeholder since logic is SQL-based

edge case: employee with exactly 3 increasing reviews

assert True

edge case: employee with exactly 3 non-increasing reviews

assert True

edge case: employee with fewer than 3 reviews

assert True

edge case: employee with many reviews but last 3 not increasing

assert True

| Test | Why |
| --- | --- |
| provided dataset | validates full correctness of ranking and scoring |
| exactly 3 increasing reviews | ensures inclusion condition works |
| non-increasing triplet | ensures strict inequality filter works |
| fewer than 3 reviews | ensures exclusion logic |
| tie on score | validates secondary ordering by name |

## Edge Cases

One important edge case is when an employee has fewer than three reviews. This must be explicitly excluded, and the `COUNT(*) = 3` condition ensures such employees never appear in the result even if partial data exists in the `rn <= 3` selection.

Another edge case occurs when review dates are identical. Without a secondary ordering key like `review_id`, the `ROW_NUMBER()` assignment may be nondeterministic. Including `review_id` in the ordering ensures stable ranking.

A final edge case involves employees whose last three reviews are not strictly increasing but contain earlier increasing sequences. Since we only consider the most recent three reviews, earlier history is irrelevant, and the filtering logic correctly ignores it by design.
| exactly 3 increasing reviews | verifies minimal valid case |
| exactly 3 non-increasing reviews | ensures strict ordering enforcement |
| fewer than 3 reviews | validates exclusion rule |
| many reviews, only last 3 matter | ensures correct windowing behavior |

## Edge Cases

One important edge case is when an employee has exactly three reviews. In this scenario, the algorithm must still correctly evaluate them without relying on ranking truncation logic errors. The window function approach naturally handles this because `rn <= 3` will include all rows.

Another edge case involves employees with more than three reviews where the first or middle reviews are increasing but the last three are not. This is critical because the problem explicitly requires evaluating only the most recent three reviews, not any best subsequence. The descending rank ensures we strictly isolate the correct subset.

A third edge case is employees with repeated ratings in the last three reviews. Even if the sequence is non-decreasing, it is invalid because the requirement is strictly increasing. The condition `r1 < r2 AND r2 < r3` enforces this strictly and prevents false positives where ratings are flat.