FastPrepMaximum Good Triplet Distance
Problem · Array

Maximum Good Triplet Distance

Learn this problem
● HardGoogle logoGoogleINTERNOA
See Google hiring insights

Problem statement

You are given an integer array A. A triplet of indices (i, j, k) is good when i < j < k and both visibility conditions hold:

  • For every index p with i < p < j, A[p] < A[i] and A[p] < A[j].
  • For every index q with j < q < k, A[q] < A[j] and A[q] < A[k].

Return the maximum possible index distance k - i among all good triplets. Return -1 if no good triplet exists.

Function

maximumGoodTripletDistance(A: int[]) → int

Examples

Example 1

A = [5,1,4,2,6]return = 4

The triplet (0, 2, 4) is good. Value 1 is strictly below both 5 and 4, while value 2 is strictly below both 4 and 6. Its distance is 4 - 0 = 4.

Example 2

A = [3,3,1,3,3]return = 3

Equal-height endpoints block visibility through one another because every interior value must be strictly smaller. One maximum-span good triplet is (0, 1, 3), with distance 3.

Constraints

  • 3 <= A.length <= 200000
  • -10^9 <= A[i] <= 10^9

More Google problems

drafts saved locally
public int maximumGoodTripletDistance(int[] A) {
    // write your code here
}
A[5,1,4,2,6]
expected4
checking account