Problem Description

You are given an array of tax brackets and an integer income. Each tax bracket is represented as a list of three integers: [upper, percent], where upper is the upper bound of the bracket (inclusive), and percent is the tax rate for that bracket (as a percentage). The brackets are sorted by upper bound in ascending order.

Your task is to calculate the total amount of tax paid for the given income according to the tax brackets. Tax is calculated progressively: for each bracket, only the portion of income within that bracket's range is taxed at the bracket's rate.

Key constraints:

• Each portion of income is taxed only once, at the rate of its bracket.
• The brackets cover all possible income up to and possibly above the given income.
• Return the total tax paid as a double or floating-point value.

Thought Process

At first glance, the problem appears to require simulating a real-world progressive tax system. For each tax bracket, we need to determine how much of the income falls within that bracket and then apply the bracket's tax rate to that portion.

A brute-force approach might try to simulate every dollar or unit of income, but that's inefficient and unnecessary. Instead, we can process each bracket in order, calculate the taxable amount for that bracket, and accumulate the total tax. We need to be careful to only tax the portion of income that falls within each bracket, not the entire income at every step.

The main challenge is to correctly handle the boundaries between brackets and stop once we've processed all of the income.

Solution Approach

We will process the tax brackets one by one, keeping track of the previous bracket's upper bound (starting from 0). For each bracket:

• Calculate the amount of income that falls within this bracket: min(income, upper) - previous_upper.
• If this value is less than or equal to zero, it means we've already processed all the income, so we can stop.
• Otherwise, compute the tax for this portion using the bracket's percentage: portion * percent / 100.0.
• Add this tax to the running total.
• Update previous_upper to upper for the next bracket.
• If income is less than or equal to upper, we can break out of the loop since all income has been taxed.

This approach is efficient because it processes each bracket at most once, and only computes the tax for the relevant portion of income.

Example Walkthrough

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

• First bracket: upper = 3, percent = 50
  • Taxable = min(10, 3) - 0 = 3
  • Tax = 3 * 50 / 100 = 1.5
  • Total tax so far: 1.5
• Second bracket: upper = 7, percent = 10
  • Taxable = min(10, 7) - 3 = 4
  • Tax = 4 * 10 / 100 = 0.4
  • Total tax so far: 1.9
• Third bracket: upper = 12, percent = 25
  • Taxable = min(10, 12) - 7 = 3
  • Tax = 3 * 25 / 100 = 0.75
  • Total tax so far: 2.65
• Since income = 10 is less than upper = 12, we're done.

The answer is 2.65.

Time and Space Complexity

Brute-force approach:

• If we attempted to process every dollar (or unit) of income, the time complexity would be O(income). This is inefficient for large incomes.

• We process each bracket once, so time complexity is O(N), where N is the number of brackets.
• Space complexity is O(1) as we only use a few variables for bookkeeping.

The optimized approach is both efficient and simple.

Summary

This problem is a simulation of progressive taxation. The key insight is to process each bracket in order, only taxing the portion of income that falls within each bracket. By keeping track of the previous upper bound and stopping early when all income is processed, we ensure both correctness and efficiency. The solution is elegant because it directly models the real-world process and avoids unnecessary computation.

Code Implementation

class Solution:
    def calculateTax(self, brackets, income):
        tax = 0.0
        prev = 0
        for upper, percent in brackets:
            taxable = min(income, upper) - prev
            if taxable <= 0:
                break
            tax += taxable * percent / 100.0
            prev = upper
            if income <= upper:
                break
        return tax
      

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double tax = 0.0;
        int prev = 0;
        for (auto& bracket : brackets) {
            int upper = bracket[0], percent = bracket[1];
            int taxable = min(income, upper) - prev;
            if (taxable <= 0) break;
            tax += taxable * percent / 100.0;
            prev = upper;
            if (income <= upper) break;
        }
        return tax;
    }
};
      

class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double tax = 0.0;
        int prev = 0;
        for (int[] bracket : brackets) {
            int upper = bracket[0], percent = bracket[1];
            int taxable = Math.min(income, upper) - prev;
            if (taxable <= 0) break;
            tax += taxable * percent / 100.0;
            prev = upper;
            if (income <= upper) break;
        }
        return tax;
    }
}
      

var calculateTax = function(brackets, income) {
    let tax = 0.0;
    let prev = 0;
    for (const [upper, percent] of brackets) {
        let taxable = Math.min(income, upper) - prev;
        if (taxable <= 0) break;
        tax += taxable * percent / 100.0;
        prev = upper;
        if (income <= upper) break;
    }
    return tax;
};