Katkat
Back

Count Seat-Price Trios Within a Budget Spread

IBMSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Count how many trios of resale-marketplace seat listings have prices within a fixed budget spread of each other, using sorting and a two-pointer sweep instead of an O(n^3) scan.

A ticket resale marketplace lists seats with asking prices. A buyer looking to grab three seats together wants to know how many groups of three listings have prices close enough to each other to feel like "the same price tier."

You're given an array prices and a non-negative integer d, the maximum allowed spread. A trio is a choice of three distinct positions i < j < k. Its spread is the largest of prices[i], prices[j], prices[k] minus the smallest of the three. A trio is valid when its spread is at most d.

Return the number of valid trios.

def count_price_trios(prices: list[int], d: int) -> int:

Rules

  • Trios are identified by position, not by value. Two trios with different sets of indices are different trios, even if the values are equal, and each set of three positions is counted exactly once.
  • The three prices in a trio may be equal; three equal prices have spread 0.
  • The bound is inclusive: a spread exactly equal to d is valid.
  • If prices has fewer than three listings, return 0.

Constraints

  • 0 <= len(prices) <= 100000
  • 0 <= prices[i] <= 10^9
  • 0 <= d <= 10^9
  • The answer can be as large as C(100000, 3) ~ 1.67 * 10^14, which exceeds a 32-bit signed integer. Use a 64-bit counter.

Examples

Example 1

prices = [50, 52, 54, 56, 58], d = 4
answer = 3

The valid trios hold the values {50, 52, 54}, {52, 54, 56}, and {54, 56, 58}. Every other trio spreads at least 6.

Example 2

prices = [80, 30, 30, 60, 45], d = 15
answer = 1

Only positions 1, 2, and 4, holding 30, 30, and 45, spread by at most 15.

Example 3

prices = [99, 99, 99, 99], d = 0
answer = 4

All four ways to choose three of the four listings are valid, since every trio has spread 0.

Hints

Hint 1

Whether a trio is valid depends only on the multiset of three values involved, not on their original positions. What happens to the count if you sort the array first?

Hint 2

After sorting, assign each valid trio to its rightmost (largest) element and avoid double counting.

Hint 3

For a fixed right end r, every eligible partner sits in one contiguous block to its left. How many ways are there to choose two partners from a block of size m?

Hint 4

As r increases, the left edge of that block never needs to move backward — a single forward-moving pointer sweeps the whole array in O(n).

Follow-up questions

  • How would you count valid groups of size k instead of exactly 3?
  • If prices arrive as a stream and you only care about the last W listings, how would you maintain the count?
  • How would you return the actual trios instead of just the count, and what does that cost in the worst case?
  • Suppose the condition flipped to "spread at least d" instead of "at most d." How would you adapt this approach?