Find a triplet that sum to a given value in c#

Programming C#
1

To find a triplet in an array that sums to a given value in C#, you can use a two-pointer approach after sorting the array. This method is efficient and works in O(n^2) time complexity. Here’s a step-by-step explanation and a sample implementation:

Explanation:

  1. Sort the Array: Begin by sorting the input array. Sorting allows us to use the two-pointer technique effectively.

  2. Iterate through the Array: For each element in the array (consider it as the first element of the triplet), use two pointers to find two other elements that, when added to the first element, equal the target sum.

  3. Two-Pointer Technique:

    • Set one pointer at the next element (left pointer) and the other at the end of the array (right pointer).
    • Calculate the sum of the three elements (the current element and the two pointed to).
    • If the sum is equal to the target, store the triplet.
    • If the sum is less than the target, move the left pointer to the right to increase the sum.
    • If the sum is greater than the target, move the right pointer to the left to decrease the sum.

  4. Skip Duplicates: If you encounter duplicate elements, you may want to skip them to avoid duplicate triplet results.

Sample Code:

using System;
using System.Collections.Generic;

class TripletFinder
{
    public static List<List<int>> FindTriplets(int[] arr, int target)
    {
        List<List<int>> triplets = new List<List<int>>();
        Array.Sort(arr); // Step 1: Sort the array

        for (int i = 0; i < arr.Length - 2; i++)
        {
            if (i > 0 && arr[i] == arr[i - 1]) continue; // Skip duplicates

            int left = i + 1; // Left pointer
            int right = arr.Length - 1; // Right pointer

            while (left < right)
            {
                int sum = arr[i] + arr[left] + arr[right];

                if (sum == target)
                {
                    triplets.Add(new List<int> { arr[i], arr[left], arr[right] });

                    // Skip duplicates for left and right
                    while (left < right && arr[left] == arr[left + 1]) left++;
                    while (left < right && arr[right] == arr[right - 1]) right--;

                    left++;
                    right--;
                }
                else if (sum < target)
                {
                    left++; // Increase sum
                }
                else
                {
                    right--; // Decrease sum
                }
            }
        }

        return triplets;
    }

    static void Main()
    {
        int[] arr = { 1, 2, -2, -1, 0, 3 };
        int target = 0;
        List<List<int>> result = FindTriplets(arr, target);

        foreach (var triplet in result)
        {
            Console.WriteLine($"[{string.Join(", ", triplet)}]");
        }
    }
}

How It Works:

  1. Sorting: The array is sorted to facilitate the two-pointer technique.
  2. Outer Loop: It iterates through each element, treating it as the first element of the triplet.
  3. Inner Loop with Two Pointers: The inner loop uses two pointers to find pairs that sum to the target when added to the current element.
  4. Result: The found triplets are added to a list and printed at the end.

Time Complexity:

  • Sorting: O(n log n)
  • Two-pointer search: O(n^2)
  • Overall, the complexity is O(n^2) due to the nested loop structure after sorting.

This method is efficient and works well for reasonably sized arrays.

1 Like