Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values - Problem

Array Hash Table Greedy Sorting Heap (Priority Queue) Medium

You are given two integer arrays x and y, each of length n. You must choose three distinct indices i, j, and k such that:

x[i] != x[j]
x[j] != x[k]
x[k] != x[i]

Your goal is to maximize the value of y[i] + y[j] + y[k] under these conditions.

Return the maximum possible sum that can be obtained by choosing such a triplet of indices. If no such triplet exists, return -1.

Input & Output

Example 1 — Basic Case

$ Input: x = [1,2,1,3], y = [5,8,3,9]

› Output: 22

💡 Note: Choose indices 0, 1, 3: x[0]=1, x[1]=2, x[3]=3 (all different), sum = y[0]+y[1]+y[3] = 5+8+9 = 22

Example 2 — No Valid Triplet

$ Input: x = [1,1,1], y = [4,5,6]

› Output: -1

💡 Note: All x-values are the same (1), so no valid triplet with distinct x-values exists

Example 3 — Multiple Options

$ Input: x = [1,2,3,1,2], y = [10,5,8,7,6]

› Output: 24

💡 Note: Best triplet: indices 0,2,4 with x-values [1,3,2] and sum = 10+8+6 = 24

Constraints

3 ≤ x.length = y.length ≤ 1000
1 ≤ x[i] ≤ 100
1 ≤ y[i] ≤ 1000

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to group elements by their x-values and keep only the highest y-values from each group. The optimized approach groups by x-values, keeps top 3 candidates per group, then efficiently finds the best triplet. Time: O(n log n + k³), Space: O(n).

Common Approaches

✓ Stack

⏱️ Time: N/A Space: N/A

Brute Force - Check All Triplets

⏱️ Time: O(n³) Space: O(1)

Generate all possible triplets of indices (i,j,k) and check if their x-values are all different. Keep track of the maximum sum found.

Hash Map Grouping

⏱️ Time: O(n² log n) Space: O(n)

Create a hash map where keys are x-values and values are lists of (y-value, index) pairs. Sort each group by y-values in descending order, then try combinations from different groups.

Optimized - Top 3 from Each Group

⏱️ Time: O(n log n + k³) Space: O(n)

Group by x-values but keep only the top 3 highest y-values for each x-value. Then systematically check combinations, greatly reducing the search space.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int groups[1000][1000][2];
static int groupSizes[1000];
static int xValues[1000];
static int numXValues;

int compare(const void *a, const void *b) {
    int *pairA = (int*)a;
    int *pairB = (int*)b;
    return pairB[0] - pairA[0]; // descending order
}

int solution(int* x, int* y, int n) {
    if (n < 3) {
        return -1;
    }
    
    // Initialize
    for (int i = 0; i < 1000; i++) {
        groupSizes[i] = 0;
    }
    numXValues = 0;
    
    // Group by x-values (using offset to handle negative values)
    int offset = 500; // assuming x values are in reasonable range
    for (int i = 0; i < n; i++) {
        int idx = x[i] + offset;
        if (groupSizes[idx] == 0) {
            xValues[numXValues++] = x[i];
        }
        groups[idx][groupSizes[idx]][0] = y[i];
        groups[idx][groupSizes[idx]][1] = i;
        groupSizes[idx]++;
    }
    
    // Sort each group by y-values descending
    for (int i = 0; i < numXValues; i++) {
        int idx = xValues[i] + offset;
        qsort(groups[idx], groupSizes[idx], sizeof(int) * 2, compare);
    }
    
    if (numXValues < 3) {
        return -1;
    }
    
    int maxSum = -1;
    // Try all combinations of 3 different x-values
    for (int i = 0; i < numXValues; i++) {
        for (int j = i + 1; j < numXValues; j++) {
            for (int k = j + 1; k < numXValues; k++) {
                // Take best y-value from each group
                int idx1 = xValues[i] + offset;
                int idx2 = xValues[j] + offset;
                int idx3 = xValues[k] + offset;
                int sumVal = groups[idx1][0][0] + groups[idx2][0][0] + groups[idx3][0][0];
                if (sumVal > maxSum) {
                    maxSum = sumVal;
                }
            }
        }
    }
    
    return maxSum;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int x[1000], y[1000];
    int nx = 0, ny = 0;
    
    parseArray(line1, x, &nx);
    parseArray(line2, y, &ny);
    
    int result = solution(x, y, nx);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚡ Linearithmic Space

31.2K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen