1899. Merge Triplets to Form Target Triplet

📝 Problem Details

• Title: 1899. Merge Triplets to Form Target Triplet
• Link: https://leetcode.com/problems/merge-triplets-to-form-target-triplet/
• Difficulty: Medium
• Tags/Categories: Greedy

you are given a list of triplets where triplets[i] = [ai, bi, ci] you can pick triplets only if they do not exceed target = [x,y,z] in any dimension you can merge picked triplets by taking the max in each dimension return true if its possible to merge some triplets to obtain the exact target

💭What Were My Initial Thoughts?

- brute force would be to try every subset and merge them
- sorting doesnt seem useful since merging is based on `max()` in each dimension

- greedy:
	- ignore any triplet where any element exceeds target[i] (they can never be merged to reach the target)
	- track whether we can construct each component (x,y,z) from some triplet
	- if we find a triplet contributing to each x,y,z we return true

💡 Explanation of Solution

Greedy: relies on an observation** that eliminates the need to **explicitly construct and track the merged triplet

1. filter valid triplets: only keep those where :
	a <= x
	b <= y
	c <= z

2. Use three boolean flags (hasX, hasY, hasZ)
	- if a triplet has a == x, set hasX to true
	- if a triplet has b == y, set hasY to true
	- if a triplet has c == z, set has Z to true

3. if all three flags are true, return true, otherwise return false 

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& target) {
        bool hasX = false;
        bool hasY = false;
        bool hasZ = false;
 
        for(auto& t : triplets) {
            // ignore invalid triplets that exceed target values
            if(t[0] > target[0]
            || t[1] > target[1]
            || t[2] > target[2]) continue;
 
            // check if this triplet contributes to achieving the target
            if(t[0] == target[0]) hasX = true;
            if(t[1] == target[1]) hasY = true;
            if(t[2] == target[2]) hasZ = true;
        
            // if all three components are found return true
            if(hasX && hasY && hasZ) return true;
        }
 
        return false;
    }
};