How should I practice Disjoint Target-Sum Triplets?

Start by reading the full statement, solve the visible examples, then compare the pattern against related American Express phone screen problems in FastPrep.

Is Disjoint Target-Sum Triplets associated with American Express?

FastPrep tags this as a American Express phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Disjoint Target-Sum Triplets

Learn this problem

● Medium

American ExpressFULLTIMEPHONE SCREEN

Problem statement

You are given an integer array nums, representing a finite stream of integers, and an integer target.

A candidate triplet is a value triplet [a, b, c] such that a <= b <= c, a + b + c = target, and nums contains enough occurrences of its values.

Consider all distinct candidate triplets in lexicographic order. Starting with the full multiset of input occurrences, accept a candidate if all of its required occurrences are still available, then consume those occurrences. Otherwise skip it. Return the accepted triplets in that order.

Each value triplet can appear at most once, and no input occurrence can be used by more than one returned triplet.

Function

disjointTargetTriplets(nums: int[], target: int) → int[][]

Examples

Example 1

nums = [1,2,3,4,5,0]target = 6return = [[0,1,5]]

The first candidate is [0,1,5], so it is accepted and those occurrences are consumed. Every later candidate summing to 6 needs either 0 or 1, so it is skipped.

Example 2

nums = [2,2,2,2,2,2]target = 6return = [[2,2,2]]

[2,2,2] is the only distinct value triplet. It is returned once even though another three occurrences remain.

Example 3

nums = [-4,-1,-1,0,1,2,5]target = 0return = [[-4,-1,5],[-1,0,1]]

The lexicographically first candidate consumes -4, one -1, and 5. The later candidate [-1,0,1] can use the remaining -1.

Constraints

1 <= nums.length <= 2000.
-10^9 <= nums[i] <= 10^9.
-10^9 <= target <= 10^9.
Use sufficiently wide arithmetic when computing a complement or sum.