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:
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 codeprint(longest_dominoes_chain([(3, 4), (5, 6), (1, 4), (1, 6)])) |
[(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!
