LeetCode 569: Median Employee Salary Solution in Python – A Step-by-Step Guide

Imagine you’re an HR analyst handed a list of employee salaries across different companies—like [(1, 100), (1, 200), (2, 150)]—and your task is to find the median salary for each company, such as 150 for company 1 and 150 for company 2, ensuring you handle odd and even counts correctly. That’s the engaging challenge of LeetCode 569: Median Employee Salary, a medium-level problem that’s a fantastic way to practice data processing in Python. We’ll explore two solutions: the Best Solution, a sorting approach with group handling that’s efficient and clear, and an Alternative Solution, a brute-force frequency counting method that’s thorough but less practical. With detailed examples, clear code, and a friendly tone—especially for the sorting approach—this guide will help you calculate those medians, whether you’re new to coding or leveling up. Let’s crunch those salaries and start sorting!

What Is LeetCode 569: Median Employee Salary?

In LeetCode 569: Median Employee Salary, you’re given a list of tuples salaries where each tuple (company_id, salary) represents an employee’s salary at a specific company, and your task is to return a dictionary mapping each company_id to its median salary. The median is the middle value in a sorted list (if odd count) or the average of the two middle values (if even count). For example, with salaries = [(1, 100), (1, 200), (2, 150)], the result is {1: 150, 2: 150}. This problem builds on LeetCode 347: Top K Frequent Elements for grouping but focuses on median computation within groups.

Problem Statement

Input: salaries (List[Tuple[int, int]])—list of (company_id, salary) tuples.
Output: Dict[int, float]—mapping of company_id to median salary.
Rules: Median is middle value (odd count) or average of two middle values (even count); handle all companies.

Constraints

1 <= salaries.length <= 10⁵
1 <= company_id <= 100
1 <= salary <= 10⁴

Examples

Input: salaries = [(1,100),(1,200),(2,150)]

Output: {1: 150, 2: 150}
Company 1: [100, 200] → 150; Company 2: [150] → 150.

Input: salaries = [(1,100),(1,200),(1,300),(2,400)]

Output: {1: 200, 2: 400}
Company 1: [100, 200, 300] → 200; Company 2: [400] → 400.

Input: salaries = [(1,500),(2,500)]

Output: {1: 500, 2: 500}
Single salaries per company.

Understanding the Problem: Computing Median Salaries

To solve LeetCode 569: Median Employee Salary in Python, we need to group salaries by company ID, sort each group, and compute the median for each, returning a dictionary of results. With up to 10⁵ salaries and 100 companies, a brute-force approach counting frequencies for each salary could work but might be inefficient for large ranges. Instead, sorting within groups leverages Python’s built-in efficiency for a cleaner solution. We’ll explore:

Best Solution (Sorting with Group Handling): O(n log n) time, O(n) space—fast and optimal (n = number of salaries).
Alternative Solution (Brute-Force Frequency Counting): O(n * s) time, O(s) space (s = salary range)—simple but less scalable.

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

Best Solution: Sorting with Group Handling

Why Sorting Wins

The sorting with group handling solution is the best for LeetCode 569 because it computes medians efficiently in O(n log n) time and O(n) space by grouping salaries by company using a dictionary, sorting each group, and calculating medians directly, avoiding unnecessary frequency counting across a wide salary range. It’s like organizing employee pay stubs by company, lining them up, and picking the middle value—all in a neat, streamlined process!

How It Works

Think of this as a salary-sorting maestro:

Step 1: Group Salaries:

Use a dictionary to map company_id to a list of salaries.

Step 2: Sort Each Group:

Sort each company’s salary list in ascending order.

Step 3: Compute Medians:

For each company:

Odd count: Take middle element.
Even count: Average two middle elements.

Step 4: Build Result:

Map each company_id to its median in a dictionary.

Step 5: Return Result:

Dictionary of medians.

Why It Works:

Sorting ensures median is easily accessible.
Grouping avoids redundant processing.

It’s like a median-salary calculator!

Step-by-Step Example

Example: salaries = [(1,100),(1,200),(2,150)]

Step 1: Group:

groups = {1: [100, 200], 2: [150]}.

Step 2: Sort:

groups = {1: [100, 200], 2: [150]} (already sorted).

Step 3: Compute medians:

Company 1: [100, 200], length = 2, median = (100 + 200) / 2 = 150.
Company 2: [150], length = 1, median = 150.

Step 4: Result: {1: 150, 2: 150}.
Result: {1: 150, 2: 150}.

Example: salaries = [(1,100),(1,200),(1,300),(2,400)]

Step 1: Group:

groups = {1: [100, 200, 300], 2: [400]}.

Step 2: Sort:

groups = {1: [100, 200, 300], 2: [400]}.

Step 3: Medians:

Company 1: [100, 200, 300], length = 3, median = 200.
Company 2: [400], length = 1, median = 400.

