#2303

Easy

LeetCode Problem Workspace

Calculate Amount Paid in Taxes

Calculate the total tax owed by iterating through sorted brackets and applying each rate incrementally to your income.

Problem Statement

You are given a 0-indexed 2D integer array brackets where each element brackets[i] = [upperi, percenti] represents a tax bracket with an upper bound upperi and a tax rate percenti. The brackets are sorted in ascending order by upper bound, meaning upperi-1 < upperi for all valid i.

Given an integer income representing your total earnings, calculate and return the total amount of tax you must pay. Apply each bracket's tax rate only to the portion of income within that bracket. Answers within 10^-5 of the correct value are acceptable.

Examples

Example 1

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

Output: 2.65000

Based on your income, you have 3 dollars in the 1st tax bracket, 4 dollars in the 2nd tax bracket, and 3 dollars in the 3rd tax bracket. The tax rate for the three tax brackets is 50%, 10%, and 25%, respectively. In total, you pay $3 * 50% +$ 4 * 10% + $3 * 25% =$ 2.65 in taxes.

Example 2

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

Output: 0.25000

Based on your income, you have 1 dollar in the 1st tax bracket and 1 dollar in the 2nd tax bracket. The tax rate for the two tax brackets is 0% and 25%, respectively. In total, you pay $1 * 0% +$ 1 * 25% = $0.25 in taxes.

Example 3

Input: brackets = [[2,50]], income = 0

Output: 0.00000

You have no income to tax, so you have to pay a total of $0 in taxes.

Constraints

1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi is sorted in ascending order.
All the values of upperi are unique.
The upper bound of the last tax bracket is greater than or equal to income.

Solution Approach

Iterative Simulation with Previous Bound

Maintain a variable prev to track the previous bracket's upper bound. For each bracket, calculate the taxable income as min(income, upperi) - prev, then multiply by percenti/100 to get the tax for that bracket. Add this to a running total and update prev to upperi.

Early Exit on Full Taxation

If at any bracket your income is less than or equal to the previous upper bound, you can stop iterating. This avoids unnecessary computation for higher brackets that do not apply to your income.

Floating Point Accuracy Handling

Use precise floating point arithmetic to ensure the accumulated tax does not deviate from the expected value. Multiply percentages as decimals and maintain a double or float variable for the running total tax to avoid rounding errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the number of tax brackets, since each bracket is processed once. Space complexity is O(1) because only a few variables like prev and total tax are needed.

What Interviewers Usually Probe

They may ask you to explain why you track the previous bracket's upper bound.
They might probe your handling of income that exactly matches a bracket's upper bound.
They could test understanding of precision by providing rates or income that produce fractional taxes.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract the previous upper bound when calculating the taxable portion in a bracket.
Continuing to compute tax for brackets when income is already fully taxed.
Rounding intermediate calculations instead of maintaining precision until the final total.

Follow-up variants

Compute taxes with brackets given in descending order, requiring sorting first.
Calculate tax when brackets may overlap or have missing ranges, requiring conditional checks.
Determine total after applying deductions before applying the bracketed tax simulation.

FAQ

How do I calculate taxes when income partially fills the last bracket?

Subtract the previous bracket's upper bound from your income within the current bracket, multiply by the rate, and stop accumulating once all income is taxed.

Why track the previous bracket's upper limit in this array simulation?

Tracking prev allows you to compute the taxable portion per bracket correctly, avoiding over-taxing amounts already accounted for.

What if the brackets are not sorted?

You must sort the brackets by upper bound first to ensure the simulation applies tax rates in the correct order.

Can floating point errors affect the final tax?

Yes, use proper decimal arithmetic or floating-point variables to accumulate tax accurately until the final calculation.

Does this problem follow the Array plus Simulation pattern?

Exactly, the problem requires iterating through an array of brackets and simulating tax computation, making it a classic Array plus Simulation use case.

terminal

Solution

Solution 1: Simulation

We traverse `brackets`, and for each tax bracket, we calculate the tax amount for that bracket, then accumulate it.

1

2

3

4

5

6

7

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        ans = prev = 0
        for upper, percent in brackets:
            ans += max(0, min(income, upper) - prev) * percent
            prev = upper
        return ans / 100

Continue Practicing

#2295 replace elements in an array #2293 min max game #2326 spiral matrix iv