How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Plaid.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Plaid during technical interviews.

Compute discounted prices in a queue

Q: Compute discounted prices in a queue

This question evaluates proficiency in array processing, algorithm design, use of auxiliary data structures such as monotonic stacks, and formal complexity and correctness reasoning.

Company: Plaid

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an integer array prices where prices[i] is the price of the i-th item in a checkout line, apply the following rule: for each i, find the first j > i such that prices[j] <= prices[i]; if such j exists, the item's discount is prices[j], so its final price is prices[i] - prices[j]; otherwise, no discount applies. Return both ( 1) the array of final prices and ( 2) the total savings across all items. Solve in O(n) time using an appropriate data structure, prove correctness, analyze time/space complexity, and provide code in a language of your choice along with brief tests.

Quick Answer: This question evaluates proficiency in array processing, algorithm design, use of auxiliary data structures such as monotonic stacks, and formal complexity and correctness reasoning.

You are given an integer array prices where prices[i] is the price of the i-th item in a checkout line. For each item i, find the first index j > i such that prices[j] <= prices[i]. If such a j exists, the discount for item i is prices[j], so its final price becomes prices[i] - prices[j]. Otherwise, the item keeps its original price. Return both: (1) the array of final prices for all items, and (2) the total savings across all items. Your solution should run in O(n) time using an appropriate data structure. A strong explanation should justify why the chosen data structure always finds the first valid discount for each item.

Constraints

0 <= len(prices) <= 200000
0 <= prices[i] <= 1000000000

Examples

Input: ([8, 4, 6, 2, 3],)

Expected Output: ([4, 2, 4, 2, 3], 8)

Explanation: Item 8 gets discount 4, item 4 gets discount 2, item 6 gets discount 2, and the last two items get no discount. Total savings are 4 + 2 + 2 = 8.

Input: ([1, 2, 3, 4, 5],)

Expected Output: ([1, 2, 3, 4, 5], 0)

Explanation: No item has a later price that is smaller than or equal to it, so no discounts apply.

Input: ([10, 1, 1, 6],)

Expected Output: ([9, 0, 1, 6], 2)

Explanation: 10 is discounted by the first 1, the second item 1 is discounted by the next 1, and the remaining two items receive no discount.

Input: ([5],)

Expected Output: ([5], 0)

Explanation: A single item has no later item, so it cannot receive a discount.

Input: ([],)

Expected Output: ([], 0)

Explanation: An empty list produces no final prices and no savings.

Solution

def solution(prices):
    final_prices = prices[:]
    total_savings = 0
    stack = []  # indices waiting for their first qualifying discount

    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] >= price:
            idx = stack.pop()
            final_prices[idx] = prices[idx] - price
            total_savings += price
        stack.append(i)

    return final_prices, total_savings

Time complexity: O(n). Space complexity: O(n).

Hints

As you scan from left to right, some earlier items are still waiting for the first later price that is smaller than or equal to them.
A monotonic increasing stack of indices lets each item be pushed and popped at most once, which gives O(n) time.

Quick Overview

This question evaluates proficiency in array processing, algorithm design, use of auxiliary data structures such as monotonic stacks, and formal complexity and correctness reasoning.