LeetCode 1468 - Calculate Salaries

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the post tax salary for every employee in the Salaries table. However, the tax rate is not determined individually for each employee. Instead, the tax rate is determined at the company level, based on the maximum salary within that company.

Each row in the input table represents an employee and contains four pieces of information:

company_id, identifying which company the employee belongs to
employee_id, uniquely identifying an employee within a company
employee_name, the employee's name
salary, the employee's original salary before taxes

The key detail is that the tax rate applied to all employees in a company depends on the highest salary earned by any employee in that company.

The tax rules are:

If the maximum salary in a company is less than 1000, then no tax is applied, meaning the tax rate is 0%.
If the maximum salary is between 1000 and 10000, inclusive, then the tax rate is 24%.
If the maximum salary exceeds 10000, then the tax rate is 49%.

After identifying the correct tax rate for a company, we apply it to every employee in that company using the formula:

$$\text{new salary} = \text{salary} - (\text{salary} \times \text{tax rate})$$

The resulting salary must be rounded to the nearest integer.

The output should contain the same employee information, but with the updated salary after taxes.

Since this is a database problem, we are expected to write an SQL query rather than implement an algorithm in a traditional programming language. The main challenge is efficiently determining each company's maximum salary and then applying the appropriate tax rate to all employees.

An important observation is that every employee in a company shares the same tax bracket. Therefore, recomputing the tax classification separately for each employee would be wasteful.

Several edge cases are important:

A company may contain only one employee. In that case, that employee's salary determines the tax bracket.
Boundary values matter because the ranges are inclusive. A company with a maximum salary exactly 1000 or exactly 10000 should receive the 24% tax rate.
Salaries after taxation may contain decimal values, so proper rounding is necessary. For example, 5910.52 becomes 5911.
Companies with salaries below 1000 should remain unchanged because the tax rate is 0%.

Approaches

Brute Force Approach

A brute force approach would determine the company tax rate separately for every employee.

For each employee row, we could run a subquery to compute the maximum salary for that employee's company. Once we have the company maximum salary, we determine the tax percentage and compute the adjusted salary.

Conceptually, this works because every employee independently derives the correct company tax information. However, it is inefficient because the maximum salary of a company is recomputed repeatedly for employees in the same company.

For example, if a company has 1,000 employees, the same maximum salary calculation would be executed 1,000 times. This redundancy makes the query unnecessarily expensive.

Optimal Approach

The key insight is that the tax rate depends only on the maximum salary per company, and this value is shared among all employees in the company.

Instead of recomputing the maximum salary repeatedly, we first calculate the maximum salary for each company once using aggregation (GROUP BY company_id with MAX(salary)).

After obtaining the maximum salary for every company, we join this information back to the original Salaries table. Once joined, every employee row has access to its company's maximum salary, allowing us to determine the correct tax bracket and compute the adjusted salary.

This approach avoids redundant computation and scales efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes company maximum salary for each employee
Optimal	O(n)	O(c)	Computes company maximum once per company

Here, n is the number of employees and c is the number of companies.

Algorithm Walkthrough

Step by Step Process

Group employees by company_id and compute the maximum salary for each company using MAX(salary).
For each company, determine the tax bracket:

< 1000 → 0%
1000 to 10000 → 24%
> 10000 → 49%

Join the computed company information back to the Salaries table so every employee row has access to its company's tax rate.
Compute the post tax salary using:

$$\text{salary} \times (1 - \text{tax rate})$$ 5. Round the computed value to the nearest integer using ROUND(). 6. Return the required columns:

company_id
employee_id
employee_name
adjusted salary

Why it works

The correctness comes from the fact that all employees in a company share the same tax rate, which depends solely on the company's maximum salary. By computing the maximum salary exactly once per company and joining it back, every employee receives the correct tax bracket. Since the salary adjustment formula is applied consistently and rounded appropriately, the final output satisfies the problem requirements.

SQL Solution

WITH CompanyTax AS (
    SELECT
        company_id,
        CASE
            WHEN MAX(salary) < 1000 THEN 0
            WHEN MAX(salary) <= 10000 THEN 24
            ELSE 49
        END AS tax_rate
    FROM Salaries
    GROUP BY company_id
)

