Calculate amount paid in taxes

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upperᵢ, percentᵢ] means that the ith tax bracket has an upper bound of upperᵢ and is taxed at a rate of percentᵢ. The brackets are sorted by upper bound (i.e. upperᵢ < upperᵢ 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⁻⁵ of the actual answer will be accepted.

Constraints:

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

Approach: Iterative Simulation

func calculateTax(brackets [][]int, income int) float64 {
    lastUpper := 0
    result := 0 
    for _, bracket := range brackets {
        upper := bracket[0]
        rate := bracket[1]
        if income > upper {
            result += (upper - lastUpper) * rate
        } else {
            result += (income - lastUpper) * rate
            break
        }
        lastUpper = upper
    }
    return float64(result) / 100
}

Time Complexity O(N)

Space Complexity O(1)

Intuition

The solution simulates the tax calculation by iterating through each tax bracket and calculating the tax for the income that falls within that bracket. For each bracket, if the total income exceeds the bracket's upper limit, the full tax for that bracket is applied. Otherwise, only the portion of income within the bracket is taxed.

Algorithm

Initialize Variables:
- lastUpper tracks the lower bound of the current tax bracket.
- result accumulates the total tax (in percentage units).
Iterate Over Tax Brackets:
- For each bracket, extract the upper limit and rate.
- If the income is greater than the upper limit:
  - Calculate the tax for the entire span of the bracket: (upper - lastUpper) * rate.
- Otherwise, compute the tax for the remaining income: (income - lastUpper) * rate and break out of the loop since no further brackets apply.
Return the Result:
- Convert the accumulated tax (which is in integer percentage units) to a floating-point number by dividing by 100.

Complexity Analysis

Time Complexity:
O(n) where n is the number of tax brackets. The algorithm processes each bracket once.
Space Complexity:
O(1) as only a fixed number of extra variables are used regardless of the input size.

Wrap up

If you found this guide helpful, consider subscribing to my newsletter on jyotirmoy.dev/blogs , You can also follow me on Twitter jyotirmoydotdev for updates and more content.