LeetCode 579: Find Cumulative Salary of an Employee

Problem Restatement

We are given an Employee table that stores each employee’s salary for different months.

For each employee and each month they worked, we need to calculate the sum of that month’s salary and the salaries from the previous two months.

However, we must not include the employee’s most recent month in the output.

The result should be ordered by id in ascending order, then by month in descending order. The official problem defines the table as (id, month, salary), with (id, month) as the primary key.

Table

Employee

The pair (id, month) is unique.

Example

Input:

Output:

For employee 1, the most recent month is 8, so month 8 is excluded.

For month 7, the sum is:

90 + 0 + 0 = 90

Months 6 and 5 are missing, so they contribute 0.

For month 4, the sum is:

60 + 40 + 30 = 130

For month 3, the sum is:

40 + 30 + 20 = 90

First Thought: Use a Running Sum

A natural first idea is to use a window function:

SUM(salary) OVER (
    PARTITION BY id
    ORDER BY month
    ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
)

This works only if every employee has continuous month records.

But the problem counts the current month and the previous two calendar months, not simply the previous two rows.

For example, employee 1 has months 4, 7, and 8.

For month 7, the previous two calendar months are 6 and 5, not months 4 and 3.

So a row-based window frame can give the wrong result when months are missing.

Key Insight

For each row (id, month), we need salaries from the same employee where:

current_month - previous_month is between 0 and 2

That includes:

current month
previous month
two months before

Missing months naturally contribute nothing because there is no matching row.

We also need to exclude each employee’s most recent month.

So the solution has two parts:

1. Find each employee’s most recent month.
2. Join each current row to salary rows from the same employee within the 3-month range.

Algorithm

1. Use a window function to compute max_month for each employee.
2. Treat each row as a current month.
3. Join it with previous salary rows from the same employee.
4. Keep rows where the salary row month is within the current month and previous two months.
5. Exclude rows where month = max_month.
6. Group by id and month.
7. Sum the matching salaries.
8. Order by id ASC, month DESC.

Correctness

For each employee-month row, the join matches salary rows with the same id.

The join condition:

curr.month - prev.month BETWEEN 0 AND 2

keeps exactly the salary rows from the current month, one month before, and two months before. It excludes future months and months more than two months earlier.

Therefore, after grouping by curr.id and curr.month, SUM(prev.salary) is exactly the required 3-month cumulative salary for that employee-month.

The window expression MAX(month) OVER (PARTITION BY id) computes the most recent worked month for each employee. The filter curr.month != curr.max_month removes exactly that most recent month from the output.

Thus, every returned row has the correct cumulative salary, and every required employee-month row is returned.

Complexity

Let:

N = number of rows in Employee

In practice, a database can optimize this with indexes on (id, month).

Implementation

WITH CurrMonth AS (
    SELECT
        id,
        month,
        salary,
        MAX(month) OVER (PARTITION BY id) AS max_month
    FROM Employee
)
SELECT
    curr.id,
    curr.month,
    SUM(prev.salary) AS Salary
FROM CurrMonth AS curr
JOIN Employee AS prev
    ON curr.id = prev.id
   AND curr.month - prev.month BETWEEN 0 AND 2
WHERE curr.month <> curr.max_month
GROUP BY curr.id, curr.month
ORDER BY curr.id ASC, curr.month DESC;

Code Explanation

The CTE adds the most recent month for each employee:

WITH CurrMonth AS (
    SELECT
        id,
        month,
        salary,
        MAX(month) OVER (PARTITION BY id) AS max_month
    FROM Employee
)

For employee 1, if the largest month is 8, every row for employee 1 receives max_month = 8.

The main query treats each row in CurrMonth as the current month:

FROM CurrMonth AS curr

Then it joins to previous salary rows:

JOIN Employee AS prev
    ON curr.id = prev.id
   AND curr.month - prev.month BETWEEN 0 AND 2

This means prev.month can be:

curr.month
curr.month - 1
curr.month - 2

The most recent month is excluded here:

WHERE curr.month <> curr.max_month

Then the query sums the matching salaries:

SUM(prev.salary) AS Salary

Finally, the result is ordered as required:

ORDER BY curr.id ASC, curr.month DESC;

Alternative Without Window Functions

Some SQL environments for this problem may not support window functions. We can use a grouped subquery instead.

SELECT
    e1.id,
    e1.month,
    SUM(e2.salary) AS Salary
FROM Employee AS e1
JOIN Employee AS e2
    ON e1.id = e2.id
   AND e1.month - e2.month BETWEEN 0 AND 2
JOIN (
    SELECT
        id,
        MAX(month) AS max_month
    FROM Employee
    GROUP BY id
) AS recent
    ON e1.id = recent.id
WHERE e1.month <> recent.max_month
GROUP BY e1.id, e1.month
ORDER BY e1.id ASC, e1.month DESC;

This version computes the most recent month in a separate derived table.

Testing

Sample data:

CREATE TABLE Employee (
    id INT,
    month INT,
    salary INT,
    PRIMARY KEY (id, month)
);

INSERT INTO Employee (id, month, salary) VALUES
(1, 1, 20),
(2, 1, 20),
(1, 2, 30),
(2, 2, 30),
(3, 2, 40),
(1, 3, 40),
(3, 3, 60),
(1, 4, 60),
(3, 4, 70),
(1, 7, 90),
(1, 8, 90);

Query:

WITH CurrMonth AS (
    SELECT
        id,
        month,
        salary,
        MAX(month) OVER (PARTITION BY id) AS max_month
    FROM Employee
)
SELECT
    curr.id,
    curr.month,
    SUM(prev.salary) AS Salary
FROM CurrMonth AS curr
JOIN Employee AS prev
    ON curr.id = prev.id
   AND curr.month - prev.month BETWEEN 0 AND 2
WHERE curr.month <> curr.max_month
GROUP BY curr.id, curr.month
ORDER BY curr.id ASC, curr.month DESC;

Expected result:

Additional test cases: