Calculate Amount Paid in Taxes

Difficulty: Easy | Acceptance: 69.30% | Paid: No Topics: Array, Simulation

You are given a 2D integer array brackets where brackets[i] = [upperi, percenti] means that the ith tax bracket has an upper bound of upperi and is taxed at a rate of percenti. The brackets are sorted by upper bound in strictly increasing order.

Tax is calculated on the income that falls within each tax bracket. The income that falls within a bracket is taxed at the rate of that bracket, and any remaining income is passed to the next bracket.

Given an integer income, return the amount of taxes you have to pay.

• Examples
• Constraints
• Iterative Simulation
• Recursive Simulation

Examples

Example 1:

Input: brackets = [[3,50],[7,10],[12,25]], income = 10
Output: 2.65000
Explanation:
The first 3 dollars are taxed at 50%: $3 * 50% = $1.50
The next 4 dollars are taxed at 10%: $4 * 10% = $0.40
The last 3 dollars are taxed at 25%: $3 * 25% = $0.75
Total tax is $1.50 + $0.40 + $0.75 = $2.65

Example 2:

Input: brackets = [[1,0],[4,25],[5,50]], income = 2
Output: 0.25000
Explanation:
The first dollar is not taxed: $1 * 0% = $0
The next dollar is taxed at 25%: $1 * 25% = $0.25
Total tax is $0 + $0.25 = $0.25

Example 3:

Input: brackets = [[2,50]], income = 0
Output: 0.00000
Explanation:
No income, no tax.

Constraints

1 <= brackets.length <= 100
1 <= upperi <= 1000
0 <= percenti <= 100
0 <= income <= 1000
upperi is strictly increasing.

Iterative Simulation

Intuition We iterate through the tax brackets sequentially. For each bracket, we determine how much of the total income falls into that specific bracket’s range, apply the tax rate, and accumulate the total tax.

Steps

• Initialize total_tax to 0 and prev_upper to 0.
• Iterate through each bracket [upper, percent] in the brackets array.
• Calculate the taxable amount for the current bracket as min(income, upper) - prev_upper.
• If the taxable amount is positive, add taxable_amount * percent / 100 to total_tax.
• Update prev_upper to upper.
• If income is less than or equal to prev_upper, we have taxed all income, so break the loop.
• Return total_tax.

from typing import List

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

Complexity

• Time: O(N) where N is the number of brackets.
• Space: O(1) as we only use a few variables for tracking state.
• Notes: This is the most efficient approach for this problem.

Recursive Simulation

Intuition We can solve the problem recursively by processing one bracket at a time. The base case occurs when we run out of brackets or the income is fully taxed. The recursive step calculates the tax for the current bracket and passes the remaining state to the next call.

Steps

• Define a recursive helper function that takes the current index, previous upper bound, and accumulated tax.
• Base case: If the index is out of bounds or income is less than or equal to the previous upper bound, return the accumulated tax.
• Recursive step: Calculate the taxable amount for the current bracket, update the accumulated tax, and call the function for the next bracket with the updated upper bound.

from typing import List

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        def helper(idx: int, prev_upper: int, current_tax: float) -> float:
            if idx >= len(brackets) or income <= prev_upper:
                return current_tax
            
            upper, percent = brackets[idx]
            taxable = min(income, upper) - prev_upper
            
            if taxable < 0:
                return current_tax
            
            new_tax = current_tax + (taxable * percent / 100.0)
            return helper(idx + 1, upper, new_tax)
        
        return helper(0, 0, 0.0)

Complexity

• Time: O(N) where N is the number of brackets.
• Space: O(N) due to the recursion stack depth.
• Notes: While functionally correct, the iterative approach is preferred to avoid stack overflow risks with large input sizes, though constraints here are small.