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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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 (

the array of final prices and (
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.

Compute discounted prices in a queue

Overview

Comments (0)