2303. Calculate Amount Paid in Taxes

EasyArraySimulation

Problem Description

The given LeetCode problem involves calculating the amount of taxes that need to be paid based on a set of tax brackets. Each bracket is defined by two parameters: upper, which is the upper bound of taxable income for that bracket, and percent, which is the tax rate for that bracket. The brackets array contains these pairs in ascending order of upper.

To calculate the total tax:

For the first bracket, tax is applied on the entire income if the income is less than or equal to upper[0], otherwise, tax is applied only up to upper[0].
For each subsequent bracket, tax is applied on the difference between the current bracket's upper and the previous bracket's upper, but only if the income is more than the previous upper. This continues until all the income is taxed or until all the brackets are exhausted.

The goal is to find out the total tax owed based on the income provided, where income is the total amount of money earned by an individual.

Intuition

The intuition behind the solution is to iterate through the tax brackets and calculate the taxes for each bracket incrementally. Since the income can span multiple brackets, the approach must consider partial amounts taxed at different brackets.

To implement this, we keep track of the previous bracket's upper bound as we iterate through the brackets so that we can calculate the taxable amount within the current bracket. The key steps in the solution are as follows:

Initialize ans as the accumulator for the total tax and prev to keep the upper bound of the previous bracket, starting with 0 for the initial condition.
Iterate over each bracket in the brackets list, which has upper and percent values.
For each bracket, calculate the amount of income that falls within this bracket. This is the minimum of the actual income and the current bracket's upper minus prev, which signifies the taxed amount in the previous brackets.
Calculate the tax for this bracket by multiplying the bracket's taxable income by the percent.
Update prev to be the current bracket's upper so that it can be used in the next iteration.
The tax rates are provided in percentages, so divide the final answer by 100 to get the actual tax amount.
Continue this process until all the brackets are covered or until the entire income is taxed.

The provided code implements this logic correctly and calculates the tax in an efficient manner.

Solution Approach

The algorithm for calculating taxes based on tax brackets is straightforward. The solution takes advantage of the sorted order of the tax brackets, following these steps:

Initialize two variables: ans to keep track of the total taxes paid so far, which starts at 0, and prev to track the upper bound of the previous bracket, starting with 0 since there's no previous bracket at the beginning.
Loop through each bracket in the brackets array, extracting upper, the upper bound for the bracket, and percent, the tax rate for that bracket.
In each iteration, calculate the taxable amount for the current bracket. This is done by subtracting prev from the minimum of income and the current upper. The subtraction of prev ensures only the income falling within the current bracket is considered. This is represented by the following expression:
```
taxable_amount = max(0, min(income, upper) - prev)
```
Calculate the tax for the current bracket by multiplying the taxable_amount by the percent rate. Since percent represents a percentage, you'll need to multiply the tax amount by the rate and then divide by 100 to convert it into the actual tax value. The tax for the current bracket is added to the ans accumulator:
```
ans += taxable_amount * percent
```
Once the tax for this bracket is calculated, update prev to the current bracket's upper, which will be used in the next iteration to calculate the next bracket's taxable income.
```
prev = upper
```
After completing the loop over all brackets, the final tax value stored in ans is divided by 100 to adjust for the percentage calculation:
```
return ans / 100
```

The use of max(0, min(income, upper) - prev) ensures that the solution also handles cases where the income does not reach the current bracket's upper. It also handles cases where the income is exactly on the upper of the previous bracket, thus not bleeding into the current tax bracket's range.

No additional data structures are needed, as the algorithm only requires simple variable assignments and arithmetic operations. The pattern followed is iterative, straightforward, and efficient, as it only requires one pass through the brackets array, making the complexity of this algorithm proportional to the number of brackets (O(n) time complexity, where n is the number of brackets).

This solution effectively calculates the total taxes for a given income according to the provided set of tax brackets.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following set of brackets:

[(10000, 10), (20000, 20), (30000, 30)]

This example states that:

Tax is 10% on income up to $10,000,
Tax is 20% on income between $10,000 and$ 20,000,
Tax is 30% on income between $20,000 and$ 30,000.

Let's calculate the total tax for an income of $25,000 using the algorithm outlined in the solution approach:

Initialize ans to 0 and prev to 0.
Start looping through the brackets.

First bracket: (10000, 10)

The taxable income for the first bracket is min(25000, 10000) - 0 = 10000.

The tax for the first bracket is 10000 * 10% = 1000.

Update ans by 1000 (now ans = 1000) and prev by the upper of the current bracket (now prev = 10000).
Second bracket: (20000, 20)

The taxable income for the second bracket is min(25000, 20000) - 10000 = 10000.

The tax for the second bracket is 10000 * 20% = 2000.

Update ans by 2000 (now ans = 3000) and prev by the upper of the current bracket (now prev = 20000).
Third bracket: (30000, 30)

Since the income is $25,000, which is less than the `upper` of$ 30,000, the calculation here is on the remaining income. The taxable income for the third bracket is min(25000, 30000) - 20000 = 5000.

The tax for the third bracket is 5000 * 30% = 1500.

Update ans by 1500 (now ans = 4500). There's no need to update prev since we've already covered all the income.

After all the brackets are processed, divide ans by 100 to adjust the percentage calculation. Therefore, ans/100 = 4500/100 = 45.

So the total tax on an income of $25,000 with the given tax brackets is$ 45. The algorithm correctly breaks down the income into portions that fall within each tax bracket, calculates the tax on each portion accordingly, and sums up the taxed amounts to determine the total tax liability.

Solution Implementation

