Merge Triplets to Form Target Triplet

NeetCode: Merge Triplets to Form Target Triplet · LeetCode: 1899. Merge Triplets to Form Target Triplet · Difficulty: Medium

You are given triplets [a, b, c] and a target = [x, y, z]. One operation picks two triplets and replaces one with their element-wise maximum. Return true if target can end up as one of the triplets. Equivalently: is there a non-empty subset of triplets whose element-wise maximum equals target?

Example

Text

Input:  triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]    Output: true
Input:  triplets = [[3,4,5],[4,5,6]],         target = [3,2,5]    Output: false

Brute force: try every subset

Enumerate all non-empty subsets with a bitmask, take the element-wise maximum of each, and compare to the target. That is 2^n subsets, so it only works for tiny inputs. The mask is an int, so the loop is valid only for n up to 30; 1 << n wraps for larger n.

Java

import java.util.Arrays;

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int n = triplets.length;
        for (int mask = 1; mask < (1 << n); mask++) {
            int[] merged = new int[3];
            for (int i = 0; i < n; i++) {
                if (((mask >> i) & 1) == 1) {
                    for (int k = 0; k < 3; k++) {
                        merged[k] = Math.max(merged[k], triplets[i][k]);
                    }
                }
            }
            if (Arrays.equals(merged, target)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mergeTriplets(new int[][]{{2, 5, 3}, {1, 8, 4}, {1, 7, 5}}, new int[]{2, 7, 5}));
        System.out.println(s.mergeTriplets(new int[][]{{3, 4, 5}, {4, 5, 6}}, new int[]{3, 2, 5}));
        System.out.println(s.mergeTriplets(new int[][]{}, new int[]{1, 1, 1}));
    }
}

Output

true
false
false

Time: O(2^n). Space: O(1).

Optimal: keep only triplets that never exceed the target

Merging can only raise values, never lower them. A triplet with a coordinate larger than the target's can never be part of a solution, because it would push that coordinate too high, so such triplets are discarded. Merging all remaining triplets gives the largest reachable value in each coordinate. The answer is true exactly when that merge equals the target, that is, each target coordinate is matched by at least one remaining triplet.

Java

import java.util.Arrays;

class Solution {
    public boolean mergeTriplets(int[][] triplets, int[] target) {
        int[] merged = new int[3];
        for (int[] t : triplets) {
            if (t[0] <= target[0] && t[1] <= target[1] && t[2] <= target[2]) {
                for (int k = 0; k < 3; k++) {
                    merged[k] = Math.max(merged[k], t[k]);
                }
            }
        }
        return Arrays.equals(merged, target);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.mergeTriplets(new int[][]{{2, 5, 3}, {1, 8, 4}, {1, 7, 5}}, new int[]{2, 7, 5}));
        System.out.println(s.mergeTriplets(new int[][]{{3, 4, 5}, {4, 5, 6}}, new int[]{3, 2, 5}));
        System.out.println(s.mergeTriplets(new int[][]{}, new int[]{1, 1, 1}));
    }
}

Output

true
false
false

Time: O(n). Space: O(1).

Java compares arrays by content only through Arrays.equals; == on arrays compares references. This relies on all triplet values being positive, as the problem guarantees, so the initial [0, 0, 0] never equals a target.