Katkat
Back

Maximize the Product of Pair Distance and Minimum Value

WayfairSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests optimal two-pointer and greedy reasoning to maximize a distance-weighted minimum value pair in linear time.

Problem Statement

In a Wayfair fulfillment center, storage bins of varying vertical dividers are arranged in a single row. You are given an integer array heights of length n, where heights[k] represents the height of the divider at index k.

You want to choose two distinct dividers at indices i and j (with 0 <= i < j < n) to form the boundary of a storage section. The capacity score of the section formed by these two dividers is calculated as the distance between them multiplied by the height of the shorter divider:

score = (j - i) * min(heights[i], heights[j])

Write a function to determine the maximum capacity score that can be formed by any pair of dividers.

Function Signature

def max_capacity_score(heights: list[int]) -> int:
    pass

Input and Output Format

  • Input: A list of integers heights where len(heights) >= 2.
  • Output: A single integer representing the maximum capacity score achievable.

Constraints

  • 2 <= len(heights) <= 100,000
  • 0 <= heights[i] <= 10,000

Examples

Example 1

Input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Explanation: 
Choosing index 1 (height 8) and index 8 (height 7) yields:
(8 - 1) * min(8, 7) = 7 * 7 = 49.
No other pair produces a higher score.

Example 2

Input: heights = [4, 3, 2, 1, 4]
Output: 16
Explanation:
Choosing index 0 (height 4) and index 4 (height 4) yields:
(4 - 0) * min(4, 4) = 4 * 4 = 16.

Example 3

Input: heights = [1, 2, 1]
Output: 2
Explanation:
Choosing index 0 and index 2 yields (2 - 0) * min(1, 1) = 2.

Edge Cases

  • Minimum length array (len(heights) == 2).
  • Arrays with zeroes (e.g., all zeroes or zeroes at the boundaries).
  • Strictly increasing or strictly decreasing heights.

Hints

Hint 1

Start by evaluating the widest possible pair using pointers at the extreme left and right ends of the array.

Hint 2

The area is bottlenecked by the shorter of the two boundaries; moving the taller boundary inward can only decrease or maintain the height while definitely decreasing width.

Hint 3

Advance the pointer pointing to the smaller height inward at each step to check for taller potential boundaries.

Follow-up questions

  • How would you return the exact indices (i, j) that produce the optimal score, breaking ties by minimizing the starting index i?
  • If the array elements could be negative, would the two-pointer greedy choice still guarantee an optimal solution? Why or why not?
  • How would your algorithm change if each step of distance had an additional constant penalty subtracted from the score, i.e., score = (j - i) * min(h[i], h[j]) - C * (j - i)?