SET Card Game - Validate Set And Find Set#

Levels: level-4

Data structures: array, hash-table

Patterns: hashing

Practice Link#

No single canonical LeetCode problem; this is a common interview / game-math problem.

Description#

Each card has k attributes (in the classic game, k = 4), each taking one of 3 values, typically encoded as 0/1/2.
Three cards form a valid set if for every attribute:
- the values are all the same, OR
- the values are all different
Tasks:
1. is_set(cards3) -> bool: given exactly 3 cards, return whether they form a set
2. find_set(cards) -> list[card]: given a list of cards, return any one set (3 cards), else []

Examples#

text

1(1,0,1,2)
2(1,2,0,2)
3(1,1,2,1)
4-> True

text

1(1,0,1,2)
2(1,0,1,2)
3(1,0,1,2)
4-> True  (all attributes all same)

Python Solution#

 1from collections import Counter
 2from typing import List, Sequence, Tuple
 3
 4Card = Tuple[int, ...]  # e.g. (1,0,1,2)
 5
 6def is_set(cards: Sequence[Card]) -> bool:
 7    """
 8    Check whether exactly 3 cards form a valid Set.
 9
10    Condition per attribute i:
11      len({c1[i], c2[i], c3[i]}) in {1, 3}
12
13    Time:  O(k)
14    Space: O(1)
15    """
16    if len(cards) != 3:
17        return False
18    a, b, c = cards
19    if len(a) != len(b) or len(b) != len(c):
20        return False
21
22    k = len(a)
23    for i in range(k):
24        vals = {a[i], b[i], c[i]}
25        if len(vals) not in (1, 3):
26            return False
27    return True
28
29def _third_value_mod3(x: int, y: int) -> int:
30    """
31    Values are in {0,1,2}.
32    If x==y then third must be same.
33    Else third is the remaining value: 0+1+2 - x - y
34    """
35    return x if x == y else (3 - x - y)
36
37def find_any_set(cards: List[Card]) -> List[Card]:
38    """
39    Find any set among the given cards (returns the 3 cards), else [].
40
41    Efficient approach (classic SET trick):
42    For any two cards A and B, the required third card C is uniquely determined
43    attribute-wise (in mod 3 encoding).
44
45    Handles duplicates by using counts.
46
47    Time:  O(n^2 * k)
48    Space: O(n)
49    """
50    n = len(cards)
51    if n < 3:
52        return []
53
54    counts = Counter(cards)
55    unique = list(counts.keys())
56    k = len(unique[0]) if unique else 0
57    unique_set = set(unique)
58
59    # Iterate over pairs of unique cards (still fine; counts handle duplicates)
60    for i in range(len(unique)):
61        for j in range(i, len(unique)):
62            a = unique[i]
63            b = unique[j]
64
65            need = tuple(_third_value_mod3(a[d], b[d]) for d in range(k))
66            if need not in unique_set:
67                continue
68
69            # Verify availability of 3 cards considering duplicates
70            # Build multiset requirement
71            req = Counter([a, b, need])
72            ok = True
73            for card, r in req.items():
74                if counts[card] < r:
75                    ok = False
76                    break
77            if ok and is_set([a, b, need]):
78                return [a, b, need]
79
80    return []