LeetCode 2303 - Calculate Amount Paid in Taxes

This problem is asking us to simulate a progressive tax system. We are given a list of tax brackets where each bracket specifies an upper bound of income and a tax percentage.

leetcodeeasyarraysimulation

LeetCode Problem 2303

Difficulty: 🟢 Easy
Topics: Array, Simulation

Solution

Problem Understanding

This problem is asking us to simulate a progressive tax system. We are given a list of tax brackets where each bracket specifies an upper bound of income and a tax percentage. Our task is to compute the total tax owed for a given income, taking into account that each bracket only taxes the portion of income within that bracket.

In other words, the first bracket taxes the first upper0 dollars at percent0, the second bracket taxes the next upper1 - upper0 dollars at percent1, and so on. The brackets are sorted by their upper bounds, and the last bracket will always cover the total income. The expected output is a floating-point number representing the total taxes owed, accurate to within 10^-5.

The constraints tell us the input size is small: at most 100 brackets and income up to 1000. This ensures that even a simple loop-based solution will run efficiently. Important edge cases include having zero income, a zero percent tax bracket, or an income that ends exactly on a bracket boundary. The problem guarantees unique upper bounds and that the last bracket covers the income, so we do not need to handle missing coverage.

Approaches

The brute-force approach would be to simulate the tax for each individual dollar of income. For each dollar from 1 to income, we would find which bracket it belongs to and add the corresponding tax. While this is conceptually simple, it is unnecessary because we can calculate the tax for an entire bracket at once using arithmetic, avoiding per-dollar computation.

The optimal approach leverages the fact that each bracket only taxes income up to its upper bound. For each bracket, we compute the taxable amount as the minimum of the bracket width (upperi - upperi-1) and the remaining income. Multiply that by the tax rate, accumulate the total tax, and stop when all income is processed.

Approach Time Complexity Space Complexity Notes
Brute Force O(income * n) O(1) Simulates tax per dollar, inefficient for large income
Optimal O(n) O(1) Processes each bracket directly and accumulates tax

Algorithm Walkthrough

  1. Initialize a variable tax to 0 to store the total tax owed.
  2. Initialize a variable prev_upper to 0 to keep track of the upper bound of the previous bracket.
  3. Loop through each bracket [upper, percent] in the list of brackets.
  4. For the current bracket, calculate taxable_income as the minimum of income - prev_upper and upper - prev_upper. This ensures we only tax the income that falls within this bracket.
  5. Multiply taxable_income by percent / 100 and add the result to tax.
  6. Update prev_upper to upper to move to the next bracket.
  7. If prev_upper reaches or exceeds income, break out of the loop because all income has been taxed.
  8. Return tax as the final amount owed.

Why it works: At each step, we accurately compute the portion of income that falls within the current bracket and apply the correct rate. Because brackets are sorted and cover the entire income, this guarantees we account for all income exactly once.

Python Solution

from typing import List

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        tax = 0.0
        prev_upper = 0
        
        for upper, percent in brackets:
            if income <= prev_upper:
                break
            taxable_income = min(income - prev_upper, upper - prev_upper)
            tax += taxable_income * (percent / 100)
            prev_upper = upper
        
        return tax

In this implementation, tax accumulates the total tax owed. The prev_upper variable tracks the upper bound of the last bracket to calculate the income slice within the current bracket. We compute the taxable portion using min to handle cases where the income does not fully cover the bracket. The loop terminates early if all income has been taxed.

Go Solution

func calculateTax(brackets [][]int, income int) float64 {
    tax := 0.0
    prevUpper := 0

    for _, bracket := range brackets {
        upper := bracket[0]
        percent := bracket[1]

        if income <= prevUpper {
            break
        }

        taxableIncome := upper - prevUpper
        if income-prevUpper < taxableIncome {
            taxableIncome = income - prevUpper
        }

        tax += float64(taxableIncome) * float64(percent) / 100.0
        prevUpper = upper
    }

    return tax
}

In Go, we follow the same logic as Python. We convert integers to float64 when computing the tax to avoid integer division issues. The early break ensures we stop once all income has been taxed.

Worked Examples

Example 1: brackets = [[3,50],[7,10],[12,25]], income = 10

Bracket prev_upper Taxable Tax this bracket Total tax
[3,50] 0 min(10-0,3-0)=3 3*0.5=1.5 1.5
[7,10] 3 min(10-3,7-3)=4 4*0.1=0.4 1.9
[12,25] 7 min(10-7,12-7)=3 3*0.25=0.75 2.65

Final tax = 2.65

Example 2: brackets = [[1,0],[4,25],[5,50]], income = 2

Bracket prev_upper Taxable Tax this bracket Total tax
[1,0] 0 min(2-0,1-0)=1 1*0=0 0
[4,25] 1 min(2-1,4-1)=1 1*0.25=0.25 0.25

Final tax = 0.25

Example 3: brackets = [[2,50]], income = 0

Bracket prev_upper Taxable Tax this bracket Total tax
[2,50] 0 min(0-0,2-0)=0 0 0

Final tax = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Loop through each bracket once, n = number of brackets
Space O(1) Only a few variables are used, independent of input size

Since the number of brackets is small, this solution is efficient and direct.

Test Cases

# Provided examples
assert abs(Solution().calculateTax([[3,50],[7,10],[12,25]], 10) - 2.65) < 1e-5  # mixed brackets
assert abs(Solution().calculateTax([[1,0],[4,25],[5,50]], 2) - 0.25) < 1e-5    # zero percent bracket
assert abs(Solution().calculateTax([[2,50]], 0) - 0.0) < 1e-5                  # zero income

# Edge cases
assert abs(Solution().calculateTax([[5,100]], 5) - 5.0) < 1e-5                 # income exactly at bracket
assert abs(Solution().calculateTax([[5,100]], 3) - 3.0) < 1e-5                 # income less than bracket
assert abs(Solution().calculateTax([[1,0],[2,50],[3,100]], 3) - 1.5) < 1e-5    # multiple brackets, exact coverage
Test Why
income spanning multiple brackets verifies correct progressive tax calculation
zero income ensures tax is zero when no income exists
zero percent bracket checks brackets with no tax are handled
income at bracket boundary confirms calculation when income matches bracket upper bound
income within a single bracket verifies partial bracket computation

Edge Cases

The first important edge case is zero income. If income is 0, no tax should be applied. Our algorithm handles this naturally because taxable_income = min(0 - prev_upper, upper - prev_upper) evaluates to 0, and the loop exits without adding any tax.

The second edge case is income exactly at a bracket boundary. If the income equals the upper bound of a bracket, the taxable amount for that bracket is exactly the difference from the previous bracket. The use of min(income - prev_upper, upper - prev_upper) ensures that this is calculated correctly.

The third edge case is a zero percent bracket. A bracket can have a tax rate of 0%, which should contribute 0 tax regardless of the income in that bracket. The algorithm multiplies the taxable income by percent/100, so a 0% bracket naturally contributes nothing to the total tax. This prevents potential division or calculation errors that might occur in naive implementations.