Calculate Amount Paid in Taxes

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upper<sub>i</sub>, percent<sub>i</sub>] means that the i<sup>th</sup> tax bracket has an upper bound of upper<sub>i</sub> and is taxed at a rate of percent<sub>i</sub>. The brackets are sorted by upper bound (i.e. upper<sub>i-1</sub> < upper<sub>i</sub> for 0 < i < brackets.length).

Tax is calculated as follows:

• The first upper<sub>0</sub> dollars earned are taxed at a rate of percent<sub>0</sub>.
• The next upper<sub>1</sub> - upper<sub>0</sub> dollars earned are taxed at a rate of percent<sub>1</sub>.
• The next upper<sub>2</sub> - upper<sub>1</sub> dollars earned are taxed at a rate of percent<sub>2</sub>.
• And so on.

You are given an integer income representing the amount of money you earned. Return the amount of money that you have to pay in taxes.

Example:

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

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.

Write a function to calculate the taxes owed, given the tax brackets and income.

## Optimal Solution

This problem can be solved by iterating through the `brackets` array and calculating the tax for each bracket based on the income. We maintain a running tax total and adjust the income as we move through the brackets.

```python
def calculateTax(brackets, income):
    tax = 0.0
    prev_upper = 0
    for upper, percent in brackets:
        taxable_income = min(income, upper - prev_upper)
        if taxable_income > 0:
            tax += taxable_income * (percent / 100.0)
            income -= taxable_income
        if income == 0:
            break
        prev_upper = upper
    return tax

Example:

brackets = [[3,50],[7,10],[12,25]]
income = 10
print(calculateTax(brackets, income))

Big(O) Run-time Analysis

The algorithm iterates through the brackets array at most once. The number of brackets is limited by the constraints to a maximum of 100. Therefore, the run-time complexity is O(n), where n is the number of brackets. In the worst case, n will be 100, so it can be considered O(1).

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space, regardless of the input size. We only use a few variables to store the tax, previous upper bound, taxable income, and the loop variables. Therefore, the space complexity is O(1).

Edge Cases

1. Income is 0: If the income is 0, the algorithm should return 0.0 without any calculations.
2. Brackets array is empty: Although the constraints specify that the brackets array will have at least one element, it's good to consider the case where it's empty. The algorithm would return 0.0 in this case, which is the correct behavior.
3. Income is less than the first upper bound: In this case, only the first bracket is used to calculate the tax.
4. Income is greater than the last upper bound: The problem statement specifies that the upper bound of the last tax bracket is greater than or equal to the income, so this case will not happen.
5. Zero percent tax bracket: If a tax bracket has a 0% tax rate, the algorithm should correctly calculate the tax as 0 for that bracket.