Skip to content

007 — Satisfiability of Equality Equations

Source

  • Original source: Classic equivalence-class exercise
  • Platform: LeetCode — https://leetcode.com/problems/satisfiability-of-equality-equations/
  • Topic: disjoint set union
  • Difficulty: Medium
  • Pattern: equivalence classes
  • Basic idea inherited from: 10-এর grouping pattern; == দিয়ে variable union করো, তারপর != গুলো ভাঙছে কি না দেখো

1. Problem in simple words

কতগুলো equation দেওয়া, প্রতিটা চার অক্ষরের string — হয় "a==b" (সমান) নয় "a!=b" (অসমান), যেখানে দুই পাশে একটা করে lowercase variable। তোমাকে বলতে হবে — সব variable-এ এমন মান বসানো সম্ভব কি না যাতে প্রতিটা equation সত্যি হয়।

equations = ["a==b", "b!=a"]
        a==b বলে a আর b সমান হতেই হবে; কিন্তু b!=a বলে আবার ভিন্ন
        একসাথে অসম্ভব  ->  False

2. Which basic idea does this inherit from?

মূল ভিত হলো এই tracker-এর grouping pattern (Pattern D) — DSU আসলে একটা equivalence-relation engine। == সম্পর্কটা reflexive, symmetric, transitive — তাই এটা variable-গুলোকে কতগুলো equivalence class-এ ভাগ করে। প্রথমে সব == দিয়ে union করে class বানাও; তারপর প্রতিটা != যাচাই করো — দুই পাশ একই class-এ পড়লে contradiction।

3. What is the hidden math or logic?

লুকানো logic একটা equivalence relation: == reflexive (a==a), symmetric (a==b ⇒ b==a), আর transitive (a==b ও b==c ⇒ a==c)। এমন relation variable-দের disjoint class-এ ভাগ করে — প্রতিটা class-এর সবাই একই মান পাবে। != constraint বলছে দুটো variable ভিন্ন class-এ থাকতে হবে। তাই: সব == মিশিয়ে class গড়ো, তারপর কোনো != যেন এক class-কে নিজের সাথে ভিন্ন হতে না বলে।

4. Which data structure is needed?

একটা DSU ঠিক 26 element-এর ('a' থেকে 'z')। variable গুলো এক অক্ষর, তাই ord(ch) - 97 দিয়ে 0–25 index। == গুলো union, != গুলো find-তুলনা।

5. Why this data structure fits

প্রশ্নটা বিশুদ্ধ "কোন variable কোন দলে?" — equivalence class। DSU merge-only দুনিয়ায় ঠিক এই কাজ: == দিয়ে দল মেশাও, != দিয়ে দুই দল আলাদা থাকা যাচাই করো। মাত্র 26 element, কোনো path/distance লাগে না — তাই DSU সবচেয়ে পরিষ্কার fit।

6. Real-life analogy

party-র friend circle, তবে variable-রা মানুষ। == মানে "এই দুজন আসলে একই পরিচয়" — তাদের circle মেশাও। সব মেশানো শেষে কয়েকটা circle টিকে থাকে। এবার != মানে "এই দুজন অবশ্যই ভিন্ন মানুষ" — যদি দেখা যায় তারা একই circle-এ, তাহলে বিরোধ: একই লোককে দুজন ভিন্ন মানুষ বলা যায় না।

7. Visual explanation

আগে সব == union; তারপর প্রতি !=-এ দুই পাশের find মেলাও — সমান হলে False।

equations = ["a==b", "b==c", "a!=c"]      (a=0, b=1, c=2)

Phase 1 — সব == union:
শুরু:   *a  *b  *c ...        parent: [a,b,c,...]

a==b -> union(0,1):  *a   *c
                      |
                      b              {a,b}

b==c -> union(1,2): find(1)=a, find(2)=c -> merge
                     *a
                    /  \
                   b    c            {a,b,c}

Phase 2 — != যাচাই:
a!=c -> find(a)=a, find(c)=a  ->  সমান!  ->  contradiction  ->  False

------ satisfiable case: ["a==b", "b!=c"] ------
Phase 1: union(a,b) -> {a,b};  c একা
Phase 2: b!=c -> find(b)=a, find(c)=c -> আলাদা -> ঠিক আছে -> True