Step 4: Result: {1: 200, 2: 400}.
Result: {1: 200, 2: 400}.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def medianSalary(self, salaries: List[Tuple[int, int]]) -> Dict[int, float]:
        # Step 1: Group salaries by company_id
        groups = {}
        for company_id, salary in salaries:
            if company_id not in groups:
                groups[company_id] = []
            groups[company_id].append(salary)

        # Step 2: Compute median for each company
        result = {}
        for company_id, salary_list in groups.items():
            salary_list.sort()  # Sort in ascending order
            n = len(salary_list)
            if n % 2 == 0:  # Even number of salaries
                mid1 = n // 2 - 1
                mid2 = n // 2
                median = (salary_list[mid1] + salary_list[mid2]) / 2
            else:  # Odd number of salaries
                median = salary_list[n // 2]
            result[company_id] = float(median)  # Ensure float output

        # Step 3: Return result dictionary
        return result

Lines 4-8: Build dictionary mapping company_id to salary list.
Lines 11-20: For each company:

Sort salaries.
Compute median: average of two middle (even) or middle (odd).

Line 23: Return dictionary of medians.
Time Complexity: O(n log n)—sorting dominates (n = total salaries).
Space Complexity: O(n)—group storage.

It’s like a salary-median maestro!

Alternative Solution: Brute-Force Frequency Counting

Why an Alternative Approach?

The brute-force frequency counting approach counts occurrences of each salary per company, then finds the median by scanning frequencies, running in O(n * s) time and O(s) space (s = salary range, e.g., 10⁴). It’s straightforward but less efficient for large ranges, making it a good baseline for small salary ranges or understanding.

How It Works

Picture this as a salary-frequency counter:

Step 1: Group salaries and count frequencies per company.
Step 2: For each company, scan frequencies to find median position.
Step 3: Compute median from frequency data.
Step 4: Return result dictionary.

It’s like a frequency-based median finder!

Step-by-Step Example

Example: salaries = [(1,100),(1,200),(2,150)]

Step 1: Group frequencies:

groups = {1: {100: 1, 200: 1}, 2: {150: 1}}.

Step 2: Medians:

Company 1: Total = 2, median pos = 1, scan: 100 (1), 200 (2) → 150 (avg).
Company 2: Total = 1, median pos = 0, scan: 150 (1) → 150.

Result: {1: 150, 2: 150}.

Code for Brute-Force Approach

class Solution:
    def medianSalary(self, salaries: List[Tuple[int, int]]) -> Dict[int, float]:
        # Step 1: Group and count frequencies
        groups = {}
        for company_id, salary in salaries:
            if company_id not in groups:
                groups[company_id] = {}
            groups[company_id][salary] = groups[company_id].get(salary, 0) + 1

        # Step 2: Compute median for each company
        result = {}
        for company_id, freq in groups.items():
            total = sum(freq.values())
            target = (total + 1) // 2 if total % 2 else total // 2
            count = 0
            prev_salary = 0
            for salary in sorted(freq.keys()):
                count += freq[salary]
                if count >= target:
                    if total % 2:
                        median = salary
                    else:
                        if count == target:
                            next_salary = next(iter(sorted([s for s in freq.keys() if s > salary])), None)
                            median = (salary + next_salary) / 2 if next_salary else salary
                        else:
                            median = salary
                    break
                prev_salary = salary
            result[company_id] = float(median)

        return result

Lines 4-8: Build frequency dictionary per company.
Lines 11-27: Compute median by scanning sorted salaries.
Line 29: Return result.
Time Complexity: O(n * s)—sorting and scanning salary range.
Space Complexity: O(s)—frequency storage.

It’s a frequency-counting median seeker!

Comparing the Two Solutions

Sorting (Best):

Pros: O(n log n), O(n), fast.
Cons: Sorting overhead.

Frequency Counting (Alternative):

Pros: O(n * s), O(s), simple.
Cons: Scales with salary range.

Sorting wins for efficiency!

Additional Examples and Edge Cases

[(1,100)]: {1: 100}.
[(1,200),(1,200)]: {1: 200}.
Empty list: {} (assume handled).

Sorting handles them all!

Complexity Recap

Sorting: Time O(n log n), Space O(n).
Frequency Counting: Time O(n * s), Space O(s).

Sorting’s the speed champ!

Key Takeaways

Sorting: Group finesse—learn at Python Basics!
Frequency: Count clarity.
Salaries: Medians are fun.
Python: Sort or count, your pick!

Final Thoughts: Calculate That Median!

LeetCode 569: Median Employee Salary in Python is a clever data challenge. Sorting with group handling is your fast track, while frequency counting offers a thorough dive. Want more? Try LeetCode 347: Top K Frequent Elements or LeetCode 215: Kth Largest Element. Ready to crunch? Head to Solve LeetCode 569 on LeetCode and find those medians today!