TIP102 Unit 3 Session 2 Standard (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
costs
, where costs[i]
represents the cost of the i
th supply item.final_costs
where each element represents the final cost of the corresponding item after applying the special discount.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
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]