Calculate Amount Paid in Taxes

Problem Description

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upper_i, percent_i] means that the i-th tax bracket has an upper bound of upper_i and is taxed at a rate of percent_i. The brackets are sorted by upper bound. 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.

Key Insights

• The tax is calculated progressively based on income within defined brackets.
• Each bracket specifies an upper limit and a corresponding tax rate.
• The total tax is a sum of taxes owed for each segment of income that falls within a bracket.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tax brackets. Space Complexity: O(1), since we are using a constant amount of space.

Solution

To solve this problem, we will iterate through each tax bracket and calculate the tax owed for each segment of income. We will maintain a running total of the tax paid and use the upper bounds of the brackets to determine how much of the income falls into each bracket. The algorithm proceeds as follows:

1. Initialize a variable to keep track of the total tax.
2. For each bracket, check how much of the income falls into the current bracket.
3. Calculate the tax for that segment of income using the bracket's tax rate.
4. Update the total tax and proceed to the next bracket until the income is fully accounted for.

Code Solutions