Calculate Amount Paid in Taxes
Calculate Amount Paid in Taxes is a easy arrays & hashing problem solved with the simulation pattern.
The best approach, optimal (bracket by bracket), runs in O(B) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dollar by dollar up.
Problem
A tax system is described by brackets, where brackets[i] = [upper_i, percent_i]. The upper bounds are strictly increasing. The first upper_0 dollars of income are taxed at percent_0 percent, the dollars after that up to upper_1 at percent_1 percent, and so on: each bracket taxes only the part of the income that lies between the previous upper bound and its own.
Given your income, return the total tax you owe as a decimal number.
Examples
Example 1
- Input
brackets = [[4, 10], [9, 30], [15, 5]], income = 12- Output
2.05- Why
- 4 dollars at 10% = 0.40, the next 5 dollars at 30% = 1.50, the last 3 dollars at 5% = 0.15; total 2.05.
Example 2
- Input
brackets = [[2, 50], [6, 0]], income = 5- Output
1.00- Why
- Only the first 2 dollars are taxed (at 50%); the other 3 fall in a 0% bracket.
Example 3
- Input
brackets = [[10, 20]], income = 0- Output
0.00- Why
- No income means no tax.
Constraints
1 <= brackets.length <= 1001 <= upper_i <= 1000and0 <= percent_i <= 100- The upper bounds are strictly increasing, and the last one is at least
income. 0 <= income <= 1000- Answers within
10^-5of the true value are accepted.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Dollar by dollar | O(income + B) | O(1) |
| Optimal (bracket by bracket) | O(B) | O(1) |
1Dollar by dollar
O(income + B)One step per dollar, and the bracket pointer only moves forward through the B brackets.O(1)A running total and a pointer.Since all values are small, tax each dollar one at a time: dollar number d (1-based) belongs to the first bracket whose upper bound is at least d, and costs that bracket's percent divided by 100.
- tax = 0, b = 0.
- For d from 1 to income: while brackets[b][0] < d, advance b; add brackets[b][1] / 100 to tax.
- Return tax.
class Solution {
public double calculateTax(int[][] brackets, int income) {
double tax = 0;
int b = 0;
for (int d = 1; d <= income; d++) {
while (brackets[b][0] < d) b++;
tax += brackets[b][1] / 100.0;
}
return tax;
}
}class Solution:
def calculateTax(self, brackets: List[List[int]], income: int) -> float:
tax = 0.0
b = 0
for d in range(1, income + 1):
while brackets[b][0] < d:
b += 1
tax += brackets[b][1] / 100.0
return taxclass Solution {
public:
double calculateTax(vector<vector<int>>& brackets, int income) {
double tax = 0;
int b = 0;
for (int d = 1; d <= income; d++) {
while (brackets[b][0] < d) b++;
tax += brackets[b][1] / 100.0;
}
return tax;
}
};function calculateTax(brackets, income) {
let tax = 0;
let b = 0;
for (let d = 1; d <= income; d++) {
while (brackets[b][0] < d) b++;
tax += brackets[b][1] / 100;
}
return tax;
}2Optimal (bracket by bracket)
O(B)Each of the B brackets is visited at most once.O(1)A running total and the previous bound.Walk the brackets once, keeping the previous upper bound. The slice of income that falls in bracket i is min(income, upper_i) - prev; tax it at the bracket's rate and stop once the income is used up.
- tax = 0, prev = 0.
- For each [upper, percent]: taxed = min(income, upper) - prev; if taxed <= 0 stop.
- tax += taxed * percent / 100; prev = upper.
- Return tax.
class Solution {
public double calculateTax(int[][] brackets, int income) {
double tax = 0;
int prev = 0;
for (int[] br : brackets) {
int taxed = Math.min(income, br[0]) - prev;
if (taxed <= 0) break;
tax += taxed * br[1] / 100.0;
prev = br[0];
}
return tax;
}
}class Solution:
def calculateTax(self, brackets: List[List[int]], income: int) -> float:
tax = 0.0
prev = 0
for upper, percent in brackets:
taxed = min(income, upper) - prev
if taxed <= 0:
break
tax += taxed * percent / 100.0
prev = upper
return taxclass Solution {
public:
double calculateTax(vector<vector<int>>& brackets, int income) {
double tax = 0;
int prev = 0;
for (auto& br : brackets) {
int taxed = min(income, br[0]) - prev;
if (taxed <= 0) break;
tax += taxed * br[1] / 100.0;
prev = br[0];
}
return tax;
}
};function calculateTax(brackets, income) {
let tax = 0;
let prev = 0;
for (const [upper, percent] of brackets) {
const taxed = Math.min(income, upper) - prev;
if (taxed <= 0) break;
tax += taxed * percent / 100;
prev = upper;
}
return tax;
}Edge cases to test
- Income of 0
- Income that ends exactly on a bracket's upper bound
- Income that runs out inside the first bracket
- Brackets with a 0% or 100% rate
Hints
Hint 1
Bracket i covers the dollars between the previous upper bound and upper_i.
Hint 2
The taxed amount in a bracket is min(income, upper_i) - previous upper, if positive.
Hint 3
Stop as soon as the previous upper bound reaches your income.
FAQ
What is the best time complexity for Calculate Amount Paid in Taxes?
Optimal (bracket by bracket) runs in O(B) time and O(1) extra space. Each of the B brackets is visited at most once.
Which pattern does Calculate Amount Paid in Taxes use?
It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, Integer to English Words, String to Integer (atoi).
Is there a brute force solution for Calculate Amount Paid in Taxes?
Yes. Dollar by dollar takes O(income + B) time and O(1) space. Since all values are small, tax each dollar one at a time: dollar number d (1-based) belongs to the first bracket whose upper bound is at least d, and costs that bracket's percent divided by 100.
Which edge cases should I test for Calculate Amount Paid in Taxes?
Income of 0; Income that ends exactly on a bracket's upper bound; Income that runs out inside the first bracket; Brackets with a 0% or 100% rate.