LeetCode 2010 - The Number of Seniors and Juniors to Join the Company II

LeetCode Problem 2010

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem asks us to simulate a hiring process with a fixed salary budget of $70,000, where candidates are classified as either "Senior" or "Junior" and each has a unique salary. The hiring rules are strict: we must first attempt to hire as many seniors as possible, always picking the one with the smallest salary first, until we can no longer afford any more seniors. After that, the remaining budget is used to hire juniors, also starting with the smallest salary and hiring until the budget runs out. The goal is to return a table of employee_ids representing the candidates who are hired.

The input is a table Candidates with three columns: employee_id (unique identifier), experience (either 'Senior' or 'Junior'), and salary (unique integer). The output is a list of employee_ids of hired candidates. Edge cases include scenarios where no seniors can be hired, or no juniors can be hired after hiring seniors, and cases where the budget allows hiring all candidates.

Important guarantees and constraints are that salaries are unique, and the budget is fixed at $70,000. This makes sorting by salary straightforward without worrying about ties. We must also consider cases where the budget is insufficient to hire any candidate of a particular type.

Approaches

The brute-force approach is straightforward: iterate through all seniors sorted by salary, subtracting their salary from the budget until it becomes impossible to hire another senior. Then repeat the same process for juniors with the remaining budget. While this is simple, it relies on sorting both groups of candidates separately, which is the key to optimizing it.

The optimal solution leverages the fact that we only need to sort seniors and juniors individually by salary, then perform a linear scan to pick candidates until the budget is exhausted. Sorting ensures that we always pick the cheapest candidates first, which satisfies the hiring criteria. This approach avoids unnecessary repeated budget checks or nested loops.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sort seniors and juniors by salary, iterate to hire until budget runs out
Optimal	O(n log n)	O(n)	Same as brute-force since sorting is necessary, linear scan after sorting

Algorithm Walkthrough

Separate the candidates into two lists based on experience: one for seniors and one for juniors. This ensures we follow the rule of hiring seniors first.
Sort both lists by salary in ascending order. Sorting guarantees that we always pick the lowest-cost candidate first, which maximizes the number of hires.
Initialize a variable remaining_budget to 70,000 to track how much we can spend.
Initialize an empty list hired_ids to store the employee_ids of hired candidates.
Iterate over the sorted list of seniors. For each senior, check if their salary is less than or equal to remaining_budget. If yes, append their employee_id to hired_ids and subtract their salary from remaining_budget. Stop when no more seniors can be afforded.
Iterate over the sorted list of juniors. For each junior, check if their salary is less than or equal to remaining_budget. If yes, append their employee_id to hired_ids and subtract their salary from remaining_budget. Stop when no more juniors can be afforded.
Return hired_ids as the final result.

Why it works: Sorting by salary ensures that we always hire the cheapest candidate first, maximizing the number of hires under the budget constraint. By processing seniors before juniors, we respect the hiring priority rules. Linear scans after sorting ensure efficient selection.

Python Solution

import pandas as pd

class Solution:
    def hiredEmployees(self, candidates: pd.DataFrame) -> pd.DataFrame:
        budget = 70000
        hired_ids = []

        seniors = candidates[candidates['experience'] == 'Senior'].sort_values('salary')
        juniors = candidates[candidates['experience'] == 'Junior'].sort_values('salary')

        for _, row in seniors.iterrows():
            if row['salary'] <= budget:
                hired_ids.append(row['employee_id'])
                budget -= row['salary']

        for _, row in juniors.iterrows():
            if row['salary'] <= budget:
                hired_ids.append(row['employee_id'])
                budget -= row['salary']

        return pd.DataFrame({'employee_id': hired_ids})

The Python implementation uses pandas to filter and sort the candidates efficiently. We first separate seniors and juniors, sort by salary, then iterate to hire within budget. The iterrows() function is used for clear and readable iteration over the DataFrame rows.

Go Solution

package main

import (
    "sort"
)

type Candidate struct {
    EmployeeID int
    Experience string
    Salary     int
}

func HiredEmployees(candidates []Candidate) []int {
    budget := 70000
    var hiredIDs []int

    var seniors, juniors []Candidate
    for _, c := range candidates {
        if c.Experience == "Senior" {
            seniors = append(seniors, c)
        } else {
            juniors = append(juniors, c)
        }
    }

    sort.Slice(seniors, func(i, j int) bool {
        return seniors[i].Salary < seniors[j].Salary
    })
    sort.Slice(juniors, func(i, j int) bool {
        return juniors[i].Salary < juniors[j].Salary
    })

    for _, s := range seniors {
        if s.Salary <= budget {
            hiredIDs = append(hiredIDs, s.EmployeeID)
            budget -= s.Salary
        }
    }

    for _, j := range juniors {
        if j.Salary <= budget {
            hiredIDs = append(hiredIDs, j.EmployeeID)
            budget -= j.Salary
        }
    }

    return hiredIDs
}

In Go, slices are used to store the filtered candidates. Sorting is done using sort.Slice with a custom comparator. The rest of the logic mirrors Python: iterate through sorted seniors first, then juniors, adjusting the budget accordingly.

Worked Examples

Example 1 Step-by-Step

Initial budget: 70000

Seniors sorted by salary: [(11, 16000), (2, 20000), (13, 50000)]

Juniors sorted by salary: [(1, 10000), (9, 15000), (4, 40000)]

Hired seniors:

Hire 11 → budget 70000-16000=54000
Hire 2 → budget 54000-20000=34000
Cannot hire 13 → salary 50000 > 34000

Hired juniors:

Hire 1 → budget 34000-10000=24000
Hire 9 → budget 24000-15000=9000
Cannot hire 4 → salary 40000 > 9000

Final hired IDs: [11, 2, 1, 9]

Example 2 Step-by-Step

Initial budget: 70000

Seniors sorted by salary: [(11, 80000), (2, 85000), (13, 90000)]

Juniors sorted by salary: [(9, 10000), (1, 25000), (4, 30000)]

Hired seniors: None (all > 70000)

Hired juniors:

Hire 9 → budget 70000-10000=60000
Hire 1 → budget 60000-25000=35000
Hire 4 → budget 35000-30000=5000

Final hired IDs: [9, 1, 4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting seniors and juniors dominates the time; iterating is O(n)
Space	O(n)	Storing separate lists for seniors and juniors and the output list

Sorting is necessary to ensure we always hire the lowest-salary candidates first. Iterating over the sorted lists is linear, making the total time O(n log n).

Test Cases

import pandas as pd

# Example 1
candidates1 = pd.DataFrame({
    'employee_id': [1, 9, 2, 11, 13, 4],
    'experience': ['Junior', 'Junior', 'Senior', 'Senior', 'Senior', 'Junior'],
    'salary': [10000, 15000, 20000, 16000, 50000, 40000]
})
sol = Solution()
assert set(sol.hiredEmployees(candidates1)['employee_id']) == {11, 2, 1, 9}  # mix of seniors and juniors

# Example 2
candidates2 = pd.DataFrame({
    'employee_id': [1, 9, 2, 11, 13, 4],
    'experience': ['Junior', 'Junior', 'Senior', 'Senior', 'Senior', 'Junior'],
    'salary': [25000, 10000, 85000, 80000, 90000, 30000]
})
assert set(sol.hiredEmployees(candidates2)['employee_id']) == {9, 1, 4}  # only juniors

# Edge case: no seniors can be hired
candidates3 = pd.DataFrame({
    'employee_id': [1, 2],
    'experience': ['Senior', 'Junior'],
    'salary': [80000, 50000]
})
assert set(sol.hiredEmployees(candidates