8. Example input and output

Input : ["a==b","b!=a"]
Output: False

Input : ["b==a","a==b"]
Output: True

Input : ["a==b","b==c","a==c"]
Output: True

Input : ["a==b","b!=c","c==a"]
Output: False     (a==b আর c==a -> a,b,c এক class; কিন্তু b!=c চায় ভিন্ন)

9. Brute force thinking

সরল চিন্তা: variable গুলোকে graph-এর node ভাবো, == গুলোকে edge। প্রতিটা variable-এর জন্য DFS/BFS দিয়ে connected component বের করো (কে কার সাথে সমান)। তারপর প্রতিটা != দেখো — দুই পাশ যদি একই component-এ থাকে, contradiction।

1) == edge দিয়ে adjacency list বানাও
2) DFS দিয়ে প্রতিটা variable-এর component-id বের করো
3) প্রতি !=: দুই পাশের component-id সমান হলে -> False
4) সব != টিকলে -> True

10. Why brute force is slow

মাত্র 26 variable বলে DFS-ও কার্যত fast — কিন্তু এতে adjacency গড়া, recursion, আর component-id label করা লাগে। DSU দুই-পাস-এ (== union, তারপর != find) একই কাজ করে কোনো adjacency বা recursion ছাড়াই, আর "same class?" প্রশ্নটা ঠিক DSU-র জন্মগত operation। তাই DSU সরল ও স্বাভাবিক।

11. Key observation

মূল observation: order matters — আগে সব ==, পরে সব !=। তুমি প্রথমে পুরো equality-graph গড়ে নাও (সব class স্থির হয়), তারপরই !=-গুলো যাচাই করো। মিশিয়ে process করলে এমন != পরে আসা == দিয়ে ভেঙে যেতে পারে — তাই দুটো আলাদা phase জরুরি।

12. Optimized intuition

26-element DSU নাও। Phase 1: সব equation-এ যেগুলো ==, দুই পাশ union করো। Phase 2: সব != equation-এ দুই পাশের find মেলাও — সমান হলে সাথে সাথে False। কোনো != না ভাঙলে True। Path compression + union by size থাকায় পুরোটা amortized প্রায় O(E)।

13. Thinking tweak

মোচড়: "equation-গুলো একে একে পড়ে সাথে সাথে যাচাই করি" — এই single-pass চিন্তা ছাড়ো। বদলে ভাবো "আগে সব 'সমান' মিশিয়ে দল পাকা করি, তারপর কোনো 'অসমান' সেই দল ভাঙছে কি না দেখি।" Equality আর inequality-কে দুই আলাদা phase-এ ভাগ করাই চাবি।

14. Step-by-step dry run

Input ["a==b","b!=c","c==a"] (a=0, b=1, c=2):

  1. Phase 1 (==): a==b → union(0,1) → {a,b}; c==a → union(2,0) → find(2)=2, find(0)=0, merge → {a,b,c}
  2. Phase 2 (!=): b!=c → find(1) আর find(2) — দুটোই এখন এক root (0) → সমান!
  3. contradiction → return False

15. Python solution

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n              # প্রতিটা group-এ একজন

    def find(self, x):                   # representative + path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, x, y):               # union by size; merge হলে True
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx              # rx এখন বড় root
        self.parent[ry] = rx            # ছোটটা বড়টার নিচে ঝোলে
        self.size[rx] += self.size[ry]
        return True


def equations_possible(equations):
    dsu = DSU(26)                        # 'a'..'z' -> index 0..25
    for eq in equations:                 # Phase 1: সব == union করো
        if eq[1] == '=':
            dsu.union(ord(eq[0]) - 97, ord(eq[3]) - 97)
    for eq in equations:                 # Phase 2: != গুলো যাচাই করো
        if eq[1] == '!':
            if dsu.find(ord(eq[0]) - 97) == dsu.find(ord(eq[3]) - 97):
                return False             # এক class-কে ভিন্ন বলা -> contradiction
    return True


