Merge Triplets to Form Target Triplet
MediumThe problem
triplets is a list of 3-number groups. In one move you pick two triplets and replace the second with a new one, where each position holds the larger of the two numbers in that position (so [2, 5, 3] and [1, 7, 5] give [2, 7, 5]). You can make as many moves as you like. Return true if some triplet in the list can become exactly target.
- Example 1Input: triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]], target = [2, 7, 5]Output: true
Combine [2, 5, 3] with [1, 7, 5] to get [2, 7, 5].
- Example 2Input: triplets = [[3, 4, 5], [4, 5, 6]], target = [3, 2, 5]Output: false
Both triplets already have a middle number above 2, and a move never lowers a number.
- 1 ≤ len(triplets) ≤ 100,000
- Every triplet and target has exactly 3 numbers
- 1 ≤ each number ≤ 1,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Merging takes the max of each position, so a triplet with any value above the target can never be used.
The idea
Ignore triplets exceeding the target in any position; among the rest check that each target value is reached in its position by some triplet.
Target: O(n) time
Go function shape
func mergeTriplets(triplets [][]int, target []int) boolReference solution
Tested with go test. Try it yourself first, then compare.
// MergeTriplets: merging takes the max in each position, so a triplet with ANY value above the target can never
// be used. Among the usable ones, check that every target value is hit exactly by some triplet.
func MergeTriplets(triplets [][]int, target []int) bool {
var hit [3]bool
for _, t := range triplets {
if t[0] > target[0] || t[1] > target[1] || t[2] > target[2] {
continue
}
for i := 0; i < 3; i++ {
if t[i] == target[i] {
hit[i] = true
}
}
}
return hit[0] && hit[1] && hit[2]
}