LeetCode 1873 - Calculate Special Bonus

This problem asks us to write an SQL query that calculates a special bonus for every employee in the Employees table.

leetcodeeasydatabase

LeetCode Problem 1873

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to write an SQL query that calculates a special bonus for every employee in the Employees table.

Each row in the table contains three pieces of information:

Column Meaning
employee_id Unique identifier for the employee
name Employee name
salary Employee salary

The task is to compute a new column called bonus according to two conditions:

  1. The employee's employee_id must be an odd number.
  2. The employee's name must not start with the character 'M'.

If both conditions are true, the employee receives a bonus equal to their full salary, meaning 100% of the salary.

If either condition fails, the employee receives a bonus of 0.

The final output should contain:

Column Meaning
employee_id Employee identifier
bonus Calculated bonus

The results must be ordered by employee_id.

This is fundamentally a conditional transformation problem. For every row, we evaluate a boolean condition and choose between two values:

  • salary
  • 0

The problem is categorized as an Easy database problem because it mainly tests familiarity with:

  • CASE WHEN
  • modulo arithmetic for checking odd/even numbers
  • string pattern matching
  • sorting results

An important detail is the condition involving names that start with 'M'. We only care about the first character of the string. Names such as "Michael" and "Meir" should fail the condition, while names such as "Alice" or "Kannon" should pass.

The problem guarantees that employee_id is unique, so we never need to handle duplicate IDs. Since this is a straightforward row-by-row computation, scalability concerns are minimal.

Some important edge cases include:

  • Employees with even IDs, they always receive 0
  • Employees whose names begin with 'M', they always receive 0
  • Employees satisfying both conditions, they receive their full salary
  • Very small IDs such as 1
  • Single-character names such as "M" or "A"

Because the logic is independent for each row, there are no complicated interactions between records.

Approaches

Brute Force Approach

A brute force approach would conceptually iterate through every employee row one at a time and manually evaluate the two required conditions.

For each employee:

  1. Check whether employee_id is odd.
  2. Check whether the name starts with 'M'.
  3. If both are true, assign the bonus as the salary.
  4. Otherwise, assign 0.

After processing all rows, the results would then be sorted by employee_id.

This approach is correct because every employee is independently evaluated according to the exact rules given in the problem statement.

In a traditional programming environment, this would involve looping through all rows explicitly. In SQL, however, databases are designed for set-based operations, so row-by-row procedural logic is unnecessary and less efficient conceptually.

Optimal Approach

The optimal solution uses SQL's built-in conditional expressions and filtering capabilities directly inside the query.

The key insight is that the bonus computation is entirely deterministic and depends only on the values within a single row. SQL handles this naturally using a CASE expression.

We can:

  • Use employee_id % 2 = 1 to check for odd IDs
  • Use name NOT LIKE 'M%' to ensure the name does not begin with 'M'
  • Use CASE WHEN to return either salary or 0

This allows the database engine to compute the result efficiently in a single pass over the table.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Iterates through all rows and sorts results separately
Optimal O(n log n) O(1) Single SQL query with conditional logic and ordering

The sorting step dominates the runtime because the final result must be ordered by employee_id.

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Start by selecting the employee_id column because it must appear in the final output.
  2. Use a CASE WHEN expression to determine the bonus value for each employee.
  3. Inside the condition, check whether the employee ID is odd using:
employee_id % 2 = 1
  1. Also check whether the employee's name does not start with 'M' using:
name NOT LIKE 'M%'
  1. Combine both conditions with AND because both requirements must be satisfied simultaneously.
  2. If both conditions are true, return the employee's salary as the bonus.
  3. Otherwise, return 0.
  4. Alias the computed value as bonus.
  5. Order the final result by employee_id using:
ORDER BY employee_id

Why it works

The algorithm works because every employee is evaluated independently according to the exact rules specified in the problem. The CASE WHEN expression guarantees that each row receives either the full salary or zero, depending on whether the conditions are satisfied. Since the query processes every row exactly once and sorts the output afterward, the final result is both complete and correctly ordered.

Python Solution

Although this is a database problem, the equivalent Python logic helps illustrate the algorithm clearly.

from typing import List, Dict

class Solution:
    def calculateSpecialBonus(
        self,
        employees: List[Dict[str, int | str]]
    ) -> List[Dict[str, int]]:
        
        result = []

        for employee in employees:
            employee_id = employee["employee_id"]
            name = employee["name"]
            salary = employee["salary"]

            if employee_id % 2 == 1 and not name.startswith("M"):
                bonus = salary
            else:
                bonus = 0

            result.append({
                "employee_id": employee_id,
                "bonus": bonus
            })

        result.sort(key=lambda x: x["employee_id"])

        return result

The implementation follows the algorithm directly.

The loop processes every employee exactly once. For each employee, the code extracts the ID, name, and salary fields. The conditional statement checks whether the ID is odd and whether the name avoids starting with 'M'.

If both conditions hold, the bonus is assigned the employee's salary. Otherwise, the bonus becomes 0.

Each computed result is appended to the output list, and finally the results are sorted by employee_id.

For the actual LeetCode database submission, the SQL query would be:

SELECT
    employee_id,
    CASE
        WHEN employee_id % 2 = 1
             AND name NOT LIKE 'M%'
        THEN salary
        ELSE 0
    END AS bonus
FROM Employees
ORDER BY employee_id;

Go Solution

The following Go implementation mirrors the same logic programmatically.

package main

import (
	"sort"
)

type Employee struct {
	EmployeeID int
	Name       string
	Salary     int
}

type Result struct {
	EmployeeID int
	Bonus      int
}

func calculateSpecialBonus(employees []Employee) []Result {
	results := make([]Result, 0)

	for _, employee := range employees {
		bonus := 0

		if employee.EmployeeID%2 == 1 &&
			(len(employee.Name) == 0 || employee.Name[0] != 'M') {
			bonus = employee.Salary
		}

		results = append(results, Result{
			EmployeeID: employee.EmployeeID,
			Bonus:      bonus,
		})
	}

	sort.Slice(results, func(i, j int) bool {
		return results[i].EmployeeID < results[j].EmployeeID
	})

	return results
}

The Go implementation is very similar to the Python version, but there are a few language-specific differences.

Go uses structs instead of dictionaries for representing employees and results. The sorting step uses sort.Slice with a custom comparison function. String indexing in Go accesses bytes, so checking the first character is done with employee.Name[0] != 'M'.

The implementation also safely handles empty strings by checking len(employee.Name) == 0.

Worked Examples

Example 1

Input table:

employee_id name salary
2 Meir 3000
3 Michael 3800
7 Addilyn 7400
8 Juan 6100
9 Kannon 7700

We evaluate each employee one at a time.

employee_id name Odd ID? Starts with M? Bonus
2 Meir No Yes 0
3 Michael Yes Yes 0
7 Addilyn Yes No 7400
8 Juan No No 0
9 Kannon Yes No 7700

Final output:

employee_id bonus
2 0
3 0
7 7400
8 0
9 7700

Detailed Trace

Employee 2

  • 2 % 2 = 0
  • ID is even
  • Bonus becomes 0

Employee 3

  • 3 % 2 = 1
  • ID is odd
  • Name starts with 'M'
  • Bonus becomes 0

Employee 7

  • 7 % 2 = 1
  • ID is odd
  • Name does not start with 'M'
  • Bonus becomes 7400

Employee 8

  • 8 % 2 = 0
  • ID is even
  • Bonus becomes 0

Employee 9

  • 9 % 2 = 1
  • ID is odd
  • Name does not start with 'M'
  • Bonus becomes 7700

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) We scan all employees once and sort by employee ID
Space O(n) The output list stores one result per employee

The computation itself is linear because each employee is processed exactly once. However, ordering the final results introduces sorting cost, which requires O(n log n) time. The extra space comes from storing the resulting output rows.

In SQL implementations, the database engine may optimize sorting internally, especially if an index exists on employee_id.

Test Cases

from typing import List, Dict

def calculate_special_bonus(employees: List[Dict]) -> List[Dict]:
    result = []

    for employee in employees:
        employee_id = employee["employee_id"]
        name = employee["name"]
        salary = employee["salary"]

        if employee_id % 2 == 1 and not name.startswith("M"):
            bonus = salary
        else:
            bonus = 0

        result.append({
            "employee_id": employee_id,
            "bonus": bonus
        })

    result.sort(key=lambda x: x["employee_id"])
    return result

# Provided example
assert calculate_special_bonus([
    {"employee_id": 2, "name": "Meir", "salary": 3000},
    {"employee_id": 3, "name": "Michael", "salary": 3800},
    {"employee_id": 7, "name": "Addilyn", "salary": 7400},
    {"employee_id": 8, "name": "Juan", "salary": 6100},
    {"employee_id": 9, "name": "Kannon", "salary": 7700},
]) == [
    {"employee_id": 2, "bonus": 0},
    {"employee_id": 3, "bonus": 0},
    {"employee_id": 7, "bonus": 7400},
    {"employee_id": 8, "bonus": 0},
    {"employee_id": 9, "bonus": 7700},
]  # Basic mixed scenario

assert calculate_special_bonus([
    {"employee_id": 1, "name": "Alice", "salary": 5000},
]) == [
    {"employee_id": 1, "bonus": 5000},
]  # Odd ID and valid name

assert calculate_special_bonus([
    {"employee_id": 4, "name": "Bob", "salary": 4000},
]) == [
    {"employee_id": 4, "bonus": 0},
]  # Even ID

assert calculate_special_bonus([
    {"employee_id": 5, "name": "Mary", "salary": 6000},
]) == [
    {"employee_id": 5, "bonus": 0},
]  # Name starts with M

assert calculate_special_bonus([
    {"employee_id": 11, "name": "A", "salary": 100},
]) == [
    {"employee_id": 11, "bonus": 100},
]  # Single character name

assert calculate_special_bonus([
    {"employee_id": 13, "name": "M", "salary": 100},
]) == [
    {"employee_id": 13, "bonus": 0},
]  # Single character M name

assert calculate_special_bonus([]) == []  # Empty input
Test Why
Mixed employee example Validates all major conditions together
Odd ID with normal name Confirms full salary bonus is awarded
Even ID Ensures even IDs receive zero
Name starting with M Ensures name restriction works
Single character non-M name Tests minimal valid name
Single character M name Tests minimal invalid name
Empty input Ensures algorithm handles no rows correctly

Edge Cases

Employees With Even IDs

An employee with an even employee_id must always receive a bonus of 0, regardless of their name. This can be a source of bugs if the implementation checks the name condition first and incorrectly awards the salary. The implementation prevents this by requiring both conditions to be true simultaneously using logical AND.

Names Starting With 'M'

Employees whose names begin with 'M' must receive no bonus, even if their IDs are odd. This edge case is important because developers may accidentally check for the existence of 'M' anywhere in the string rather than specifically at the beginning. Using LIKE 'M%' in SQL and startswith("M") in Python ensures only the first character matters.

Empty or Very Short Names

Short names such as "M" or "A" can expose indexing bugs if the implementation assumes names always contain multiple characters. The solutions handle this safely by using built-in string methods rather than manually indexing without checks.

Empty Input Table

If the table contains no employees, the correct result is simply an empty result set. The implementation naturally handles this because iterating over an empty collection produces no rows, and the final returned result remains empty.