Number of Equivalent Domino Pairs

🏠 ⬅️ ➡️

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a == c and b == d), or (a == d and b == c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]] Output: 1

Example 2:

Input: dominoes = [[1,2],[1,2],[1,1],[1,2],[2,2]] Output: 3

Constraints:

  • 1 <= dominoes.length <= 4 * 104
  • dominoes[i].length == 2
  • 1 <= dominoes[i][j] <= 9
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: dominoes
    integer :: i, j, k, l, m, n_pairs

    ! Example 1
    dominoes = reshape([1, 2, 2, 1, 3, 4, 5, 6], shape=[n])
    write(*,*) 'Example 1'
    write(*,*) 'Input:'
    do i = 1, size(dominoes)
        write(*,'(A,I0,A,I0)') '[', dominoes(i,1), ',', dominoes(i,2), ']'
    end do
    call solve(dominoes)
    write(*,*) 'Output:'
    write(*,*) n_pairs

    ! Example 2
    dominoes = reshape([1, 2, 1, 2, 1, 2, 1, 2], shape=[n])
    write(*,*) 'Example 2'
    write(*,*) 'Input:'
    do i = 1, size(dominoes)
        write(*,'(A,I0,A,I0)') '[', dominoes(i,1), ',', dominoes(i,2), ']'
    end do
    call solve(dominoes)
    write(*,*) 'Output:'
    write(*,*) n_pairs

contains

    subroutine solve(dominoes)
        implicit none
        integer, intent(inout) :: dominoes(:,:)
        integer :: i, j, k, l, m, n_pairs

        n_pairs = 0
        do i = 1, size(dominoes)-1
            do j = i+1, size(dominoes)
                if (dominoes(i,1) == dominoes(j,2)) then
                    if (dominoes(i,2) == dominoes(j,1)) then
                        n_pairs = n_pairs + 1
                    end if
                else if (dominoes(i,2) == dominoes(j,2)) then
                    if (dominoes(i,1) == dominoes(j,1)) then
                        n_pairs = n_pairs + 1
                    end if
                end if
            end do
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module dominoes
  implicit none
contains
  function countEquivalentDominoPairs(dominoes) result(count)
    integer, intent(in) :: dominoes(:, :)
    integer :: count, i, j, k, l
    logical :: equivalent

    count = 0
    do i = 1, size(dominoes, 1) - 1
      do j = i + 1, size(dominoes, 1)
        equivalent = .false.
        do k = 1, 2
          do l = 1, 2
            if (dominoes(i, k) == dominoes(j, l)) then
              equivalent = .true.
              exit
            end if
          end do
          if (equivalent) exit
        end do
        if (equivalent) then
          count = count + 1
        end if
      end do
    end do
  end function countEquivalentDominoPairs
end module dominoes

program main
  use dominoes
  implicit none
  integer, parameter :: N = 5
  integer :: dominoes(N, 2)
  integer :: i, j

  dominoes = reshape([1, 2, 2, 1, 3, 4, 5, 6], shape(dominoes))
  write (*, '(A, I0)') 'Number of equivalent domino pairs: ', &
                       countEquivalentDominoPairs(dominoes)

  dominoes = reshape([1, 2, 1, 2, 1, 2, 1, 2], shape(dominoes))
  write (*, '(A, I0)') 'Number of equivalent domino pairs: ', &
                       countEquivalentDominoPairs(dominoes)
end program main
🌐 Data from online sources 
def remove_duplicates(s: str) -> str:
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

The algorithm uses a stack data structure to process the input string 's'. Iterate through the string from left to right, if the current character 'c' is equal to the character at the top of the stack, pop the character from the top of the stack, otherwise, push the current character onto the stack.

After processing the entire string 's', the stack will contain the characters left after all the duplicate removals. Then, convert the stack to the resulting string in the respective language (in C++, Java, and JavaScript, we convert the stack to a string by iterating through it, and in Python, we use the built-in join function).

The time complexity of the algorithm is O(n), where n is the length of the input string 's', and the space complexity is O(n) considering the stack that can be as big as the input string.

🌐 Data from online sources 
#include <string>
#include <stack>

std::string removeDuplicates(std::string s) {
    std::stack<char> st;
    for (char c : s) {
        if (!st.empty() && st.top() == c) {
            st.pop();
        } else {
            st.push(c);
        }
    }

    std::string result;
    while (!st.empty()) {
        result = st.top() + result;
        st.pop();
    }

    return result;
}

The algorithm uses a stack data structure to process the input string 's'. Iterate through the string from left to right, if the current character 'c' is equal to the character at the top of the stack, pop the character from the top of the stack, otherwise, push the current character onto the stack.

After processing the entire string 's', the stack will contain the characters left after all the duplicate removals. Then, convert the stack to the resulting string in the respective language (in C++, Java, and JavaScript, we convert the stack to a string by iterating through it, and in Python, we use the built-in join function).

The time complexity of the algorithm is O(n), where n is the length of the input string 's', and the space complexity is O(n) considering the stack that can be as big as the input string.