Welcome to Subscribe On Youtube

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

Description

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.

 

Example 1:

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

Output: 14

Explanation:

• Choose i = 0 (x[i] = 1, y[i] = 5), j = 1 (x[j] = 2, y[j] = 3), k = 3 (x[k] = 3, y[k] = 6).
• All three values chosen from x are distinct. 5 + 3 + 6 = 14 is the maximum we can obtain. Hence, the output is 14.

Example 2:

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

Output: -1

Explanation:

• There are only two distinct values in x. Hence, the output is -1.

 

Constraints:

• n == x.length == y.length
• 3 <= n <= 105
• 1 <= x[i], y[i] <= 106

Solutions

Solution 1: Sorting + Greedy + Hash Table

We pair the elements of arrays $x$ and $y$ into a 2D array $\textit{arr}$, and then sort $\textit{arr}$ in descending order by the value of $y$. Next, we use a hash table to record the $x$ values that have already been selected, and iterate through $\textit{arr}$, each time selecting an $x$ value and its corresponding $y$ value that has not been chosen yet, until we have selected three distinct $x$ values.

If we manage to select three different $x$ values during the iteration, we return the sum of their corresponding $y$ values; if we finish iterating without selecting three distinct $x$ values, we return -1.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of arrays $\textit{x}$ and $\textit{y}$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• class Solution {
      public int maxSumDistinctTriplet(int[] x, int[] y) {
          int n = x.length;
          int[][] arr = new int[n][0];
          for (int i = 0; i < n; i++) {
              arr[i] = new int[] {x[i], y[i]};
          }
          Arrays.sort(arr, (a, b) -> b[1] - a[1]);
          int ans = 0;
          Set<Integer> vis = new HashSet<>();
          for (int i = 0; i < n; ++i) {
              int a = arr[i][0], b = arr[i][1];
              if (vis.add(a)) {
                  ans += b;
                  if (vis.size() == 3) {
                      return ans;
                  }
              }
          }
          return -1;
      }
  }
  

• class Solution {
  public:
      int maxSumDistinctTriplet(vector<int>& x, vector<int>& y) {
          int n = x.size();
          vector<array<int, 2>> arr(n);
          for (int i = 0; i < n; ++i) {
              arr[i] = {x[i], y[i]};
          }
          ranges::sort(arr, [](auto& a, auto& b) {
              return b[1] < a[1];
          });
          int ans = 0;
          unordered_set<int> vis;
          for (int i = 0; i < n; ++i) {
              int a = arr[i][0], b = arr[i][1];
              if (vis.insert(a).second) {
                  ans += b;
                  if (vis.size() == 3) {
                      return ans;
                  }
              }
          }
          return -1;
      }
  };
  
  

• class Solution:
      def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
          arr = [(a, b) for a, b in zip(x, y)]
          arr.sort(key=lambda x: -x[1])
          vis = set()
          ans = 0
          for a, b in arr:
              if a in vis:
                  continue
              vis.add(a)
              ans += b
              if len(vis) == 3:
                  return ans
          return -1
  
  

• func maxSumDistinctTriplet(x []int, y []int) int {
  	n := len(x)
  	arr := make([][2]int, n)
  	for i := 0; i < n; i++ {
  		arr[i] = [2]int{x[i], y[i]}
  	}
  	sort.Slice(arr, func(i, j int) bool {
  		return arr[i][1] > arr[j][1]
  	})
  	ans := 0
  	vis := make(map[int]bool)
  	for i := 0; i < n; i++ {
  		a, b := arr[i][0], arr[i][1]
  		if !vis[a] {
  			vis[a] = true
  			ans += b
  			if len(vis) == 3 {
  				return ans
  			}
  		}
  	}
  	return -1
  }
  
  

• function maxSumDistinctTriplet(x: number[], y: number[]): number {
      const n = x.length;
      const arr: [number, number][] = [];
      for (let i = 0; i < n; i++) {
          arr.push([x[i], y[i]]);
      }
      arr.sort((a, b) => b[1] - a[1]);
      const vis = new Set<number>();
      let ans = 0;
      for (let i = 0; i < n; i++) {
          const [a, b] = arr[i];
          if (!vis.has(a)) {
              vis.add(a);
              ans += b;
              if (vis.size === 3) {
                  return ans;
              }
          }
      }
      return -1;
  }
  
  

• impl Solution {
      pub fn max_sum_distinct_triplet(x: Vec<i32>, y: Vec<i32>) -> i32 {
          let n = x.len();
          let mut arr: Vec<(i32, i32)> = (0..n).map(|i| (x[i], y[i])).collect();
          arr.sort_by(|a, b| b.1.cmp(&a.1));
          let mut vis = std::collections::HashSet::new();
          let mut ans = 0;
          for (a, b) in arr {
              if vis.insert(a) {
                  ans += b;
                  if vis.len() == 3 {
                      return ans;
                  }
              }
          }
          -1
      }
  }
  
  

All Problems

All Solutions