Happiest Triplet

Time: O(n^2)

Space: O(1)

Intuition

Find triplet (i,j,k) maximizing arr[i]*arr[j]+arr[j]*arr[k]. Fix middle element j, multiply max left and max right with it.

Algorithm

1Precompute prefixMax[i] = max(arr[0..i-1]). Precompute suffixMax[i] = max(arr[i+1..n-1]).
2For each j: candidate = prefixMax[j]*arr[j] + arr[j]*suffixMax[j]. Track maximum.

Common Pitfalls

•O(n) with prefix/suffix max arrays. Middle element determines the max possible value.

Happiest Triplet.java

Java

// Approach: Sort or brute-force check all triplets for the maximum happiness score metric.
// Time: O(n^2) Space: O(1)
import java.util.*;

class Solution {
    int[] smallestDiff(int a[], int b[], int c[]) {
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);

        int i = 0, j = 0, k = 0;
        int best = Integer.MAX_VALUE;

        int[] ans = new int[3];

        while (i < a.length && j < b.length && k < c.length) {

            int x = a[i], y = b[j], z = c[k];

            int mx = Math.max(x, Math.max(y, z));
            int mn = Math.min(x, Math.min(y, z));

            if (mx - mn < best) {
                best = mx - mn;
                ans[0] = x;
                ans[1] = y;
                ans[2] = z;
            }

            if (mn == x)
                i++;
            else if (mn == y)
                j++;
            else
                k++;
        }

        Arrays.sort(ans);
        for (int l = 0, r = 2; l < r; l++, r--) {
            int tmp = ans[l];
            ans[l] = ans[r];
            ans[r] = tmp;
        }

        return ans;
    }
}

Was this solution helpful?