Problem Description

The "All Valid Triplets That Can Represent a Country" problem asks you to find all unique triplets in a given array nums such that each triplet can represent a country based on a specific condition. Typically, the condition is that the sum of the triplet's elements equals a given target value (sometimes 0, as in the classic 3Sum problem). The solution must:

• Return all unique triplets (nums[i], nums[j], nums[k]) such that i != j != k and nums[i] + nums[j] + nums[k] == target.
• Not reuse elements for the same triplet (no duplicate indices).
• Not return duplicate triplets (triplets with the same numbers, even if in different order, count as one).

Thought Process

At first glance, you might consider a brute-force approach: check every possible combination of three numbers in the array to see if they sum to the target. However, this quickly becomes inefficient for large arrays, since there are O(n³) possible triplets.

To improve efficiency, it's important to avoid unnecessary checks and duplicate triplets. Sorting the array enables us to use pointers to efficiently check for valid triplets and skip duplicates. This is a common optimization in problems involving unique combinations and sums.

The key insight is to fix one number, then use a two-pointer approach on the rest of the array to find pairs that, together with the fixed number, sum to the target. This reduces the time complexity significantly.

Solution Approach

Here is a step-by-step breakdown of the optimized solution:

1. Sort the Array: Start by sorting nums. This helps with duplicate management and enables the two-pointer technique.
2. Iterate with a Fixed Index: Loop through the array, fixing one element at a time (let's call it nums[i]).
3. Skip Duplicates: If the current element is the same as the previous one (and not the first), skip it to avoid duplicate triplets.
4. Two-Pointer Search:
   • Set two pointers: left (just after i) and right (at the end of the array).
   • While left < right:
     • Calculate the sum of nums[i] + nums[left] + nums[right].
     • If the sum matches the target, add the triplet to the result.
     • Move left and right to skip over duplicate values.
     • If the sum is less than the target, increment left; if it's more, decrement right.
5. Collect Results: Continue this process for each i, collecting all unique triplets.

We use sorting and pointer movement to efficiently avoid duplicates and unnecessary checks, making the solution much faster than brute force.

Example Walkthrough

Let's walk through an example with nums = [-1, 0, 1, 2, -1, -4] and target = 0:

1. Sort nums: [-4, -1, -1, 0, 1, 2]
2. Start with i = 0 (nums[0] = -4):
   • Set left = 1, right = 5.
   • Sum: -4 + -1 + 2 = -3 (less than 0), so move left to 2.
   • Sum: -4 + -1 + 2 = -3 (again), move left to 3.
   • Continue until left >= right.
3. Next, i = 1 (nums[1] = -1):
   • left = 2, right = 5.
   • Sum: -1 + -1 + 2 = 0 (found a triplet: [-1, -1, 2]).
   • Move left and right to skip duplicates.
   • Continue: -1 + 0 + 1 = 0 (found [-1, 0, 1]).
4. Continue with i = 2 (nums[2] = -1), but since it's a duplicate of nums[1], skip it.
5. Continue for remaining i values; no new triplets found.

Final result: [[-1, -1, 2], [-1, 0, 1]]

Time and Space Complexity

Brute-force approach:

• Time complexity: O(n³), since it checks every possible triplet.
• Space complexity: O(1) (not counting output), but may use extra space to store results.

• Time complexity: O(n²). Sorting is O(n log n), and for each of the n elements, the two-pointer scan is O(n).
• Space complexity: O(1) extra (ignoring the space for the output list), since we only use pointers and indices.

The optimization comes from reducing the number of unnecessary checks and efficiently skipping duplicates.

Summary

To find all valid triplets representing a country (i.e., summing to a target value), we use sorting and a two-pointer approach to avoid duplicates and reduce computation. By fixing one number and searching for pairs with two pointers, we achieve an efficient O(n²) solution. The approach is elegant because it combines the strengths of sorting for duplicate management and the two-pointer technique for efficient searching, making it both fast and robust.

Code Implementation

def all_valid_triplets(nums, target):
    nums.sort()
    n = len(nums)
    result = []
    for i in range(n):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # Skip duplicate 'i'
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left-1]:
                    left += 1  # Skip duplicate 'left'
                while left < right and nums[right] == nums[right+1]:
                    right -= 1  # Skip duplicate 'right'
            elif s < target:
                left += 1
            else:
                right -= 1
    return result
      

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> allValidTriplets(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> result;
    for (int i = 0; i < n; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == target) {
                result.push_back({nums[i], nums[left], nums[right]});
                ++left; --right;
                while (left < right && nums[left] == nums[left-1]) ++left;
                while (left < right && nums[right] == nums[right+1]) --right;
            } else if (sum < target) {
                ++left;
            } else {
                --right;
            }
        }
    }
    return result;
}
      

import java.util.*;

public class Solution {
    public List<List<Integer>> allValidTriplets(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++; right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}
      

function allValidTriplets(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const result = [];
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1, right = n - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (left < right && nums[left] === nums[left - 1]) left++;
                while (left < right && nums[right] === nums[right + 1]) right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}