Final Costs After a Supply Discount - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Standard (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the problem?
    • A: The input is an integer array costs, where costs[i] represents the cost of the ith supply item.
  • Q: What is the output?
    • A: The output is an integer array final_costs where each element represents the final cost of the corresponding item after applying the special discount.
  • Q: How is the discount applied?
    • A: For each item, the discount is the cost of the first subsequent item that is less than or equal to the current item's cost. If no such item exists, no discount is applied.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to keep track of the indices of the supply items that have not yet found their discount. As you iterate through the list, if the current item’s cost is less than or equal to the cost of the item at the top of the stack, apply the discount to the item at the stack's top and update the final cost.

1. Initialize `final_costs` as a copy of `costs` to store the discounted prices.
2. Initialize an empty stack to keep track of indices of items that have not yet received a discount.
3. Iterate through the `costs` array:
   1. For each item, check the stack:
      * While the stack is not empty and the current item's cost is less than or equal to the cost of the item at the top of the stack, pop the index from the stack and apply the discount.
      * Subtract the current item's cost from the cost of the item at the popped index in `final_costs`.
   2. Push the current index onto the stack.
4. Return the `final_costs` array.

⚠️ Common Mistakes

  • Forgetting to check the stack for items that need a discount applied.
  • Incorrectly applying the discount, such as subtracting the wrong value or applying it to the wrong item.
  • Not handling the case where no discount can be applied, leaving the original cost unchanged.

I-mplement

def final_supply_costs(costs):
    n = len(costs)
    final_costs = costs[:]
    stack = []

    for i in range(n):
        while stack and costs[stack[-1]] >= costs[i]:
            j = stack.pop()
            final_costs[j] -= costs[i]
        stack.append(i)

    return final_costs

# Example usage
print(final_supply_costs([8, 4, 6, 2, 3]))  # Output: [4, 2, 4, 2, 3]
print(final_supply_costs([1, 2, 3, 4, 5]))  # Output: [1, 2, 3, 4, 5]
print(final_supply_costs([10, 1, 1, 6]))    # Output: [9, 0, 1, 6]