Problem Description

You need to calculate the total tax amount based on a progressive tax bracket system.

You're given:

• A 2D array brackets where each element brackets[i] = [upper_i, percent_i] represents:
  • upper_i: the upper bound of the i-th tax bracket (in dollars)
  • percent_i: the tax rate for that bracket (as a percentage)
• The brackets are sorted in ascending order by their upper bounds
• An integer income representing your total earnings

The tax calculation follows a progressive system:

• The first upper_0 dollars of your income are taxed at percent_0%
• The next chunk from upper_0 to upper_1 dollars is taxed at percent_1%
• The next chunk from upper_1 to upper_2 dollars is taxed at percent_2%
• This pattern continues for all brackets

For example, if brackets are [[10000, 10], [20000, 20]] and income is 15000:

• First $10,000 is taxed at 10$1,000
• Next $5,000 (from$10,000 to $15,000) is taxed at 20$1,000
• Total tax = $2,000

The solution iterates through each bracket, calculating the taxable amount for that bracket as min(income, upper) - prev, where prev tracks the previous bracket's upper bound. This ensures we only tax the portion of income that falls within each bracket. The tax for each bracket is then accumulated and divided by 100 to convert from percentage to decimal.

Return the total tax amount as a floating-point number.

Intuition

The key insight is that we need to process the income in chunks, where each chunk corresponds to a tax bracket range. Since the brackets are already sorted by their upper bounds, we can process them sequentially.

Think of the income as being divided into layers, like a cake. Each layer gets taxed at a different rate. For each bracket, we need to figure out how much of our income falls within that bracket's range.

The challenge is determining how much income to tax at each bracket. For any bracket i, the taxable amount is the income that falls between the previous bracket's upper bound and the current bracket's upper bound. However, we need to be careful about two edge cases:

1. If our income is less than the current bracket's upper bound, we should only tax up to our income amount, not the full bracket range
2. If our income was already fully taxed in previous brackets, we shouldn't tax anything in the current bracket

This leads us to the formula: taxable_amount = max(0, min(income, upper) - prev)

• min(income, upper) ensures we don't tax more than what we earned
• Subtracting prev gives us only the portion that falls in the current bracket
• max(0, ...) handles the case where our income was already fully covered by previous brackets

By maintaining a prev variable that tracks the upper bound of the last processed bracket, we can calculate the taxable amount for each bracket incrementally. We multiply this amount by the bracket's tax rate and accumulate the total tax.

The final division by 100 converts the percentage rates to decimal form for the final answer.

Solution Approach

The solution uses a simulation approach, processing each tax bracket sequentially to calculate the total tax.

Implementation Steps:

1. Initialize Variables:

   • ans to accumulate the total tax amount (initially 0)
   • prev to track the upper bound of the previous bracket (initially 0)

2. Iterate Through Brackets: For each bracket [upper, percent] in the brackets array:

   a. Calculate Taxable Amount for Current Bracket:

   • Use the formula: max(0, min(income, upper) - prev) * percent
   • min(income, upper) ensures we don't exceed the actual income
   • Subtracting prev gives us only the portion in this bracket
   • max(0, ...) handles cases where income is less than prev

   b. Accumulate Tax:

   • Add the calculated tax to ans

   c. Update Previous Upper Bound:

   • Set prev = upper for the next iteration

3. Return Result:

   • Divide ans by 100 to convert from percentage to decimal format

Example Walkthrough:

Let's say brackets = [[10000, 10], [20000, 20], [30000, 30]] and income = 25000:

• First bracket [10000, 10]:

  • Taxable: min(25000, 10000) - 0 = 10000
  • Tax: 10000 * 10 = 100000
  • Update: prev = 10000

• Second bracket [20000, 20]:

  • Taxable: min(25000, 20000) - 10000 = 10000
  • Tax: 10000 * 20 = 200000
  • Update: prev = 20000

• Third bracket [30000, 30]:

  • Taxable: min(25000, 30000) - 20000 = 5000
  • Tax: 5000 * 30 = 150000
  • Update: prev = 30000

• Total: (100000 + 200000 + 150000) / 100 = 4500.0

The algorithm runs in O(n) time where n is the number of brackets, with O(1) space complexity.

Example Walkthrough

Let's walk through a simple example with brackets = [[3, 50], [7, 10], [12, 25]] and income = 10.

Initial Setup:

• ans = 0 (total tax accumulator)
• prev = 0 (tracks previous bracket upper bound)

Processing Each Bracket:

Bracket 1: [3, 50]

• Income range for this bracket: $0 to$3
• Taxable amount: min(10, 3) - 0 = 3 - 0 = 3
• Tax calculation: 3 * 50 = 150
• Running total: ans = 0 + 150 = 150
• Update: prev = 3

Bracket 2: [7, 10]

• Income range for this bracket: $3 to$7
• Taxable amount: min(10, 7) - 3 = 7 - 3 = 4
• Tax calculation: 4 * 10 = 40
• Running total: ans = 150 + 40 = 190
• Update: prev = 7

Bracket 3: [12, 25]

• Income range for this bracket: $7 to$12
• Taxable amount: min(10, 12) - 7 = 10 - 7 = 3
• Tax calculation: 3 * 25 = 75
• Running total: ans = 190 + 75 = 265
• Update: prev = 12

Final Result:

• Total tax: 265 / 100 = 2.65

The key insight is that for each bracket, we calculate how much of our income falls within that bracket's range by taking the minimum of our income and the bracket's upper bound, then subtracting what was already taxed in previous brackets. This ensures each dollar is taxed exactly once at the appropriate rate.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the brackets list. This is because the algorithm iterates through each bracket exactly once in a single loop, performing constant-time operations (comparisons, arithmetic operations, and assignments) for each bracket.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables ans and prev, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Convert Percentage to Decimal

One of the most common mistakes is forgetting to divide the final result by 100. Since the tax rates are given as percentages (e.g., 20 means 20%), the accumulated tax needs to be converted to the actual dollar amount.

Incorrect:

def calculateTax(self, brackets: List[List[int]], income: int) -> float:
    total_tax = 0
    previous_upper_bound = 0
  
    for upper_bound, tax_percentage in brackets:
        taxable_in_bracket = max(0, min(income, upper_bound) - previous_upper_bound)
        total_tax += taxable_in_bracket * tax_percentage
        previous_upper_bound = upper_bound
  
    return total_tax  # Missing division by 100!

Solution: Always remember to divide by 100 at the end, or alternatively, convert percentages to decimals at the beginning.

2. Not Handling Early Termination

When income is less than the upper bound of a bracket, continuing to process remaining brackets wastes computation time. While the current solution handles this correctly with min(income, upper_bound), an optimization would be to break early.

Optimized Solution:

def calculateTax(self, brackets: List[List[int]], income: int) -> float:
    total_tax = 0
    previous_upper_bound = 0
  
    for upper_bound, tax_percentage in brackets:
        if income <= previous_upper_bound:
            break  # No more income to tax
          
        taxable_in_bracket = min(income, upper_bound) - previous_upper_bound
        total_tax += taxable_in_bracket * tax_percentage
        previous_upper_bound = upper_bound
      
        if income <= upper_bound:
            break  # All income has been taxed
  
    return total_tax / 100

3. Integer Division Issues in Other Languages

If implementing in languages like C++ or Java, using integer division could lead to precision loss. Always ensure floating-point arithmetic when dealing with the final result.

Example in Java (incorrect):

return totalTax / 100;  // Integer division if totalTax is int

Correct approach:

return totalTax / 100.0;  // Forces floating-point division

4. Not Initializing Previous Upper Bound to Zero

Forgetting to initialize previous_upper_bound to 0 or starting it with the wrong value will cause incorrect calculations for the first bracket.

Incorrect:

def calculateTax(self, brackets: List[List[int]], income: int) -> float:
    total_tax = 0
    # Missing initialization of previous_upper_bound!
  
    for i, (upper_bound, tax_percentage) in enumerate(brackets):
        if i == 0:
            taxable_in_bracket = min(income, upper_bound)
        else:
            # previous_upper_bound is undefined here!
            taxable_in_bracket = min(income, upper_bound) - previous_upper_bound
        # ...

5. Misunderstanding the Bracket System

A conceptual pitfall is thinking that if your income falls in a certain bracket, ALL of it gets taxed at that rate. This is incorrect - only the portion within each bracket gets taxed at that bracket's rate.

Wrong Mental Model: "If I earn $25,000 and fall in the 30$25,000"

Correct Understanding: "Each portion of my income gets taxed at its corresponding bracket rate"