algoadvance

Leetcode 2303. Calculate Amount Paid in Taxes

Problem Statement

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upper_i, percent_i] means that the i-th tax bracket has an upper bound of upper_i and is taxed at a rate of percent_i. The brackets are sorted by upper_i in ascending order.

An integer income represents the amount of money you made. You need to compute the total amount of taxes you need to pay based on the given tax brackets.

The tax is calculated progressively:

Return the total amount of taxes you need to pay as a double.

Clarifying Questions

  1. Question: What is the input range for income and the values within brackets? Answer: Typically, problems like these are constrained to reasonable financial values, but we would need to check the problem constraints explicitly for limits.

  2. Question: Are the percent_i values given as integers or floating-point numbers? Answer: They are integer percentages. For example, percent_i = 10 means a 10% tax rate.

  3. Question: Should the final tax amount be rounded or formatted to a specific precision? Answer: Typically, such problems expect at least two decimal places precision, but we should confirm based on the problem statement.

Strategy

  1. Initialize totalTax as 0.0 to store the accumulated tax.
  2. Define previousUpper as 0 to represent the lower bound of the current bracket being processed.
  3. Iterate through each bracket:
    • Calculate the taxable portion within the current bracket: currentUpper - previousUpper.
    • If the current income is less than or equal to the current bracket’s upper bound, calculate the tax for the remaining income, and then break out of the loop.
    • Otherwise, calculate the tax for the full bracket range and update the previousUpper.
  4. Return the accumulated totalTax.

Code

Here’s the C++ implementation for the given strategy:

#include <vector>
using namespace std;

class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        double totalTax = 0.0;
        int previousUpper = 0;

        for (const auto& bracket : brackets) {
            int currentUpper = bracket[0];
            int percent = bracket[1];

            if (income <= currentUpper) {
                totalTax += (income - previousUpper) * percent / 100.0;
                break;
            } else {
                totalTax += (currentUpper - previousUpper) * percent / 100.0;
                previousUpper = currentUpper;
            }
        }

        return totalTax;
    }
};

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of tax brackets. This is because we iterate through each bracket once to calculate the tax. The space complexity is (O(1)) as no extra space is required aside from a few variables.

We should test the solution with various cases, including edge cases like income being exactly on bracket thresholds, being 0, and more to ensure complete robustness.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI