Compute discounted prices and full-price indices
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an array `prices` of length \(n\). Items are sold from left to right, and each item’s final selling price is computed as follows:
For item \(i\):
- Find the **first** index \(j > i\) such that `prices[j] <= prices[i]`.
- If such \(j\) exists, the final price is `prices[i] - prices[j]`.
- Otherwise, the final price is `prices[i]` (sold at full price).
You must output **two lines**:
1. The **total** of all final prices.
2. All indices (0-based) of items that are sold at **full price**, in increasing order.
### Input
- Integer \(n\)
- Array `prices` of length \(n\)
### Output
- Line 1: integer total final price
- Line 2: space-separated 0-based indices sold at full price (print an empty line if none)
### Example (informal)
If `prices = [5, 1, 3]`, then item 0 is discounted by 1 (final 4), item 1 has no qualifying item to its right (final 1), item 2 has none (final 3). Total = 8, full-price indices = `1 2`.
Quick Answer: This question evaluates array-processing skills, competency with next-smaller-or-equal element patterns, and the ability to compute aggregated results under ordering constraints.
You are given an integer n and an array prices of length n. Items are processed from left to right. For each item i, find the first index j > i such that prices[j] <= prices[i]. If such an index exists, the final selling price of item i is prices[i] - prices[j]; otherwise, the item is sold at full price and its final selling price is prices[i]. Compute the total of all final selling prices and identify every 0-based index that is sold at full price. For this function-based version, return a tuple (total, indices), where indices is the list of full-price indices in increasing order.
Constraints
- 0 <= n <= 2 * 10^5
- len(prices) == n
- 0 <= prices[i] <= 10^9
- Use a 64-bit integer type for the total in languages with fixed-size integers
Examples
Input: (3, [5, 1, 3])
Expected Output: (8, [1, 2])
Explanation: Item 0 is discounted by prices[1] = 1, so its final price is 4. Items 1 and 2 have no qualifying item to their right, so they are sold at full price. Total = 4 + 1 + 3 = 8.
Input: (5, [8, 4, 6, 2, 3])
Expected Output: (15, [3, 4])
Explanation: Final prices are [4, 2, 4, 2, 3]. Items at indices 3 and 4 have no smaller-or-equal item to their right.
Hints
- Try scanning from left to right while keeping track of earlier items that still have not found a discount.
- If the current price is less than or equal to some previous prices, it becomes the first valid discount for those previous items.