Triplet Family

Given an array arr of integers. Find whether three numbers are such that the sum of two elements equals the third element.

Example:

Input: arr[] = [1, 2, 3, 4, 5]
Output: true
Explanation: The pair (1, 2) sums to 3.

Input: arr[] = [5, 3, 4]
Output: false
Explanation: No triplets satisfy the condition.

Expected Time Complexity: O(n²)
Expected Auxilary Space: O(1)

Constraints:
1 <= arr.size() <= 10³
0 <= arr[i] <= 10⁵

Approach 01:

class Solution {
  public:
    bool findTriplet(vector<int>& arr) {
        unordered_map<int, int> elementFrequency;
        int arraySize = arr.size();

        if (arraySize < 3) {
            return false;
        }

        for (int &element : arr) {
            ++elementFrequency[element];
        }

        for (int i = 0; i < arraySize - 1; i++) {
            for (int j = i + 1; j < arraySize; j++) {
                int pairSum = arr[i] + arr[j];
                if (elementFrequency[pairSum] != 0) {
                    return true;
                }
            }
        }

        return false;
    }
};

class Solution:
    def findTriplet(self, arr):
        elementFrequency = {}
        arraySize = len(arr)

        if arraySize < 3:
            return False

        for element in arr:
            elementFrequency[element] = elementFrequency.get(element, 0) + 1

        for i in range(arraySize - 1):
            for j in range(i + 1, arraySize):
                pairSum = arr[i] + arr[j]
                if elementFrequency.get(pairSum, 0) != 0:
                    return True

        return False

Time Complexity

• Building the Frequency Map:

  The unordered map elementFrequency is populated in a single loop over the array, which takes \(O(n)\), where \(n\) is the size of the array.

• Checking Pair Sums:

  The algorithm then uses a nested loop to check all pairs of elements in the array. The first loop runs \(n-1\) times, and the second loop runs \(n-i-1\) times for each iteration of the first loop. This results in \(O(n^2)\) comparisons.

• Checking in the Frequency Map:

  For each pair, checking whether their sum exists in the unordered map is an \(O(1)\) operation. Since there are \(O(n^2)\) pairs, the total time for checking the map is also \(O(n^2)\).

• Overall Time Complexity:

  The total time complexity is \(O(n^2)\) because the nested loop dominates the time complexity.

Space Complexity

• Space for Frequency Map:

  The unordered map elementFrequency stores up to \(n\) elements, so its space complexity is \(O(n)\).

• Overall Space Complexity:

  Since no additional space is used besides the frequency map and a few variables, the total space complexity is \(O(n)\).