SELECT
    s.company_id,
    s.employee_id,
    s.employee_name,
    ROUND(s.salary * (100 - ct.tax_rate) / 100) AS salary
FROM Salaries s
JOIN CompanyTax ct
    ON s.company_id = ct.company_id;

Implementation Explanation

The query begins with a Common Table Expression named CompanyTax. This intermediate result calculates the tax rate for every company.

We group rows by company_id and compute MAX(salary). The CASE expression converts the company maximum salary into the appropriate tax percentage.

Next, we join CompanyTax back to Salaries using company_id. This gives every employee access to the tax rate for their company.

Finally, the adjusted salary is computed using:

$$\text{salary} \times \frac{100 - \text{tax rate}}{100}$$

The ROUND() function ensures salaries are rounded to the nearest integer, exactly as required.

Worked Examples

Example 1

Input:

company_id	employee_id	employee_name	salary
1	1	Tony	2000
1	2	Pronub	21300
1	3	Tyrrox	10800
2	1	Pam	300
2	7	Bassem	450
2	9	Hermione	700
3	7	Bocaben	100
3	2	Ognjen	2200
3	13	Nyancat	3300
3	15	Morninngcat	7777

Step 1: Compute Company Maximum Salaries

company_id	max_salary
1	21300
2	700
3	7777

Step 2: Determine Tax Rates

company_id	max_salary	tax_rate
1	21300	49
2	700	0
3	7777	24

Step 3: Compute Adjusted Salaries

company_id	employee	original salary	tax	adjusted salary
1	Tony	2000	49%	1020
1	Pronub	21300	49%	10863
1	Tyrrox	10800	49%	5508
2	Pam	300	0%	300
2	Bassem	450	0%	450
2	Hermione	700	0%	700
3	Bocaben	100	24%	76
3	Ognjen	2200	24%	1672
3	Nyancat	3300	24%	2508
3	Morninngcat	7777	24%	5911

The final result matches the expected output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to compute company maximum salaries and one join over employees
Space	O(c)	Stores one aggregated row per company

The query scans the Salaries table to compute company maximum salaries. Then it performs a join with the original table. Since each employee row is processed a constant number of times, the total work is linear in the number of employees.

Test Cases

Although LeetCode Database problems are solved using SQL rather than asserts, we can still describe representative scenarios that validate correctness.

# Company below 1000, no tax
# max salary = 700 -> 0% tax
assert True

# Boundary case: max salary exactly 1000
# should apply 24% tax
assert True

# Boundary case: max salary exactly 10000
# should apply 24% tax
assert True

# Company above 10000
# should apply 49% tax
assert True

# Single employee company
# employee determines tax bracket
assert True

# Rounding test
# 7777 * 0.76 = 5910.52 -> 5911
assert True

Test	Why
Company max salary < 1000	Verifies 0% tax case
Max salary = 1000	Verifies lower boundary inclusion
Max salary = 10000	Verifies upper boundary inclusion
Max salary > 10000	Verifies 49% bracket
Single employee company	Ensures grouping logic works with one row
Decimal rounding case	Validates nearest integer behavior

Edge Cases

Company With Exactly 1000 or 10000 Maximum Salary

Boundary conditions are common sources of mistakes. A naive implementation might incorrectly use < 10000 instead of <= 10000, which would place companies with a maximum salary of exactly 10000 into the wrong tax bracket. The CASE statement explicitly handles inclusivity by using <= 10000.

Company With Only One Employee

Some implementations accidentally assume multiple employees exist per company. Since the maximum salary for a single employee company is simply that employee's salary, the aggregation still behaves correctly. The GROUP BY operation naturally supports this case.

Rounding Decimal Salaries

Tax calculations often produce fractional values. Without rounding, results would not match the expected output format. Using ROUND() ensures values such as 5910.52 correctly become 5911.

No Tax Companies

Companies whose maximum salary is below 1000 should keep original salaries unchanged. By assigning a 0% tax rate, the formula naturally preserves the original salary without requiring any special case logic.