The game of dominoes is played with small black tiles, each having 2 numbers of dots from 0-6. Players line up tiles to match dots. Each domino can be flipped. From a given set of dominoes, you need to find the longest chain of dominoes.
Examples:
Input: dominoes = [(3, 4), (5, 6), (1, 4), (1, 6)]
Output: [(3,4), (4,1), (1,6)]
Explanation: (3->4->4->1->1->6) Each domino in the chain connects to the next one by matching numbers, and this chain is the longest possible chain that can be formed from the given dominoes.Input: dominoes = [(0,3), (3,1), (2,1), (4,0)]
Output: [(0,3), (3,1), (1,2)]]
Explanation: (0->3->3->1->1->2) Each domino in the chain connects to the next one by matching numbers, and this chain is the longest possible chain that can be formed from the given dominoes.
Approach: To solve the problem follow the below idea:
The approach to find the longest chain of dominoes by using dynamic programming to store and update chain lengths, and then backtracking to reconstruct the chain.
Follow the steps to implement the approach:
- Initializing a dictionary to keep track of the longest chain that ends with a particular number. It also initializes a prev list to keep track of the previous domino in the longest chain.
- Then iterates through the dominoes list, starting from the second domino (index 1) to the end.
- For each domino (x, y), it checks if x or y is already present in the left_count dictionary. If it is, it updates the chain length (normal) for the current domino by adding 1 to the length of the chain that ends with x or y, depending on which one is present.
- It also updates the prev list to keep track of the previous domino in the longest chain. If y is present in left_count and has a longer chain, the prev list is updated accordingly.
- If x or y is not in left_count or has a shorter chain, it updates the left_count dictionary with the new chain length (normal).
- After processing all the dominoes, the code performs backtracking to find the longest chain. It starts with the domino that has the longest chain length in left_count and follows the prev list to reconstruct the longest chain.
Below is the implementation of the above approach:
C++
#include <algorithm> #include <iostream> #include <unordered_map> #include <vector> using namespace std; // Function to find the longest domino chain vector<pair< int , int > > findLongestDominoChain( const unordered_map< int , pair< int , int > >& leftCount, const vector<pair< int , int > >& dominoes, const vector< int >& prev); // Function to backtrack and find the longest domino chain vector<pair< int , int > > findLongestDominoChain( const vector<pair< int , int > >& dominoes) { if (dominoes.empty()) { return vector<pair< int , int > >(); } unordered_map< int , pair< int , int > > leftCount; leftCount[dominoes[0].first] = make_pair(1, 0); leftCount[dominoes[0].second] = make_pair(1, 0); vector< int > prev(dominoes.size(), -1); for ( int i = 1; i < dominoes.size(); ++i) { int x = dominoes[i].first; int y = dominoes[i].second; pair< int , int > normal = make_pair(1, i); pair< int , int > reverse = make_pair(1, i); if (leftCount.find(x) != leftCount.end()) { normal = make_pair(leftCount[x].first + 1, i); prev[i] = leftCount[x].second; } if (leftCount.find(y) != leftCount.end()) { reverse = make_pair(leftCount[y].first + 1, i); if (reverse.first > normal.first) { prev[i] = leftCount[y].second; } } if (leftCount.find(y) == leftCount.end() || leftCount[y].first < normal.first) { leftCount[y] = normal; } if (leftCount.find(x) == leftCount.end() || leftCount[x].first < reverse.first) { leftCount[x] = reverse; } } return findLongestDominoChain(leftCount, dominoes, prev); } // Function to backtrack and find the longest domino chain vector<pair< int , int > > findLongestDominoChain( const unordered_map< int , pair< int , int > >& leftCount, const vector<pair< int , int > >& dominoes, const vector< int >& prev) { vector<pair< int , int > > output; // Find the right number with the longest chain int rightNum = max_element( leftCount.begin(), leftCount.end(), []( const auto & left, const auto & right) { return left.second.first < right.second.first; }) ->first; int index = leftCount.at(rightNum).second; // Backtrack from the longest chain to construct the // chain while (index != -1) { int leftNum = (dominoes[index].second == rightNum) ? dominoes[index].first : dominoes[index].second; output.emplace_back(leftNum, rightNum); index = prev[index]; rightNum = leftNum; } // Reverse the list to get the correct order reverse(output.begin(), output.end()); return output; } int main() { // Sample input vector<pair< int , int > > dominoes = { { 3, 4 }, { 5, 6 }, { 1, 4 }, { 1, 6 } }; vector<pair< int , int > > longestChain = findLongestDominoChain(dominoes); // Output the longest domino chain for ( const auto & domino : longestChain) { cout << "(" << domino.first << ", " << domino.second << ") " ; } return 0; } |
Java
// Java Implementation: import java.util.*; public class Main { public static void main(String[] args) { // Sample input List<Pair<Integer, Integer>> dominoes = new ArrayList<>(); dominoes.add( new Pair<>( 3 , 4 )); dominoes.add( new Pair<>( 5 , 6 )); dominoes.add( new Pair<>( 1 , 4 )); dominoes.add( new Pair<>( 1 , 6 )); List<Pair<Integer, Integer>> longestChain = findLongestDominoChain(dominoes); // Output the longest domino chain for (Pair<Integer, Integer> domino : longestChain) { System.out.println( "(" + domino.getFirst() + ", " + domino.getSecond() + ")" ); } } // Function to find the longest domino chain public static List<Pair<Integer, Integer>> findLongestDominoChain(List<Pair<Integer, Integer>> dominoes) { if (dominoes.isEmpty()) { return new ArrayList<>(); } Map<Integer, Pair<Integer, Integer>> leftCount = new HashMap<>(); leftCount.put(dominoes.get( 0 ).getFirst(), new Pair<>( 1 , 0 )); leftCount.put(dominoes.get( 0 ).getSecond(), new Pair<>( 1 , 0 )); List<Integer> prev = new ArrayList<>(Collections.nCopies(dominoes.size(), - 1 )); for ( int i = 1 ; i < dominoes.size(); i++) { int x = dominoes.get(i).getFirst(); int y = dominoes.get(i).getSecond(); Pair<Integer, Integer> normal = new Pair<>( 1 , i); Pair<Integer, Integer> reverse = new Pair<>( 1 , i); if (leftCount.containsKey(x)) { normal = new Pair<>(leftCount.get(x).getFirst() + 1 , i); prev.set(i, leftCount.get(x).getSecond()); } if (leftCount.containsKey(y)) { reverse = new Pair<>(leftCount.get(y).getFirst() + 1 , i); if (reverse.getFirst() > normal.getFirst()) { prev.set(i, leftCount.get(y).getSecond()); } } if (!leftCount.containsKey(y) || leftCount.get(y).getFirst() < normal.getFirst()) { leftCount.put(y, normal); } if (!leftCount.containsKey(x) || leftCount.get(x).getFirst() < reverse.getFirst()) { leftCount.put(x, reverse); } } return findLongestDominoChain(leftCount, dominoes, prev); } // Function to backtrack and find the longest domino chain public static List<Pair<Integer, Integer>> findLongestDominoChain(Map<Integer, Pair<Integer, Integer>> leftCount, List<Pair<Integer, Integer>> dominoes, List<Integer> prev) { List<Pair<Integer, Integer>> output = new ArrayList<>(); // Find the right number with the longest chain int rightNum = Collections.max(leftCount.entrySet(), Comparator.comparingInt(entry -> entry.getValue().getFirst())).getKey(); int index = leftCount.get(rightNum).getSecond(); // Backtrack from the longest chain to construct the chain while (index != - 1 ) { int leftNum = (dominoes.get(index).getSecond() == rightNum) ? dominoes.get(index).getFirst() : dominoes.get(index).getSecond(); output.add( new Pair<>(leftNum, rightNum)); index = prev.get(index); rightNum = leftNum; } // Reverse the list to get the correct order Collections.reverse(output); return output; } } class Pair<T, U> { private T first; private U second; public Pair(T first, U second) { this .first = first; this .second = second; } public T getFirst() { return first; } public U getSecond() { return second; } } // This code is contributed by Tapesh(tapeshdua420) |
Python
def longest_dominoes_chain(dominoes): if not dominoes: return [] # Dictionary to keep track of the count # of left numbers and their indices left_count = { dominoes[ 0 ][ 0 ]: ( 1 , 0 ), dominoes[ 0 ][ 1 ]: ( 1 , 0 ) } # Initialize a list to store the previous # indices for backtracking prev = [ - 1 for _ in dominoes] # Loop through the dominoes to # find the longest chain for i in range ( 1 , len (dominoes)): x, y = dominoes[i] normal = ( 1 , i) reverse = ( 1 , i) # Check if the left number 'x' # is already in left_count if x in left_count: normal = (left_count[x][ 0 ] + 1 , i) prev[i] = left_count[x][ 1 ] # Check if the left number 'y' # is already in left_count if y in left_count: reverse = (left_count[y][ 0 ] + 1 , i) # If the reverse chain is longer, # update the previous index if reverse[ 0 ] > normal[ 0 ]: prev[i] = left_count[y][ 1 ] # Update left_count with the longer chain if y not in left_count or left_count[y][ 0 ] < normal[ 0 ]: left_count[y] = normal if x not in left_count or left_count[x][ 0 ] < reverse[ 0 ]: left_count[x] = reverse # Call the helper function to backtrack # and find the longest domino chain return find_longest_domino_chain(left_count, dominoes, prev) def find_longest_domino_chain(left_count, dominoes, prev): output = [] # Find the right number with # the longest chain right_num = max (left_count, key = lambda x: left_count[x][ 0 ]) _, index = left_count[right_num] # Backtrack from the longest chain # to construct the chain while index ! = - 1 : left_num = dominoes[index][ 0 ] if dominoes[index][ 1 ] = = right_num else dominoes[index][ 1 ] output.append((left_num, right_num)) index = prev[index] right_num = left_num # Reverse the list to get the correct order return output[:: - 1 ] # Driver code print (longest_dominoes_chain([( 3 , 4 ), ( 5 , 6 ), ( 1 , 4 ), ( 1 , 6 )])) |
C#
//C# Implementation using System; using System.Collections.Generic; using System.Linq; class GFG { static void Main( string [] args) { // Sample input List<Tuple< int , int >> dominoes = new List<Tuple< int , int >> { Tuple.Create(3, 4), Tuple.Create(5, 6), Tuple.Create(1, 4), Tuple.Create(1, 6) }; List<Tuple< int , int >> longestChain = FindLongestDominoChain(dominoes); // Output the longest domino chain foreach ( var domino in longestChain) { Console.WriteLine( "(" + domino.Item1 + ", " + domino.Item2 + ")" ); } } // Function to find the longest domino chain static List<Tuple< int , int >> FindLongestDominoChain(List<Tuple< int , int >> dominoes) { if (dominoes.Count == 0) { return new List<Tuple< int , int >>(); } Dictionary< int , Tuple< int , int >> leftCount = new Dictionary< int , Tuple< int , int >>(); leftCount[dominoes[0].Item1] = Tuple.Create(1, 0); leftCount[dominoes[0].Item2] = Tuple.Create(1, 0); List< int > prev = Enumerable.Repeat(-1, dominoes.Count).ToList(); for ( int i = 1; i < dominoes.Count; i++) { int x = dominoes[i].Item1; int y = dominoes[i].Item2; Tuple< int , int > normal = Tuple.Create(1, i); Tuple< int , int > reverse = Tuple.Create(1, i); if (leftCount.ContainsKey(x)) { normal = Tuple.Create(leftCount[x].Item1 + 1, i); prev[i] = leftCount[x].Item2; } if (leftCount.ContainsKey(y)) { reverse = Tuple.Create(leftCount[y].Item1 + 1, i); if (reverse.Item1 > normal.Item1) { prev[i] = leftCount[y].Item2; } } if (!leftCount.ContainsKey(y) || leftCount[y].Item1 < normal.Item1) { leftCount[y] = normal; } if (!leftCount.ContainsKey(x) || leftCount[x].Item1 < reverse.Item1) { leftCount[x] = reverse; } } return FindLongestDominoChain(leftCount, dominoes, prev); } // Function to backtrack and find the longest domino chain static List<Tuple< int , int >> FindLongestDominoChain(Dictionary< int , Tuple< int , int >> leftCount, List<Tuple< int , int >> dominoes, List< int > prev) { List<Tuple< int , int >> output = new List<Tuple< int , int >>(); // Find the right number with the longest chain int rightNum = leftCount.Aggregate((x, y) => x.Value.Item1 > y.Value.Item1 ? x : y).Key; int index = leftCount[rightNum].Item2; // Backtrack from the longest chain to construct the chain while (index != -1) { int leftNum = (dominoes[index].Item2 == rightNum) ? dominoes[index].Item1 : dominoes[index].Item2; output.Add(Tuple.Create(leftNum, rightNum)); index = prev[index]; rightNum = leftNum; } // Reverse the list to get the correct order output.Reverse(); return output; } } |
Javascript
function findLongestDominoChain(dominoes) { // If the input array is empty, return an empty array (no dominoes) if (dominoes.length === 0) { return []; } // Store the count of left occurrences of each number and their positions const leftCount = new Map(); leftCount.set(dominoes[0][0], [1, 0]); // Initialize the count for the first domino's left number leftCount.set(dominoes[0][1], [1, 0]); // Initialize the count for the first domino's right number // Keep track of previous dominoes in the longest chain const prev = Array(dominoes.length).fill(-1); // Iterate over the dominoes starting from the second one for (let i = 1; i < dominoes.length; ++i) { const x = dominoes[i][0]; const y = dominoes[i][1]; let normal = [1, i]; // Track the normal chain count for current domino let reverse = [1, i]; // Track the reverse chain count for current domino // If the left number of the domino exists in the leftCount map if (leftCount.has(x)) { normal = [leftCount.get(x)[0] + 1, i]; // Increment the normal count and update the position prev[i] = leftCount.get(x)[1]; // Store the index of the previous domino in the chain } // If the right number of the domino exists in the leftCount map if (leftCount.has(y)) { reverse = [leftCount.get(y)[0] + 1, i]; // Increment the reverse count and update the position if (reverse[0] > normal[0]) { prev[i] = leftCount.get(y)[1]; // Update the previous index if the reverse count is greater } } // Update leftCount map with the max chain count for each number if (!leftCount.has(y) || leftCount.get(y)[0] < normal[0]) { leftCount.set(y, normal); } if (!leftCount.has(x) || leftCount.get(x)[0] < reverse[0]) { leftCount.set(x, reverse); } } // Find and return the longest chain of dominoes return findLongestChain(leftCount, dominoes, prev); } function findLongestChain(leftCount, dominoes, prev) { const output = []; // Store the longest chain of dominoes let rightNum = -1; let maxChain = -1; // Find the right number with the longest chain count for (const [num, [count]] of leftCount) { if (count > maxChain) { maxChain = count; rightNum = num; } } let index = leftCount.get(rightNum)[1]; // Get the index of the longest chain // Backtrack from the longest chain to reconstruct the chain while (index !== -1) { const leftNum = dominoes[index][1] === rightNum ? dominoes[index][0] : dominoes[index][1]; output.push([leftNum, rightNum]); // Add the domino to the output chain index = prev[index]; // Move to the previous domino in the chain rightNum = leftNum; // Update the right number for the next domino } // Reverse the list to get the correct order of the longest chain return output.reverse(); } // Sample input const dominoes = [ [3, 4], [5, 6], [1, 4], [1, 6] ]; const longestChain = findLongestDominoChain(dominoes); // Output the longest domino chain console.log( "Longest Domino Chain:" ); console.log(longestChain.map(domino => `(${domino[0]}, ${domino[1]})`).join( " " )); |
[(3, 4), (4, 1), (1, 6)]
Time complexity: O(N), where N is the number of dominoes.
Auxiliary Space: O(N), where N is the number of dominoes.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!