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

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: 23

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

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays x and y with corresponding indices

Find Valid Triplet

Select 3 indices with distinct x-values

Maximize Sum

Choose triplet that maximizes sum of y-values

Key Takeaway

🎯 Key Insight: Group by x-values and keep only the best y-values from each group to efficiently find optimal triplet

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

Approach	Time	Space	Notes
✓ Hash Map Grouping	O(n² log n)	O(n)	Group indices by x-values, then find best triplet from different groups
Brute Force - Check All Triplets	O(n³)	O(1)	Try every possible combination of three distinct indices
Optimized - Top 3 from Each Group	O(n log n + k³)	O(n)	Keep only top 3 y-values per x-group, then efficiently find best triplet

Hash Map Grouping — Algorithm Steps

Group indices by their x-values in hash map
Sort each group by y-values (highest first)
Try combinations from different x-value groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by X

Organize indices by their x-values

Sort Groups

Sort each group by y-values descending

Pick Best

Choose highest y from 3 different groups

Code -

solution.c — C

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

typedef struct {
    int y;
    int index;
} Pair;

typedef struct {
    int x_val;
    Pair* pairs;
    int count;
} Group;

int comparePairs(const void* a, const void* b) {
    return ((Pair*)b)->y - ((Pair*)a)->y;
}

int solution(int* x, int* y, int n) {
    if (n < 3) return -1;
    
    Group groups[1000];
    int groupCount = 0;
    
    for (int i = 0; i < n; i++) {
        int found = -1;
        for (int j = 0; j < groupCount; j++) {
            if (groups[j].x_val == x[i]) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            groups[groupCount].x_val = x[i];
            groups[groupCount].pairs = malloc(n * sizeof(Pair));
            groups[groupCount].count = 0;
            groups[groupCount].pairs[0].y = y[i];
            groups[groupCount].pairs[0].index = i;
            groups[groupCount].count = 1;
            groupCount++;
        } else {
            groups[found].pairs[groups[found].count].y = y[i];
            groups[found].pairs[groups[found].count].index = i;
            groups[found].count++;
        }
    }
    
    if (groupCount < 3) return -1;
    
    for (int i = 0; i < groupCount; i++) {
        qsort(groups[i].pairs, groups[i].count, sizeof(Pair), comparePairs);
    }
    
    int maxSum = -1;
    for (int i = 0; i < groupCount; i++) {
        for (int j = i + 1; j < groupCount; j++) {
            for (int k = j + 1; k < groupCount; k++) {
                int sumVal = groups[i].pairs[0].y + groups[j].pairs[0].y + groups[k].pairs[0].y;
                if (sumVal > maxSum) {
                    maxSum = sumVal;
                }
            }
        }
    }
    
    for (int i = 0; i < groupCount; i++) {
        free(groups[i].pairs);
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    int x[1000], y[1000];
    int n = 0;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 1000) {
        x[n] = atoi(token);
        token = strtok(NULL, "[,]");
        n++;
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    for (int i = 0; i < n; i++) {
        y[i] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(x, y, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Sorting groups takes O(n log n), checking combinations takes O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores all n elements grouped by x-values

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler