Calculate Amount Paid in Taxes

Easy

#2099Time: O(I * N), where I is the `income` and N is the number of brackets. The outer loop runs `income` times, and for each iteration, the inner loop may run up to N times.Space: O(1), as only a constant amount of extra space is used for variables.1 company

Data structures

Array

Companies

Snowflake

Prompt

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 (i.e. upper_i-1 < upper_i for 0 < i < brackets.length).

Tax is calculated as follows:

The first upper₀ dollars earned are taxed at a rate of percent₀.
The next upper₁ - upper₀ dollars earned are taxed at a rate of percent₁.
The next upper₂ - upper₁ dollars earned are taxed at a rate of percent₂.
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. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: brackets = [[3,50],[7,10],[12,25]], income = 10
Output: 2.65000
Explanation:
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.

Example 2:

Input: brackets = [[1,0],[4,25],[5,50]], income = 2
Output: 0.25000
Explanation:
Based on your income, you have 1 dollar in the 1st tax bracket and 1 dollar in the 2nd tax bracket.
The tax rate for the two tax brackets is 0% and 25%, respectively.
In total, you pay $1 * 0% + $1 * 25% = $0.25 in taxes.

Example 3:

Input: brackets = [[2,50]], income = 0
Output: 0.00000
Explanation:
You have no income to tax, so you have to pay a total of $0 in taxes.

Constraints:

1 <= brackets.length <= 100
1 <= upper_i <= 1000
0 <= percent_i <= 100
0 <= income <= 1000
upper_i is sorted in ascending order.
All the values of upper_i are unique.
The upper bound of the last tax bracket is greater than or equal to income.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the tax calculation for each individual dollar of the income. It iterates from 1 up to the total income. For each dollar, it determines the corresponding tax bracket and calculates the tax for that single dollar, adding it to a running total.

Algorithm

Initialize totalTax = 0.0.
If income is 0, return 0.0 immediately.
Loop for each dollar i from 1 to income.
Inside the loop, initialize lowerBound = 0.
Loop through each bracket in brackets.
Let `upper = bracket[0]` and `percent = bracket[1]`.

1If the current dollar `i` is greater than `lowerBound` and less than or equal to `upper`, it falls in this bracket.

Calculate tax for this single dollar: `tax_for_one_dollar = 1.0 * percent / 100.0`.
Add this to the total: `totalTax += tax_for_one_dollar`.
Break the inner loop since the bracket for the current dollar is found.
Update `lowerBound = upper` to define the range for the subsequent bracket.
After the outer loop finishes, return totalTax.

Walkthrough

The algorithm initializes a variable totalTax to zero. It then enters a loop that runs from 1 to income. Inside this loop, for each dollar, it needs to find the correct tax bracket. This is done by iterating through the brackets array. A variable lowerBound is used to keep track of the lower bound of the current bracket, initialized to 0 for the first bracket. For each bracket [upper, percent], it checks if the current dollar falls within the range (lowerBound, upper]. If it does, the tax for this single dollar is calculated as 1.0 * percent / 100.0 and added to totalTax. The inner loop (over brackets) is then broken, and the process continues for the next dollar. After finding the bracket for a dollar, lowerBound is updated to upper to correctly define the range for the subsequent bracket. This process repeats for all dollars up to the income. Finally, the accumulated totalTax is returned.

1class Solution {2    public double calculateTax(int[][] brackets, int income) {3        double totalTax = 0.0;4        if (income == 0) {5            return 0.0;6        }7 8        for (int i = 1; i <= income; i++) {9            int lowerBound = 0;10            for (int[] bracket : brackets) {11                int upperBound = bracket[0];12                int percent = bracket[1];13                if (i > lowerBound && i <= upperBound) {14                    totalTax += 1.0 * percent / 100.0;15                    break;16                }17                lowerBound = upperBound;18            }19        }20        return totalTax;21    }22}

Complexity

Time

O(I * N), where I is the `income` and N is the number of brackets. The outer loop runs `income` times, and for each iteration, the inner loop may run up to N times.

Space

O(1), as only a constant amount of extra space is used for variables.

Trade-offs

Pros

Conceptually simple and easy to understand.
Directly models the definition of taxing each dollar.

Cons

Highly inefficient, especially for large incomes, as its runtime depends on the value of the income.
Performs redundant work by repeatedly scanning the brackets for each dollar.

This approach calculates the tax by iterating through the tax brackets just once. For each bracket, it determines the total amount of income that falls into that specific bracket's range and calculates the tax on that chunk of income. This avoids the redundant work of the brute-force method.

Algorithm

Initialize totalTax = 0.0.
Initialize previousUpperBound = 0.
Loop through each bracket in the brackets array.
Let `upper = bracket[0]` and `percent = bracket[1]`.
If `income <= previousUpperBound`, it means all income has been taxed, so break the loop.

1Calculate the taxable amount in this bracket: `taxableAmount = Math.min(income, upper) - previousUpperBound`.

Calculate the tax for this amount: `tax = (double) taxableAmount * percent / 100.0`.
Add this tax to the total: `totalTax += tax`.
Update `previousUpperBound = upper` for the next iteration.
Return totalTax.

Walkthrough

The algorithm maintains a running total of the tax, totalTax, and the amount of income that has already been taxed, which can be tracked using a previousUpperBound variable. Both are initialized to zero. It then iterates through the brackets array. For each bracket [upper, percent]:

It first checks if all the income has already been taxed by comparing income with previousUpperBound. If income <= previousUpperBound, the loop can be terminated early.
It calculates the amount of income taxable within this bracket. This is the portion of the total income that is greater than previousUpperBound but not more than the current bracket's upper bound. The formula for this is Math.min(income, upper) - previousUpperBound.
The tax for the current bracket is taxableAmount * percent / 100.0. This is added to totalTax.
previousUpperBound is then updated to the current bracket's upper bound to serve as the lower bound for the next bracket. After iterating through all relevant brackets, totalTax holds the final result.

1class Solution {2    public double calculateTax(int[][] brackets, int income) {3        double totalTax = 0.0;4        int previousUpperBound = 0;5 6        for (int[] bracket : brackets) {7            int currentUpperBound = bracket[0];8            int percent = bracket[1];9 10            if (income <= previousUpperBound) {11                break;12            }13 14            int taxableAmount = Math.min(income, currentUpperBound) - previousUpperBound;15            totalTax += (double) taxableAmount * percent / 100.0;16            17            previousUpperBound = currentUpperBound;18        }19 20        return totalTax;21    }22}

Complexity

Time

O(N), where N is the number of brackets. The algorithm iterates through the `brackets` array at most once.

Space

O(1), as it only uses a constant amount of extra space for variables like `totalTax` and `previousUpperBound`.

Trade-offs

Pros

Highly efficient with linear time complexity relative to the number of brackets.
Optimal solution as each bracket must be considered at least once to calculate the tax correctly.

Cons

Requires careful handling of the previousUpperBound to correctly calculate the taxable amount for each progressive bracket.

Solutions

Solution

1class Solution {2public3  double calculateTax(int[][] brackets, int income) {4    int ans = 0, prev = 0;5    for (var e : brackets) {6      int upper = e[0], percent = e[1];7      ans += Math.max(0, Math.min(income, upper) - prev) * percent;8      prev = upper;9    }10    return ans / 100.0;11  }12}

1class Solution {2public:3  double calculateTax(vector<vector<int>> &brackets, int income) {4    int ans = 0, prev = 0;5    for (auto &e : brackets) {6      int upper = e[0], percent = e[1];7      ans += max(0, min(income, upper) - prev) * percent;8      prev = upper;9    }10    return ans / 100.0;11  }12};

1class Solution:2    def calculateTax(self, brackets: List[List[int]], income: int) -> float: ans = prev = 0 for upper, percent in brackets: ans += max(0, min(income, upper) - prev) * percent prev = upper return ans / 100

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem