# 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

| Column | Type | Meaning |
|---|---|---|
| `id` | int | Employee ID |
| `month` | int | Month number |
| `salary` | int | Salary for that employee in that month |

The pair `(id, month)` is unique.

## Example

Input:

| id | month | salary |
|---|---:|---:|
| 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 |

Output:

| id | month | Salary |
|---|---:|---:|
| 1 | 7 | 90 |
| 1 | 4 | 130 |
| 1 | 3 | 90 |
| 1 | 2 | 50 |
| 1 | 1 | 20 |
| 2 | 1 | 20 |
| 3 | 3 | 100 |
| 3 | 2 | 40 |

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

For month `7`, the sum is:

```text
90 + 0 + 0 = 90
```

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

For month `4`, the sum is:

```text
60 + 40 + 30 = 130
```

For month `3`, the sum is:

```text
40 + 30 + 20 = 90
```

## First Thought: Use a Running Sum

A natural first idea is to use a window function:

```sql
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:

```text
current_month - previous_month is between 0 and 2
```

That includes:

```text
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:

```sql
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:

```text
N = number of rows in Employee
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(N^2)` worst case | The self join can compare rows for the same employee |
| Space | `O(N)` | The CTE and grouped result may store intermediate rows |

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

## Implementation

```sql
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:

```sql
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:

```sql
FROM CurrMonth AS curr
```

Then it joins to previous salary rows:

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

This means `prev.month` can be:

```text
curr.month
curr.month - 1
curr.month - 2
```

The most recent month is excluded here:

```sql
WHERE curr.month <> curr.max_month
```

Then the query sums the matching salaries:

```sql
SUM(prev.salary) AS Salary
```

Finally, the result is ordered as required:

```sql
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.

```sql
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:

```sql
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:

```sql
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:

| id | month | Salary |
|---|---:|---:|
| 1 | 7 | 90 |
| 1 | 4 | 130 |
| 1 | 3 | 90 |
| 1 | 2 | 50 |
| 1 | 1 | 20 |
| 2 | 1 | 20 |
| 3 | 3 | 100 |
| 3 | 2 | 40 |

Additional test cases:

| Case | Expected behavior |
|---|---|
| Employee has only one month | No row returned for that employee |
| Missing previous month | Missing month contributes `0` |
| Missing two previous months | Both missing months contribute `0` |
| Employee has months `1`, `4`, `7` | Each month only sums calendar months in range |
| Multiple employees | Each employee is processed independently |