# ---- tests ----
assert equations_possible(["a==b", "b!=a"]) is False
assert equations_possible(["b==a", "a==b"]) is True
assert equations_possible(["a==b", "b==c", "a==c"]) is True
assert equations_possible(["a==b", "b!=c", "c==a"]) is False
assert equations_possible(["c==c", "b==d", "x!=z"]) is True   # self-eq + আলাদা class
print("সব test pass!")

16. Line-by-line code explanation

  • dsu = DSU(26) — variable গুলো একক lowercase অক্ষর, তাই ঠিক 26 element যথেষ্ট।
  • if eq[1] == '=' — string-এর index 1-এ operator-এর প্রথম অক্ষর; '=' মানে এটা == equation।
  • dsu.union(ord(eq[0]) - 97, ord(eq[3]) - 97) — index 0 আর 3 হলো দুই variable; ord(ch) - 97 দিয়ে 'a'..'z' কে 0..25-এ map।
  • if eq[1] == '!' (দ্বিতীয় loop) — এবার শুধু != equation; Phase 1 শেষ হওয়ায় সব class স্থির।
  • if dsu.find(...) == dsu.find(...): return False — দুই পাশ একই class-এ পড়লে "ভিন্ন হও" শর্ত ভাঙে — অসম্ভব।
  • return True — কোনো != ভাঙেনি, তাই একটা valid assignment আছে।

17. Output walkthrough

প্রথম test-এ a==b দুটো এক class করে; b!=a সেই class-কে ভিন্ন বলে — False। দ্বিতীয়টায় দুটোই ==, কোনো != নেই — True। তৃতীয়টায় a,b,c এক class, সব == সামঞ্জস্যপূর্ণ — True। চতুর্থটায় a,b,c এক class হয়ে যায়, কিন্তু b!=c চায় ভিন্ন — False। পঞ্চমটায় c==c ক্ষতিহীন, b,d এক class, x আর z আলাদা — True। শেষে print: সব test pass!।

18. Time complexity

O(E · α(1)) ≈ O(E) — E হলো equation-সংখ্যা; দুটো pass, প্রতিটায় প্রতি equation একটা union বা দুটো find, প্রতিটা amortized near-constant। মাত্র 26 element বলে α কার্যত ধ্রুবক।

19. Space complexity

O(1) — DSU array সবসময় ঠিক 26 element, input-size-নিরপেক্ষ; তাই constant extra space।

20. Common mistakes

  • দুই phase মিশিয়ে single pass-এ করা — তখন আগে আসা != পরে আসা == দিয়ে ভেঙে যেতে পারে; আগে সব ==, পরে সব != — order জরুরি।
  • string parsing-এ index ভুল — operator index 1–2, variable index 0 আর 3; eq[2] কে variable ভাবা একটা সহজ ভুল।
  • DSU size 26-এর বদলে equation-সংখ্যা দিয়ে নেওয়া।

21. Which basic problem this inherits from

ভিত্তি: এই tracker-এর grouping pattern (Pattern D, concept.md) — "reflexive + symmetric + transitive যা কিছু, তা-ই DSU-আকৃতির"। এখানে == ঠিক সেই equivalence relation। DFS দিয়ে component বের করেও সমাধান হয়; কিন্তু "same class?" প্রশ্নটা DSU-র find-এই সবচেয়ে সরাসরি, আর দুই-phase structure DSU-তে স্বাভাবিক।

22. Similar harder problems

23. Pattern learned

Equivalence classes: equality constraint গুলো আগে union করে class পাকা করো, তারপর inequality constraint গুলো সেই class ভাঙছে কি না দেখো। reflexive+symmetric+transitive যেকোনো "সমান/একই" সম্পর্ক পেলে এই দুই-phase DSU সরাসরি খাটে।

24. Final summary

ভবিষ্যতের আমাকে: "এই constraint-গুলো একসাথে সম্ভব?" — যেখানে কিছু "সমান" আর কিছু "অসমান" — দেখলে DSU ভাবো: আগে সব সমান মিশিয়ে দল গড়ো, পরে কোনো অসমান শর্ত এক দলকে নিজের সাথে ভিন্ন হতে বলছে কি না দেখো। এটাই equivalence-class checking-এর সবচেয়ে পরিষ্কার রূপ।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।