algoadvance

Leetcode 1534. Count Good Triplets

Problem Statement

Given an array of integers arr, and three integers a, b and c. You need to return the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is a good triplet if the following conditions are true:

• 0 <= i < j < k < len(arr)
• |arr[i] - arr[j]| <= a
• |arr[j] - arr[k]| <= b
• |arr[i] - arr[k]| <= c

Clarifying Questions

1. Input Constraints:
   • What is the range of values for the input array and integers a, b, and c?
     • arr will have 3 to 100 elements. Each element in arr will be between 0 and 1000. a, b, and c will be between 0 and 1000.
2. Output:
   • What should be returned?
     • Return a single integer denoting the number of good triplets.
3. Edge Cases:
   • Are there specific edge cases we should be aware of?
     • Handle the smallest array size (3 elements), maximum values for a, b, and c, and varying values within arr.

Strategy

To solve this problem, we need to iterate through all possible triplets (i, j, k) where i < j < k and check if they satisfy the given conditions. Given the constraints (length of array up to 100), a triple nested loop solution will be feasible and simple to implement.

1. Use three nested loops to iterate over the indices i, j, and k.
2. For each triplet (arr[i], arr[j], arr[k]), check the conditions:
   • |arr[i] - arr[j]| <= a
   • |arr[j] - arr[k]| <= b
   • |arr[i] - arr[k]| <= c
3. If all conditions are met, increment the count of good triplets.
4. Return the count of good triplets.

Code

Here’s the C++ implementation of the above strategy:

#include <vector>
#include <cmath> // for abs

class Solution {
public:
    int countGoodTriplets(std::vector<int>& arr, int a, int b, int c) {
        int count = 0;
        int n = arr.size();
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (std::abs(arr[i] - arr[j]) <= a &&
                        std::abs(arr[j] - arr[k]) <= b &&
                        std::abs(arr[i] - arr[k]) <= c) {
                        ++count;
                    }
                }
            }
        }
        return count;
    }
};

Time Complexity

• Time Complexity: The algorithm runs in O(n^3) time, where n is the number of elements in the array. This is because we are using three nested loops to iterate over all possible triplets.
• Space Complexity: The space complexity is O(1) as we are only using a few extra variables (the count and loop indices).

Given the constraints (with n up to 100), this time complexity is acceptable and should run efficiently within those limits.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?