Quick Overview

Sum item costs discounted by the minimum earlier price with a prefix-minimum scan, preserving negative costs and avoiding current-item discount errors.

Sum Prices Discounted by the Minimum Earlier Price

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

For an integer array `prices`, the first item's cost is `prices[0]`. For each later index i, its cost is `prices[i]` minus the minimum price at a strictly earlier index. Return the sum of all item costs. ### Constraints & Assumptions Interpret the reported earlier-price range as indices 0 through i-1. Do not clamp a negative cost to zero: the stated formula allows it. Define the empty-array total as zero for this practice version. ### Clarifying Questions to Ask - Is the current item excluded from the discount minimum? - Should negative computed costs remain negative as the formula specifies? ```hint Reuse the prefix information When advancing one index, only one new price can change the minimum of all earlier prices. ``` ### What a Strong Answer Covers - Maintaining the minimum of the strictly earlier prefix. - Adding the current cost before updating that minimum. - Empty/singleton input, decreasing prices, and integer range. ### Follow-up Questions - Could the total be computed from a stream without storing the array? - How would the problem change if the discount used only the previous w prices?

Overview: Sum item costs discounted by the minimum earlier price with a prefix-minimum scan, preserving negative costs and avoiding current-item discount errors.

Read the full PayPal Software Engineer interview experience this question came from

Given an integer array `prices`, return the total cost of the items. The first item costs `prices[0]`. For each later item at index `i`, its cost is `prices[i]` minus the smallest price at any strictly earlier index. Keep negative costs in the sum. If `prices` is empty, return `0`.

Constraints

  • prices contains 0 through 2^31 - 1 integers.
  • Each price and the exact final total are between -(2^53 - 1) and 2^53 - 1, inclusive.
  • Intermediate sums and item costs can extend beyond the final total's range.

Examples

Input: ([7, 5, 9, 4, 8],)

Expected Output: 12

Explanation: The individual costs in order are 7, -2, 4, -1, and 4.

Input: ([12, 9, 3],)

Expected Output: 3

Explanation: The costs are 12, -3, and -6. Both negative costs contribute to the sum.

Hints

  1. For an item that costs less than every earlier item, work out its contribution before moving to the next index.

Sum Prices Discounted by the Minimum Earlier Price

easyPayPalSoftware Engineer

Given an integer array prices, return the total cost of the items. The first item costs prices[0]. For each later item at index i, its cost is prices[i] minus the smallest price at any strictly earlier index. Keep negative costs in the sum. If prices is empty, return 0.

Examples

Example 1
Input
([7, 5, 9, 4, 8],)
Output
12
Notes
The individual costs in order are 7, -2, 4, -1, and 4.
Example 2
Input
([12, 9, 3],)
Output
3
Notes
The costs are 12, -3, and -6. Both negative costs contribute to the sum.

Constraints

  • •prices contains 0 through 2^31 - 1 integers.
  • •Each price and the exact final total are between -(2^53 - 1) and 2^53 - 1, inclusive.
  • •Intermediate sums and item costs can extend beyond the final total's range.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def total_discounted_prices(prices: list[int]) -> int:
Sample call
total_discounted_prices([7, 5, 9, 4, 8])
Language
Case 1
Input
([7, 5, 9, 4, 8],)
Expected
12
Case 2
Input
([12, 9, 3],)
Expected
3

Browse More Questions

Show the approach

Approach

Scan from left to right, starting the total and the running minimum at the first price. Before processing index i, the running minimum is the smallest price at indices before i, and the total is the sum of the costs for those processed items. Add the current price minus that minimum, then update the minimum. Updating in this order keeps the current item out of its own discount. Return zero immediately for an empty list.

Use exact arithmetic. Let M = 2^53 - 1. Each difference has magnitude at most 2M. Negative costs occur only when the running minimum decreases, so their cumulative magnitude is at most 2M. A prefix total is at least -M because its first price and negative costs telescope to the prefix minimum. It is at most 3M because later negative costs can reduce it by at most 2M and the final total is at most M. Those bounds fit in signed 64 bits. The JavaScript reference accumulates with BigInt to preserve intermediates and converts the guaranteed representable result to Number.

Time complexity:
O(n) for n prices.
Space complexity:
O(1) auxiliary space.