Calculate Amount Paid in Taxes
Easy
0 views
Topics:
Arrays
You are given a 0-indexed 2D integer array brackets where brackets[i] = [upperi, percenti] means that the ith tax bracket has an upper bound of upperi and is taxed at a rate of percenti. The brackets are sorted by upper bound (i.e. upperi-1 < upperi for 0 < i < brackets.length).
Tax is calculated as follows:
- The first
upper0dollars earned are taxed at a rate ofpercent0. - The next
upper1 - upper0dollars earned are taxed at a rate ofpercent1. - The next
upper2 - upper1dollars earned are taxed at a rate ofpercent2. - 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 <= 1001 <= upperi <= 10000 <= percenti <= 1000 <= income <= 1000upperiis sorted in ascending order.- All the values of
upperiare unique. - The upper bound of the last tax bracket is greater than or equal to
income.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the data types and possible ranges for the income and upper bound values in the brackets?
- Is the `brackets` array guaranteed to be sorted in ascending order of upper bounds, and are the upper bounds guaranteed to be strictly increasing?
- Can the income be larger than the upper bound of the last bracket?
- Can the tax percentage be any floating point value between 0 and 1 inclusive or should I expect it as an integer percentage?
- What should I return if the `brackets` array is empty or null?
Brute Force Solution
Approach
The brute force method in this tax calculation problem means we'll check the tax bracket for every single dollar earned, one at a time. We essentially go through each dollar and figure out which tax rate applies to it. Then, we add up all the taxes owed on each dollar to get the total tax amount.
Here's how the algorithm would work step-by-step:
- Start with the very first dollar of income.
- Figure out which tax bracket that dollar falls into.
- Calculate the tax owed on that single dollar based on that bracket's tax rate.
- Move on to the second dollar, and do the same thing: determine its tax bracket, and calculate the tax.
- Continue this process for every single dollar, all the way up to the total income.
- Finally, add up all the taxes you calculated for each individual dollar. This sum represents the total amount of tax owed.
Code Implementation
def calculate_taxes_brute_force(income, tax_brackets):
total_tax_owed = 0
# Iterate through each dollar of income.
for current_dollar in range(1, income + 1):
applicable_tax_rate = 0
# Find the applicable tax bracket for the current dollar.
for bracket in tax_brackets:
if current_dollar <= bracket[0]:
applicable_tax_rate = bracket[1]
break
else:
# If no bracket is found, use the highest bracket.
applicable_tax_rate = tax_brackets[-1][1]
# Calculate the tax owed for this specific dollar.
tax_for_dollar = current_dollar * applicable_tax_rate / current_dollar
# Accumulate the tax owed.
total_tax_owed += tax_for_dollar
return total_tax_owedBig(O) Analysis
Time Complexity
O(n) – The provided brute force approach iterates through each dollar of income, up to the total income amount, to determine the applicable tax bracket and calculate the tax for that dollar. If the total income is represented by n, the algorithm performs a constant amount of work for each of the n dollars. Therefore, the time complexity is directly proportional to the total income n, resulting in a linear time complexity of O(n).
Space Complexity
O(1) – The brute force approach described calculates the tax owed on each dollar individually and adds it to a running total. It doesn't require storing any data structures that scale with the income amount. We only need a few variables to store the current dollar being evaluated, the tax owed for that dollar, and the cumulative tax amount, regardless of how large the total income is. Therefore, the space complexity is constant. This constant space usage is independent of the input size, N (the total income).
Optimal Solution
Approach
To figure out the taxes, we'll go through each tax bracket one by one. We'll only calculate taxes for the portion of income that falls into each specific bracket, and then add up the taxes from all the brackets.
Here's how the algorithm would work step-by-step:
- Start with the first tax bracket (the one with the lowest income range).
- Check how much of the total income falls within this bracket's income range. If the entire income is within this range, skip to the calculation step.
- If the income exceeds the bracket, calculate the income amount in that bracket by subtracting the bracket minimum from the bracket maximum. If there is no bracket maximum, calculate the difference between the income and the bracket minimum
- Multiply the income amount in that bracket by the tax rate of that bracket. This is the tax due for that bracket.
- Move on to the next tax bracket.
- Repeat steps 2-4 for each tax bracket, adding the tax due for each bracket to a running total.
- The final running total is the total amount of taxes to be paid.
Code Implementation
def calculate_amount_paid_in_taxes(income, tax_brackets):
total_tax = 0
for bracket in tax_brackets:
lower_bound = bracket['lower_bound']
upper_bound = bracket['upper_bound']
rate = bracket['rate']
#Determine taxable income in current bracket
if income <= lower_bound:
continue
taxable_income_in_bracket = 0
if upper_bound is None:
taxable_income_in_bracket = income - lower_bound
else:
taxable_income_in_bracket = min(income, upper_bound) - lower_bound
#Calculate and accumulate tax from the current bracket
tax_for_bracket = taxable_income_in_bracket * rate
total_tax += tax_for_bracket
return total_taxBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through each tax bracket once to calculate the tax due for that bracket. The number of tax brackets corresponds to the input size, n. In each iteration, it performs a constant number of arithmetic operations to determine the taxable income within the bracket and calculate the tax. Therefore, the time complexity is directly proportional to the number of tax brackets, resulting in O(n) time complexity.
Space Complexity
O(1) – The algorithm calculates taxes iteratively for each tax bracket, accumulating the total tax due in a running total variable. No auxiliary data structures like lists, maps, or sets are created to store intermediate results. Therefore, the space used is constant, regardless of the number of tax brackets or the income amount.
Edge Cases
| Case | How to Handle |
|---|---|
| Empty brackets array | Return 0 as no tax brackets are defined, meaning no taxes are paid. |
| Null brackets array | Throw an IllegalArgumentException or return an error code, signaling invalid input. |
| Zero income | Return 0 as no income means no tax is owed. |
| Income less than or equal to the lowest bracket upper bound. | Calculate the tax for the portion of income within that bracket and return the result. |
| Income exceeds the highest bracket upper bound. | Calculate tax for each bracket up to its upper bound, then apply the highest bracket's rate to the remaining income. |
| Invalid bracket: Upper bound is not strictly increasing. | Throw an IllegalArgumentException or return an error code because brackets must be sorted and increasing. |
| Invalid bracket: Tax percentage is outside the range [0, 1]. | Throw an IllegalArgumentException or return an error code since tax rates can only be between 0% and 100%. |
| Integer overflow when calculating tax amount (income * tax percentage) | Use long data type for intermediate calculations to prevent potential integer overflow before final return. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
