LeetCode 579: Find Cumulative Salary of an Employee Solution in Python – A Step-by-Step Guide

What Is LeetCode 579: Find Cumulative Salary of an Employee?

In LeetCode 579: Find Cumulative Salary of an Employee, you’re given a list of tuples salary_records where each tuple (emp_id, month, salary) represents an employee’s ID, the month (in "YYYY-MM" format), and their salary for that month. Your task is to return a dictionary mapping each emp_id to the cumulative salary of their three highest-earning months. If an employee has fewer than three months, sum all available months. For example, with salary_records = [(1, "2023-01", 1000), (1, "2023-02", 1500), (1, "2023-03", 1200)], the result is {1: 3700}. This problem builds on LeetCode 215: Kth Largest Element in an Array for top-k selection but focuses on grouping and summing by employee.

Problem Statement

• Input: salary_records (List[Tuple[int, str, int]])—list of (emp_id, month, salary).
• Output: Dict[int, int]—mapping of emp_id to cumulative salary of top 3 months.
• Rules: Sum 3 highest salaries per employee; if < 3 months, sum all; months are unique per employee.

Constraints

• 1 <= salary_records.length <= 10⁵
• 1 <= emp_id <= 10⁵
• month in "YYYY-MM" format (e.g., "2023-01")
• 0 <= salary <= 10⁴

Examples

• Input: salary_records = [(1,"2023-01",1000),(1,"2023-02",1500),(1,"2023-03",1200)]
• Output: {1: 3700}
• Top 3: [1500, 1200, 1000], sum = 3700.
• Input: salary_records = [(1,"2023-01",1000),(1,"2023-02",1500),(2,"2023-01",2000)]
• Output: {1: 2500, 2: 2000}
• E1: [1500, 1000], sum = 2500; E2: [2000], sum = 2000.
• Input: salary_records = [(1,"2023-01",500),(1,"2023-02",500),(1,"2023-03",500),(1,"2023-04",500)]
• Output: {1: 1500}
• Top 3: [500, 500, 500], sum = 1500.

Understanding the Problem: Summing Top Salaries

To solve LeetCode 579: Find Cumulative Salary of an Employee in Python, we need to group salary records by emp_id, sort each employee’s salaries, and compute the cumulative sum of their three highest months (or all if fewer than three), returning a dictionary with these totals, handling up to 10⁵ records efficiently. A brute-force approach scanning the list repeatedly for each employee (O(n²)) could work but would be slow. Instead, a dictionary-based grouping followed by sorting optimizes this to O(n log n), leveraging Python’s efficient sorting. We’ll explore:

• Best Solution (Sorting with Cumulative Sum): O(n log n) time, O(n) space—fast and optimal (n = number of records).
• Alternative Solution (Brute-Force Traversal): O(n²) time, O(1) space—simple but slow.

Let’s dive into the sorting solution with a friendly breakdown!

Best Solution: Sorting with Cumulative Sum

Why Sorting Wins

The sorting with cumulative sum solution is the best for LeetCode 579 because it computes the cumulative salaries in O(n log n) time and O(n) space by grouping records by employee ID using a dictionary, sorting each group’s salaries in descending order, and summing the top three in a single pass per group, avoiding redundant traversals. It’s like organizing an employee’s pay stubs, ranking them by value, and totaling the top three—all in a neat, efficient process!

How It Works

Think of this as a salary-sorting maestro:

• Step 1: Group Records:
• Use a dictionary to map emp_id to a list of salaries.
• Step 2: Sort Salaries:
• For each employee, sort their salaries in descending order.
• Step 3: Compute Cumulative Sum:
• Take top 3 salaries (or all if < 3), sum them.
• Step 4: Build Result:
• Map each emp_id to its cumulative sum.
• Step 5: Return Result:
• Dictionary of cumulative salaries.
• Why It Works:
• Sorting ensures top 3 are easily accessed.
• Grouping avoids redundant scans.

It’s like a top-salary calculator!

Step-by-Step Example

Example: salary_records = [(1,"2023-01",1000),(1,"2023-02",1500),(1,"2023-03",1200)]

• Step 1: Group:
• groups = {1: [1000, 1500, 1200]}.
• Step 2: Sort:
• groups = {1: [1500, 1200, 1000]}.
• Step 3: Sum top 3:
• E1: [1500, 1200, 1000], sum = 3700.
• Step 4: Result: {1: 3700}.
• Result: {1: 3700}.

Example: salary_records = [(1,"2023-01",1000),(1,"2023-02",1500),(2,"2023-01",2000)]

• Step 1: Group:
• groups = {1: [1000, 1500], 2: [2000]}.
• Step 2: Sort:
• groups = {1: [1500, 1000], 2: [2000]}.
• Step 3: Sum:
• E1: [1500, 1000], sum = 2500 (only 2 months).
• E2: [2000], sum = 2000.
• Step 4: Result: {1: 2500, 2: 2000}.
• Result: {1: 2500, 2: 2000}.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

from typing import List, Tuple

class Solution:
    def findCumulativeSalary(self, salary_records: List[Tuple[int, str, int]]) -> dict[int, int]:
        # Step 1: Group salaries by employee ID
        groups = {}
        for emp_id, _, salary in salary_records:
            if emp_id not in groups:
                groups[emp_id] = []
            groups[emp_id].append(salary)

        # Step 2: Compute cumulative sum for top 3
        result = {}
        for emp_id, salaries in groups.items():
            salaries.sort(reverse=True)  # Sort descending
            # Take top 3 or all if less than 3
            top_salaries = salaries[:min(3, len(salaries))]
            result[emp_id] = sum(top_salaries)

        # Step 3: Return result dictionary
        return result

• Lines 6-11: Build dictionary mapping emp_id to salary list.
• Lines 14-18: For each employee:
• Sort salaries in descending order.
• Sum top 3 (or all if < 3).
• Line 21: Return dictionary of sums.
• Time Complexity: O(n log n)—sorting dominates (n = total records).
• Space Complexity: O(n)—group storage.

It’s like a salary-sum wizard!

Alternative Solution: Brute-Force Traversal

Why an Alternative Approach?

The brute-force traversal approach identifies unique employee IDs, then scans the list repeatedly to collect and sort their salaries, running in O(n²) time and O(1) space (excluding output). It’s simple but inefficient for large lists, making it a good baseline for small datasets or understanding.

How It Works

Picture this as a salary-scanning seeker:

• Step 1: Get unique employee IDs.
• Step 2: For each ID, scan list to collect salaries.
• Step 3: Sort and sum top 3 salaries.
• Step 4: Return result dictionary.

It’s like a salary-collecting explorer!

Step-by-Step Example

Example: salary_records = [(1,"2023-01",1000),(1,"2023-02",1500)]

• Step 1: Unique IDs: [1].
• Step 2: Collect:
• E1: Scan → [1000, 1500].
• Step 3: Sort: [1500, 1000], sum = 2500 (only 2).
• Step 4: Result: {1: 2500}.
• Result: {1: 2500}.

Code for Brute-Force Approach

from typing import List, Tuple

class Solution:
    def findCumulativeSalary(self, salary_records: List[Tuple[int, str, int]]) -> dict[int, int]:
        # Step 1: Get unique employee IDs
        unique_ids = set(emp_id for emp_id, _, _ in salary_records)

        # Step 2: Compute cumulative salary for each employee
        result = {}
        for emp_id in unique_ids:
            salaries = []
            for record_id, _, salary in salary_records:
                if record_id == emp_id:
                    salaries.append(salary)
            salaries.sort(reverse=True)
            top_salaries = salaries[:min(3, len(salaries))]
            result[emp_id] = sum(top_salaries)

        # Step 3: Return result
        return result

• Line 6: Extract unique IDs.
• Lines 9-16: For each ID, collect, sort, sum top 3 salaries.
• Line 19: Return dictionary.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(1)—minimal extra space (excluding output).

It’s a brute-force salary summer!

Comparing the Two Solutions

• Sorting (Best):
• Pros: O(n log n), O(n), fast.
• Cons: Extra space for grouping.
• Brute-Force (Alternative):
• Pros: O(n²), O(1), space-efficient.
• Cons: Slower.

Sorting wins for efficiency!

Additional Examples and Edge Cases

• Single record: Sum of one month.
• Fewer than 3: Sum all available.
• Empty list: Empty dict (assume handled).

Sorting handles them all!

Complexity Recap

• Sorting: Time O(n log n), Space O(n).
• Brute-Force: Time O(n²), Space O(1).

Sorting’s the speed champ!

Key Takeaways

• Sorting: Salary finesse—learn at Python Basics!
• Brute-Force: Scan simplicity.
• Payrolls: Sums are fun.
• Python: Sort or scan, your pick!

Final Thoughts: Tally Those Salaries!

LeetCode 579: Find Cumulative Salary of an Employee in Python is a practical data challenge. Sorting with cumulative sum is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 215: Kth Largest Element or LeetCode 347: Top K Frequent Elements. Ready to crunch? Head to Solve LeetCode 579 on LeetCode and sum those top salaries today!