Blogs Hub

Number of Equivalent Domino Pairs - Array - Easy - LeetCode - MiniTV

Number of Equivalent Domino Pairs - Array - Easy - LeetCode - मिनी टीवी

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

 

Constraints:

1 <= dominoes.length <= 40000

1 <= dominoes[i][j] <= 9

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class NumEquivDominoPairsSoln
    {
        public int NumEquivDominoPairs(int[][] dominoes)
        {
            var map = new Dictionary<string, int>();
            int count = 0;
            string key = string.Empty;
            for (int i = 0; i < dominoes.Length; i++)
            {
                key = Math.Min(dominoes[i][0], dominoes[i][1]).ToString() +
                    "-" +Math.Max(dominoes[i][0], dominoes[i][1]).ToString();

                if (map.ContainsKey(key))
                {
                    count += map[key];
                    map[key]++;
                }
                else
                {
                    map.Add(key, 1);
                }                
            }

            return count;
        }        
    }
}

 

Time Complexity: O(n)

Space Complexity: O(n)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class NumEquivDominoPairsSolnTests
    {
        [TestMethod]
        public void NumEquivDominoPairsSoln_First()
        {
            var dominoes = new int[,]{
                    { 1, 2 },
                    { 2, 1 },
                    { 3, 4 },
                    { 5, 6 }
                };      
            var expected = 1;

            var res = new NumEquivDominoPairsSoln().NumEquivDominoPairs(ArrayMapper(dominoes));
            Assert.AreEqual(expected, res);
        }

        [TestMethod]
        public void NumEquivDominoPairsSoln_Second()
        {
            var dominoes = new int[,]{
                    { 1, 1 },
                    { 2, 2 },
                    { 1, 1 },
                    { 1, 2 },
                    { 1, 2 },
                    { 1, 1 }
                };
            var expected = 4;

            var res = new NumEquivDominoPairsSoln().NumEquivDominoPairs(ArrayMapper(dominoes));
            Assert.AreEqual(expected, res);
        }

        private int[][] ArrayMapper(int[,] matrix)
        {
            var arr = new int[matrix.GetLength(0)][];
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                arr[i] = new int[matrix.GetLength(1)];
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    arr[i][j] = matrix[i, j];
                }
            }

            return arr;
        }
    }
}