Find Cumulative Salary of an Employee - Video Solutions
Leetcode HARD 579 - Cumulative Salary of Employee RANGE vs ROW BETWEEN in SQL - Explained by EDS
Find Cumulative Salary of an Employee - Video Solution
Watch 5 video solutions for Find Cumulative Salary of an Employee, a hard level problem involving Database. This walkthrough by Everyday Data Science has 1,343 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Table: Employee
+-------------+------+ | Column Name | Type | +-------------+------+ | id | int | | month | int | | salary | int | +-------------+------+ (id, month) is the primary key (combination of columns with unique values) for this table. Each row in the table indicates the salary of an employee in one month during the year 2020.
Write a solution to calculate the cumulative salary summary for every employee in a single unified table.
The cumulative salary summary for an employee can be calculated as follows:
- For each month that the employee worked, sum up the salaries in that month and the previous two months. This is their 3-month sum for that month. If an employee did not work for the company in previous months, their effective salary for those months is
0. - Do not include the 3-month sum for the most recent month that the employee worked for in the summary.
- Do not include the 3-month sum for any month the employee did not work.
Return the result table ordered by id in ascending order. In case of a tie, order it by month in descending order.
The result format is in the following example.
Example 1:
Input: Employee table: +----+-------+--------+ | 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 | +----+-------+--------+ Explanation: Employee '1' has five salary records excluding their most recent month '8': - 90 for month '7'. - 60 for month '4'. - 40 for month '3'. - 30 for month '2'. - 20 for month '1'. So the cumulative salary summary for this employee is: +----+-------+--------+ | id | month | salary | +----+-------+--------+ | 1 | 7 | 90 | (90 + 0 + 0) | 1 | 4 | 130 | (60 + 40 + 30) | 1 | 3 | 90 | (40 + 30 + 20) | 1 | 2 | 50 | (30 + 20 + 0) | 1 | 1 | 20 | (20 + 0 + 0) +----+-------+--------+ Note that the 3-month sum for month '7' is 90 because they did not work during month '6' or month '5'. Employee '2' only has one salary record (month '1') excluding their most recent month '2'. +----+-------+--------+ | id | month | salary | +----+-------+--------+ | 2 | 1 | 20 | (20 + 0 + 0) +----+-------+--------+ Employee '3' has two salary records excluding their most recent month '4': - 60 for month '3'. - 40 for month '2'. So the cumulative salary summary for this employee is: +----+-------+--------+ | id | month | salary | +----+-------+--------+ | 3 | 3 | 100 | (60 + 40 + 0) | 3 | 2 | 40 | (40 + 0 + 0) +----+-------+--------+
Approach Overview
Problem Overview: You have an Employee table with id, month, and salary. For every employee and month, compute the cumulative salary for that month plus the previous two months. The most recent month for each employee is excluded because future months may change the rolling total.
Approach 1: Self Join Rolling Window (O(n log n) time, O(1) extra space)
Join the table with itself to simulate a rolling three‑month window. Treat one instance (e1) as the current row and the other (e2) as rows contributing to the cumulative sum. Match rows where e1.id = e2.id and e2.month falls in the range e1.month - 2 to e1.month. Aggregate with SUM(e2.salary) and group by e1.id and e1.month. Finally, filter out the latest month for each employee using a subquery that checks MAX(month). This approach works in nearly every SQL engine and demonstrates how to simulate a sliding window using joins. It relies on efficient indexing and grouping operations commonly discussed in database query optimization.
Approach 2: Window Function with SUM OVER (O(n log n) time, O(1) space)
Modern SQL engines support window functions, which simplify rolling calculations. Partition the rows by id and order them by month. Use SUM(salary) OVER (PARTITION BY id ORDER BY month ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) to compute the cumulative salary for the last three months. After computing the rolling total, exclude the most recent month per employee using a condition comparing month with the partition's maximum month. This version avoids explicit joins and is usually easier to read and maintain. Window functions are a common advanced pattern in SQL and analytical queries involving database aggregations.
Recommended for interviews: The self‑join solution shows you understand how to build rolling aggregates without advanced SQL features. Interviewers often accept it because it works across many database systems. The window function version is cleaner and closer to how production analytics queries are written. Demonstrating both approaches signals strong SQL fundamentals and familiarity with modern query capabilities.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self Join Rolling Window | O(n log n) | O(1) | When window functions are unavailable or when demonstrating SQL fundamentals in interviews |
| Window Function (SUM OVER) | O(n log n) | O(1) | Preferred for modern SQL engines like MySQL 8+, PostgreSQL, and analytical queries |