# Calculate Amount Paid in Taxes
**Difficulty:** EASY
[External](https://leetcode.com/problems/calculate-amount-paid-in-taxes)
Canonical: https://scaleengineer.com/dsa/problems/calculate-amount-paid-in-taxes
**Data structures:** Array
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## Problem
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 `upper0` dollars earned are taxed at a rate of `percent0`.
* The next `upper1 - upper0` dollars earned are taxed at a rate of `percent1`.
* The next `upper2 - upper1` dollars earned are taxed at a rate of `percent2`.
* 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 <= upperi <= 1000`
* `0 <= percenti <= 100`
* `0 <= income <= 1000`
* `upperi` is sorted in ascending order.
* All the values of `upperi` are **unique**.
* The upper bound of the last tax bracket is greater than or equal to `income`.

# Approaches
## Brute Force: Dollar-by-Dollar Calculation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double totalTax = 0.0;
        if (income == 0) {
            return 0.0;
        }

        for (int i = 1; i <= income; i++) {
            int lowerBound = 0;
            for (int[] bracket : brackets) {
                int upperBound = bracket[0];
                int percent = bracket[1];
                if (i > lowerBound && i <= upperBound) {
                    totalTax += 1.0 * percent / 100.0;
                    break;
                }
                lowerBound = upperBound;
            }
        }
        return totalTax;
    }
}
```
### Algorithm
1. Initialize `totalTax = 0.0`.
2. If `income` is 0, return 0.0 immediately.
3. Loop for each dollar `i` from 1 to `income`.
4.  Inside the loop, initialize `lowerBound = 0`.
5.  Loop through each `bracket` in `brackets`.
6.      Let `upper = bracket[0]` and `percent = bracket[1]`.
7.      If the current dollar `i` is greater than `lowerBound` and less than or equal to `upper`, it falls in this bracket.
8.          Calculate tax for this single dollar: `tax_for_one_dollar = 1.0 * percent / 100.0`.
9.          Add this to the total: `totalTax += tax_for_one_dollar`.
10.         Break the inner loop since the bracket for the current dollar is found.
11.     Update `lowerBound = upper` to define the range for the subsequent bracket.
12. After the outer loop finishes, return `totalTax`.

## Optimized Single Pass Iteration
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public double calculateTax(int[][] brackets, int income) {
        double totalTax = 0.0;
        int previousUpperBound = 0;

        for (int[] bracket : brackets) {
            int currentUpperBound = bracket[0];
            int percent = bracket[1];

            if (income <= previousUpperBound) {
                break;
            }

            int taxableAmount = Math.min(income, currentUpperBound) - previousUpperBound;
            totalTax += (double) taxableAmount * percent / 100.0;
            
            previousUpperBound = currentUpperBound;
        }

        return totalTax;
    }
}
```
### Algorithm
1. Initialize `totalTax = 0.0`.
2. Initialize `previousUpperBound = 0`.
3. Loop through each `bracket` in the `brackets` array.
4.      Let `upper = bracket[0]` and `percent = bracket[1]`.
5.      If `income <= previousUpperBound`, it means all income has been taxed, so break the loop.
6.      Calculate the taxable amount in this bracket: `taxableAmount = Math.min(income, upper) - previousUpperBound`.
7.      Calculate the tax for this amount: `tax = (double) taxableAmount * percent / 100.0`.
8.      Add this tax to the total: `totalTax += tax`.
9.      Update `previousUpperBound = upper` for the next iteration.
10. Return `totalTax`.

# Solutions
### Java

```java
class Solution {
public
  double calculateTax(int[][] brackets, int income) {
    int ans = 0, prev = 0;
    for (var e : brackets) {
      int upper = e[0], percent = e[1];
      ans += Math.max(0, Math.min(income, upper) - prev) * percent;
      prev = upper;
    }
    return ans / 100.0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double calculateTax(vector<vector<int>> &brackets, int income) {
    int ans = 0, prev = 0;
    for (auto &e : brackets) {
      int upper = e[0], percent = e[1];
      ans += max(0, min(income, upper) - prev) * percent;
      prev = upper;
    }
    return ans / 100.0;
  }
};

```

### Python

```python
class Solution:
    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

```