1class Solution:
2    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
3        # Initialize the total tax amount to 0
4        total_tax = 0
5      
6        # Initialize 'previous_upper_bound' which will hold the upper bound of the previous bracket
7        previous_upper_bound = 0
8      
9        # Loop through the collected tax brackets
10        for upper_bound, tax_rate in brackets:
11            # Calculate the taxable income for the current bracket.
12            # 'max(0, min(income, upper_bound) - previous_upper_bound)' ensures that the income does not exceed the current bracket's upper bound
13            # and that income is not taxed twice for the lower brackets.
14            taxable_income = max(0, min(income, upper_bound) - previous_upper_bound)
15          
16            # Calculate the tax for the current bracket and accumulate it into 'total_tax'
17            total_tax += taxable_income * tax_rate
18          
19            # Update 'previous_upper_bound' to the current bracket's upper bound for the next iteration
20            previous_upper_bound = upper_bound
21      
22        # Divide the 'total_tax' by 100 to convert the tax rate to a percentage and return the result
23        return total_tax / 100
24

1class Solution {
2    public double calculateTax(int[][] brackets, int income) {
3        // `taxAmount` will store the calculated tax based on brackets.
4        int taxAmount = 0;
5      
6        // `previousBracketUpperLimit` holds the upper limit of the previous tax bracket.
7        int previousBracketUpperLimit = 0;
8      
9        for (int[] bracket : brackets) {
10            // Each bracket contains an upper limit and the tax rate percent for the bracket range.
11            int currentBracketUpperLimit = bracket[0];
12            int taxRatePercent = bracket[1];
13          
14            // Calculate the taxed income at this bracket by taking the lesser of
15            // income or the bracket's upper limit minus the previous bracket's upper limit.
16            // This is the amount of income that falls within the current bracket's range.
17            int taxedIncomeAtCurrentBracket = Math.max(0, Math.min(income, currentBracketUpperLimit) 
18                                                       - previousBracketUpperLimit);
19          
20            // Update the total taxAmount with the tax from this bracket's range.
21            taxAmount += taxedIncomeAtCurrentBracket * taxRatePercent;
22          
23            // Update the previousBracketUpperLimit for the next iteration.
24            previousBracketUpperLimit = currentBracketUpperLimit;
25        }
26      
27        // Convert the taxAmount to dollars and cents (as the percent was in whole number).
28        return taxAmount / 100.0;
29    }
30}
31

1class Solution {
2public:
3    // Function to calculate the tax based on given brackets and income
4    double calculateTax(vector<vector<int>>& brackets, int income) {
5        int tax = 0; // Variable to store the total tax
6        int prevBracketUpperLimit = 0; // Variable to keep track of the previous bracket upper limit
7
8        // Iterate over the tax brackets
9        for (const auto& bracket : brackets) {
10            int currentBracketUpperLimit = bracket[0]; // Upper limit for the current tax bracket
11            int taxRate = bracket[1]; // Tax rate for the current bracket
12
13            // Calculate the tax for the income falling within the current tax bracket range
14            // max(0, ...) ensures we don't get negative values in case income is less than the previous bracket
15            // min(income, currentBracketUpperLimit) ensures we don't calculate tax for income beyond the current bracket
16            // Subtracting prevBracketUpperLimit gives us the taxable amount in the current bracket
17            tax += max(0, min(income, currentBracketUpperLimit) - prevBracketUpperLimit) * taxRate;
18
19            prevBracketUpperLimit = currentBracketUpperLimit; // Update the previous bracket upper limit for the next iteration
20
21            // If income is less than the current bracket upper limit, no need to continue
22            if (income < currentBracketUpperLimit) {
23                break;
24            }
25        }
26
27        // Tax rates are given in percentage, divide by 100 to get the actual tax amount
28        return tax / 100.0;
29    }
30};
31

1/**
2 * Calculates the total tax based on tax brackets.
3 * Each tax bracket specifies the upper limit and the tax rate.
4 * Income is taxed in a progressive manner according to these brackets.
5 *
6 * @param brackets - An array of arrays where each inner array contains 2 numbers:
7 *                   the upper limit and the tax rate (as a percentage) for that bracket.
8 * @param income - The total income to calculate tax for.
9 * @returns The total tax calculated based on the brackets.
10 */
11function calculateTax(brackets: number[][], income: number): number {
12    let totalTax = 0; // Stores the cumulative tax amount
13    let previousBracketUpper = 0; // The upper limit of the previous bracket
14
15    // Loop over each bracket
16    for (const [currentBracketUpper, taxRatePercent] of brackets) {
17        // Calculate the taxable income for the current bracket
18        const taxableIncome = Math.max(0, Math.min(income, currentBracketUpper) - previousBracketUpper);
19      
20        // Calculate the tax for the current bracket and add it to the total tax
21        totalTax += taxableIncome * taxRatePercent;
22
23        // Update the previous bracket upper limit for the next iteration
24        previousBracketUpper = currentBracketUpper;
25    }
26
27    return totalTax / 100; // Convert percentage to a decimal representation
28}
29

Time and Space Complexity

The provided code snippet is designed to calculate taxes based on various tax brackets and the given income. Here is the analysis of both the time complexity and space complexity of the code:

Time Complexity

The time complexity of the calculateTax function is O(n), where n is the number of tax brackets. This is because the function contains a loop that iterates through each bracket exactly once.

for upper, percent in brackets:
    ans += max(0, min(income, upper) - prev) * percent
    prev = upper

Inside the loop, operations are performed in constant time, including comparisons, arithmetic operations, and variable assignments.

Space Complexity

The space complexity of the calculateTax function is O(1). The algorithm uses a fixed amount of extra space for variables ans and prev. No additional space which grows with the input size is utilized, as there are no data structures dependent on the size of the input.

ans = prev = 0

It's important to note that the input brackets, which is provided to the function, does not count towards the space complexity as it is considered input to the function and not extra space used by the function itself.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know