Calculate Amount Paid in Taxes

In this problem, we need to calculate the total tax amount from the given income and tax brackets. We traverse through each tax bracket from the lowest to highest. In each bracket, we calculate the taxable income as the minimum of the income and the upper limit of the bracket. The tax for this bracket is then calculated by multiplying the taxable income with the tax rate. This process continues until we exhaust the income or all brackets.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        tax = 0.0
        previous_upper = 0

        for upper, percent in brackets:
            if income > upper:
                # If the income is more than the upper limit,
                # calculate tax for the income up to the upper limit
                tax += (upper - previous_upper) * percent / 100
            else:
                # If the income is less than the upper limit,
                # calculate tax for the remaining income and break the loop
                tax += (income - previous_upper) * percent / 100
                break

            previous_upper = upper

        return tax

We maintain a variable previous_upper to keep track of the upper limit of the previous tax bracket. This is needed to calculate the taxable income for the current tax bracket.

The complexity of the solution is O(n) where n is the number of tax brackets, as we potentially need to traverse all the brackets.