Quick Overview

Maximize the smaller of two array values times their index distance, using the Container With Most Water objective and returning one deterministic score.

Maximize the Product of Pair Distance and Minimum Value

Company: Wayfair

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement `maximum_pair_score(nums)`. Choose two distinct indices `i` and `j` and maximize: $$ \min(nums[i], nums[j])\,|i-j|. $$ Return the maximum score, not the selected pair. Repeated values are allowed. This is the numeric form of the referenced Container With Most Water problem: there are 2 through 100,000 elements, and each integer value is between 0 and 10,000. ### Examples ```text maximum_pair_score([1,8,6,2,5,4,8,3,7]) -> 49 ``` Indices 1 and 8 give a minimum value of 7 and a distance of 7, for a score of 49. ```text maximum_pair_score([1,1]) -> 1 ``` The only distinct pair has distance 1 and minimum value 1. Multiple pairs may share the maximum, but the returned numeric score is unambiguous. Problem reference: [LeetCode 11](https://leetcode.com/problems/container-with-most-water/).

Overview: Maximize the smaller of two array values times their index distance, using the Container With Most Water objective and returning one deterministic score.

Implement `maximum_pair_score(nums)`. Choose two distinct indices `i` and `j` and maximize: $$ \min(nums[i], nums[j])\,|i-j|. $$ Return the maximum score, not the selected pair. Repeated values are allowed. This is the numeric form of the referenced Container With Most Water problem: there are 2 through 100,000 elements, and each integer value is between 0 and 10,000. ### Examples ```text maximum_pair_score([1,8,6,2,5,4,8,3,7]) -> 49 ``` Indices 1 and 8 give a minimum value of 7 and a distance of 7, for a score of 49. ```text maximum_pair_score([1,1]) -> 1 ``` The only distinct pair has distance 1 and minimum value 1. Multiple pairs may share the maximum, but the returned numeric score is unambiguous. Problem reference: [LeetCode 11](https://leetcode.com/problems/container-with-most-water/).

Constraints

  • nums contains 2 through 100000 integers, inclusive.
  • Every nums value is between 0 and 10000, inclusive.
  • The selected indices must be distinct.
  • Return only the maximum numeric score; repeated values and tied maximizing pairs are allowed.

Examples

Input: ([1,8,6,2,5,4,8,3,7],)

Expected Output: 49

Explanation: Source example: indices 1 and 8 have score 7 times 7.

Input: ([1,1],)

Expected Output: 1

Explanation: Source minimum-length example: the single pair scores 1.

Hints

  1. Only distinct indices may be paired.
  2. Different maximizing pairs can yield the same returned score.

Loading coding console...

Show the approach

Approach

Start with the leftmost and rightmost indices and record their score. If the left value is no larger than the right value, any pair using that left endpoint and a closer right endpoint has a no larger minimum and a smaller distance, so it cannot improve on the score just checked. Discard the left endpoint. The symmetric argument discards the right endpoint when its value is smaller. This argument also permits discarding the left endpoint when the values tie. Each discarded endpoint belongs only to pairs already bounded by a checked score, so the largest recorded score is the global maximum when the indices meet. Zeroes, repeated values and tied optimal pairs require no special return rule. The maximum possible score is 10000 times 99999, or 999990000, which fits the integer type used by each implementation. Each iteration shrinks the interval, giving O(n) time. The algorithm needs O(1) working space; the C++ by-value interface additionally copies the input vector.

Time complexity:
O(n)
Space complexity:
O(1) algorithmic working space; O(n) input-copy storage in the C++ by-value interface.