Count Good Triplets

🏠 ⬅️ ➡️

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

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

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3 Output: 4 Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1 Output: 0 Explanation: No triplet satisfies all conditions.

Constraints:

  • 3 <= arr.length <= 100
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 6
    integer, dimension(n) :: arr = (/ 3, 0, 1, 1, 9, 7 /)
    integer, parameter :: a = 7, b = 2, c = 3
    integer :: i, j, k
    integer :: num_good_triplets

    num_good_triplets = count_good_triplets(arr, a, b, c)
    write (*, '(A, I0)') 'Number of good triplets: ', num_good_triplets

contains

    function count_good_triplets(arr, a, b, c) result(num_good_triplets)
        implicit none
        integer, intent(in) :: arr(:)
        integer, intent(in) :: a, b, c
        integer :: i, j, k
        logical :: condition_1, condition_2, condition_3
        num_good_triplets = 0
        do i = 1, size(arr) - 2
            do j = i + 1, size(arr) - 1
                do k = j + 1, size(arr)
                    condition_1 = (0 <= i .and. i < j .and. j < k .and. k < size(arr))
                    condition_2 = abs(arr(i) - arr(j)) <= a
                    condition_3 = abs(arr(j) - arr(k)) <= b
                    condition_4 = abs(arr(i) - arr(k)) <= c
                    if (condition_1 .and. condition_2 .and. condition_3 .and. condition_4) then
                        num_good_triplets = num_good_triplets + 1
                    end if
                end do
            end do
        end do
    end function count_good_triplets
end program main
❌ Compiled
❌ Executed
❌ Correct 
module good_triplets
  implicit none
contains
  integer function count_good_triplets(arr, a, b, c) result(good_triplets)
    integer, intent(in) :: arr(:)
    integer, intent(in) :: a, b, c
    integer :: i, j, k

    good_triplets = 0
    do i = 1, size(arr) - 2
      do j = i + 1, size(arr) - 1
        do k = j + 1, size(arr)
          if (abs(arr(i) - arr(j)) <= a .and. &
              abs(arr(j) - arr(k)) <= b .and. &
              abs(arr(i) - arr(k)) <= c) then
            good_triplets = good_triplets + 1
          end if
        end do
      end do
    end do
  end function count_good_triplets
end module good_triplets

program test_good_triplets
  use good_triplets
  implicit none
  integer, parameter :: arr = [3, 0, 1, 1, 9, 7]
  integer, parameter :: a = 7, b = 2, c = 3
  integer :: good_triplets

  good_triplets = count_good_triplets(arr, a, b, c)
  write (*, '(A, I0)') 'Number of good triplets: ', good_triplets
end program test_good_triplets
🌐 Data from online sources 
def minNumberOfFrogs(croakOfFrogs: str) -> int:
    counts = [0] * 5
    max_frogs = 0

    for c in croakOfFrogs:
        index = "croak".find(c)
        if index == 0:
            counts[0] += 1
            max_frogs = max(max_frogs, counts[0])
        elif counts[index - 1] > 0:
            counts[index - 1] -= 1
            counts[index] += 1
        else:
            return -1

    if counts[0] == counts[4]:
        return max_frogs
    else:
        return -1

The algorithm starts by initializing an array counts with five elements and max_frogs to zero. It iterates through the given string croakOfFrogs. For each character, it finds its index in the string "croak":

  • If the character is a 'c', it increases the first element of counts and updates the max_frogs.
  • If the character is one of 'r', 'o', 'a', or 'k', it checks if the previous letter in "croak" has a non-zero count in the counts array. If it does, it transfers the count of the previous letter to the count of the current character; otherwise, it returns -1, as the string does not represent a valid croak sequence.

After iterating through the entire string, the algorithm checks if the count of 'c's is equal to the count of 'k's, which indicates that all frog croaks are completed. If so, it returns the value of max_frogs; otherwise, it returns -1.

🌐 Data from online sources 
#include <string>

int minNumberOfFrogs(std::string croakOfFrogs) {
    int counts[5] = {0}, max_frogs = 0;

    for (char c : croakOfFrogs) {
        int index = std::string("croak").find(c);
        if (index == 0) {
            counts[0]++;
            max_frogs = std::max(max_frogs, counts[0]);
        } else if (counts[index - 1] > 0) {
            counts[index - 1]--;
            counts[index]++;
        } else {
            return -1;
        }
    }

    if (counts[0] == counts[4]) {
        return max_frogs;
    } else {
        return -1;
    }
}

The algorithm starts by initializing an array counts with five elements and max_frogs to zero. It iterates through the given string croakOfFrogs. For each character, it finds its index in the string "croak":

  • If the character is a 'c', it increases the first element of counts and updates the max_frogs.
  • If the character is one of 'r', 'o', 'a', or 'k', it checks if the previous letter in "croak" has a non-zero count in the counts array. If it does, it transfers the count of the previous letter to the count of the current character; otherwise, it returns -1, as the string does not represent a valid croak sequence.

After iterating through the entire string, the algorithm checks if the count of 'c's is equal to the count of 'k's, which indicates that all frog croaks are completed. If so, it returns the value of max_frogs; otherwise, it returns -1.