Skip to content

011 — Most Stones Removed with Same Row or Column

Source

  • Original source: Classic creative-grouping exercise
  • Platform: LeetCode — https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
  • Topic: disjoint set union
  • Difficulty: Medium
  • Pattern: creative union keys (rows/cols as nodes)
  • Basic idea inherited from: 10-এর grouping pattern; এখানে row আর column নিজেরাই DSU node — DSU-র আসল interview-শক্তি

1. Problem in simple words

2D সমতলে কতগুলো stone, প্রতিটার [row, col] দেওয়া। একটা stone সরানো যায় যদি ওই same row বা same column-এ আরও একটা stone থাকে। তুমি যতবার খুশি সরাতে পারো; বলো সর্বোচ্চ কতগুলো stone সরানো সম্ভব।

stones = (0,0)(0,1)(1,0)(1,2)(2,1)(2,2)
        সব stone row/column শৃঙ্খলে একে অপরের সাথে যুক্ত -> এক group
        n - (group-সংখ্যা) = 6 - 1 = 5  ->  উত্তর: 5

2. Which basic idea does this inherit from?

মূল ভিত হলো এই tracker-এর grouping pattern (Pattern D), তবে একটা সৃজনশীল মোচড়সহ। সরাসরি stone-কে stone-এর সাথে জোড়ার বদলে, row আর column-কেই DSU node বানাও। যেসব stone একই row বা column শেয়ার করে — সরাসরি বা ঘুরিয়ে — তারা এক group। এই "row/col-কে node" দৃষ্টিভঙ্গিই DSU-র আসল interview-শক্তি।

3. What is the hidden math or logic?

লুকানো logic দুই অংশে:

  • কত সরানো যায়: একটা connected group-এ k stone থাকলে, তুমি k − 1 টা সরাতে পারো — শেষ একটা রেখে দিতে হয় (সরানোর নিয়মে অন্তত একটা সঙ্গী লাগে)। তাই মোট সরানো = n − (group-সংখ্যা)।
  • কীভাবে group বানাবে: দুটো stone যুক্ত যদি তারা row বা column শেয়ার করে। একই row-এর সব stone এক group, একই column-এরও — তাই প্রতিটা row আর প্রতিটা column-কে node ধরে ওই stone-এর row-node ও col-node union করলে শৃঙ্খলটা আপনাআপনি গড়ে।

4. Which data structure is needed?

একটা DSU যেখানে node দুই ধরনের: row-গুলো আর column-গুলো (collision এড়াতে column-কে আলাদা namespace, যেমন col + 10001 বা একটা dictionary দিয়ে id)। প্রতিটা stone তার row-node আর col-node union করে। শেষে আলাদা root-সংখ্যা গুনি।

5. Why this data structure fits

প্রশ্নটা "কয়টা আলাদা যুক্ত দল?" — grouping, path নয়। কিন্তু সরাসরি stone-জোড়া union করলে O(n²) তুলনা লাগত। row/column-কে node বানানোর creative চাল-এ প্রতিটা stone মাত্র একটা union করে (তার row ও col), আর shared row/col আপনাআপনি stone-দের জুড়ে দেয় — DSU তখন সবচেয়ে elegant fit।

6. Real-life analogy

ভাবো প্রতিটা row একটা করিডোর, প্রতিটা column একটা করিডোর। একটা stone হলো এক row-করিডোর আর এক col-করিডোর-এর সংযোগস্থলে রাখা একটা দরজা — সে ওই দুই করিডোরকে যুক্ত করে দেয়। দুটো করিডোর যদি কোথাও একটা stone-দরজা দিয়ে জোড়া থাকে, তারা একই "ভবন"-এর অংশ। এক ভবনের যত stone, একটা বাদে সব সরানো যায়।

7. Visual explanation

প্রতিটা stone-এ তার row-node আর col-node union করো; group-সংখ্যা বের করে n − group ফেরাও।

stones: (0,0) (0,1) (1,0)        row-node: r0,r1 ;  col-node: c0,c1

(0,0): union(r0, c0)        r0—c0 যুক্ত
(0,1): union(r0, c1)        r0 আগেই group-এ -> c1-ও টেনে আনে: {r0,c0,c1}
(1,0): union(r1, c0)        c0 আগের group-এ -> r1-ও যোগ: {r0,r1,c0,c1}

forest (এক group):
        r0
      / | \
    c0 c1 r1        সব 3 stone এক group

group-সংখ্যা = 1  ->  সরানো যায় = n - group = 3 - 1 = 2

------ দুই আলাদা group: (0,0)(0,1)(2,2) ------
(0,0),(0,1): {r0,c0,c1}      (2,2): {r2,c2}  (আলাদা!)
group-সংখ্যা = 2  ->  সরানো = 3 - 2 = 1

8. Example input and output

Input : [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5      (সব এক group; 6 - 1)

Input : [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3      (দুই group; 5 - 2)

Edge case (একটা stone): [[0,0]]                  ->  0   (সঙ্গী নেই)
Edge case (দুই বিচ্ছিন্ন): [[0,0],[1,1]]          ->  0   (দুই group, কেউ সরে না)

9. Brute force thinking

সরল চিন্তা: stone-গুলোকে node ভাবো; প্রতি জোড়া stone তুলনা করো — row বা column মিললে edge। তারপর DFS/BFS দিয়ে connected component গোনো; উত্তর = n − component।

1) প্রতি জোড়া (i, j): row সমান বা col সমান হলে -> edge
2) DFS দিয়ে component গোনো
3) উত্তর = n - component-সংখ্যা

10. Why brute force is slow

প্রতি জোড়া stone তুলনা করা O(n²), তারপর DFS — বড় n-এ ধীর। row/col-কে node বানানোর চালে প্রতিটা stone মাত্র দুটো union করে (row+col), মোট O(n·α) ≈ O(n)। জোড়া-তুলনা সম্পূর্ণ বাদ — shared row/col নিজেই stone-দের জুড়ে দেয়। এটাই creative-key-র মূল লাভ।

11. Key observation

মূল observation: row আর column-কে DSU node বানাও — stone নিজে edge। একটা stone (r, c) তার row-node আর col-node-কে union করে; একই row বা col-এর stone-গুলো তখন এক group-এ এসে পড়ে আপনাআপনি, কোনো জোড়া-তুলনা ছাড়াই। উত্তর = n − (group-সংখ্যা)।

12. Optimized intuition

DSU নাও যেখানে row-id আর col-id আলাদা থাকে (col-কে col + offset বা dict-id দিয়ে আলাদা করো, যাতে row 0 আর col 0 না মেশে)। প্রতিটা stone-এ union(row_id, col_id)। শেষে stone-গুলোর representative-set-এর আকার = group-সংখ্যা; উত্তর n − group-সংখ্যা। মোট O(n·α)।

13. Thinking tweak

মোচড়: "কোন কোন stone একই row/col-এ, জোড়ায় জোড়ায় মিলাই" — এই জোড়া-তুলনার চিন্তা ছাড়ো। বদলে ভাবো "প্রতিটা row আর column একটা করিডোর (node); stone ওই দুই করিডোর জোড়ার আঠা।" Element (stone) নয়, তার coordinate-গুলোকে node বানানোই এই problem-এর আসল চাবি — DSU-র সবচেয়ে সৃজনশীল রূপ।

14. Step-by-step dry run

Input [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]], n=6 (row-id = r, col-id = c আলাদা namespace):

  1. (0,0) → union(r0, c0) → {r0,c0}
  2. (0,1) → union(r0, c1) → r0 group-এ, c1 যোগ → {r0,c0,c1}
  3. (1,0) → union(r1, c0) → c0 group-এ, r1 যোগ → {r0,r1,c0,c1}
  4. (1,2) → union(r1, c2) → r1 group-এ, c2 যোগ → {r0,r1,c0,c1,c2}
  5. (2,1) → union(r2, c1) → c1 group-এ, r2 যোগ → সব এক group
  6. (2,2) → union(r2, c2) → দুটোই আগেই এক group → False, কিছু বদলায় না
  7. stone-গুলোর distinct root = 1 → উত্তর = 6 − 1 = 5

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 remove_stones(stones):
    n = len(stones)
    dsu = DSU(n)                         # node হবে stone-index, key দিয়ে জোড়া
    row_first = {}                       # প্রতিটা row প্রথম যে stone-এ দেখা
    col_first = {}                       # প্রতিটা col প্রথম যে stone-এ দেখা
    for i, (r, c) in enumerate(stones):
        if r in row_first:
            dsu.union(i, row_first[r])   # একই row -> আগের stone-এর সাথে merge
        else:
            row_first[r] = i
        if c in col_first:
            dsu.union(i, col_first[c])   # একই col -> আগের stone-এর সাথে merge
        else:
            col_first[c] = i
    roots = {dsu.find(i) for i in range(n)}   # distinct group-সংখ্যা
    return n - len(roots)                # প্রতি group থেকে একটা বাদে সব সরে


# ---- tests ----
assert remove_stones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]) == 5
assert remove_stones([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) == 3
assert remove_stones([[0, 0]]) == 0                 # সঙ্গী নেই
assert remove_stones([[0, 0], [1, 1]]) == 0         # দুই আলাদা group
print("সব test pass!")

16. Line-by-line code explanation

  • dsu = DSU(n) — এই বাস্তবায়নে node হলো stone-index, আর row/col-কে dictionary-key বানিয়ে stone-দের জোড়া হয় (row/col-id সরাসরি node বানানোর সমতুল্য, কিন্তু index-collision-মুক্ত)।
  • row_first / col_first — প্রতিটা row বা column প্রথম যে stone-এ দেখা গেছে, সেটা মনে রাখে — যাতে একই row/col-এর পরের stone আগের stone-এর সাথে merge করতে পারে।
  • if r in row_first: dsu.union(i, row_first[r]) — এই stone-এর row আগে দেখা গেলে, এখনকার stone-কে সেই আগের stone-এর সাথে এক group-এ আনো।
  • col-এর জন্য একই — একই column-এর stone-দের জোড়ে।
  • roots = {dsu.find(i) for i in range(n)} — সব stone-এর representative জড়ো করে distinct group-সংখ্যা বের করা।
  • return n - len(roots) — প্রতি group থেকে একটা stone রেখে বাকি সব সরানো যায়, তাই n − group।

17. Output walkthrough

প্রথম test-এ সব stone row/col শৃঙ্খলে এক group → distinct root 1 → 6−1 = 5। দ্বিতীয়টায় দুটো আলাদা group তৈরি হয় (একটা corner-জোড়া, একটা মাঝের একা সারি/স্তম্ভ) → 5−2 = 3। একক-stone case-এ 1 group, কোনো সঙ্গী নেই → 1−1 = 0। দুই-বিচ্ছিন্ন case-এ 2 group → 2−2 = 0। শেষে print: সব test pass!।

18. Time complexity

O(n · α(n)) ≈ O(n) — প্রতিটা stone বড়জোর দুটো union (row + col), প্রতিটা amortized near-constant; শেষে n বার find। জোড়া-তুলনার O(n²) সম্পূর্ণ এড়ানো।

19. Space complexity

O(n) — parent + size array, আর row_first / col_first map — সবই stone-সংখ্যার সমানুপাতিক।

20. Common mistakes

  • row-id আর col-id একই namespace-এ রাখা (যেমন raw row আর raw col) — তখন row 0 আর col 0 ভুল করে মিশে যায়; offset (col + 10001) বা আলাদা dict-id লাগে। (এখানে stone-index-কে node করে সেই ফাঁদ এড়ানো হয়েছে।)
  • n − group-এর বদলে group বা n ফেরানো — উত্তর হলো সরানো-সংখ্যা = মোট − টিকে-থাকা।
  • জোড়ায় জোড়ায় stone union করার চেষ্টা (O(n²)) — creative-key পুরো এই খরচ মুছে দেয়।
  • distinct root গুনতে find না করে parent ব্যবহার করা — classic DSU bug।

21. Which basic problem this inherits from

ভিত্তি: এই tracker-এর grouping pattern (Pattern D) — shared key দিয়ে union। এখানে নতুনত্ব হলো key নিজেই node (row/column), element নয়। DFS দিয়েও stone-জোড়ার graph-এ component গোনা যায়, কিন্তু সেজন্য O(n²) edge গড়তে হয়; row/col-কে node বানানো DSU সেই খরচ এড়ায়। এই "coordinate-কে node" চোখটাই grid/geometry problem-এ DSU-র শক্তি।

22. Similar harder problems

23. Pattern learned

Creative union keys (rows/cols as nodes): element-কে সরাসরি না জুড়ে, তার shared attribute (row, column)-কেই DSU node বানাও; element হয়ে যায় তার attribute-গুলো জোড়ার আঠা। এতে জোড়া-তুলনা (O(n²)) মুছে যায়, আর group-সংখ্যা থেকে উত্তর বেরোয়। "same row/column/property" দেখলে এই চাল ভাবো।

24. Final summary

ভবিষ্যতের আমাকে: "একই row/column হলে যুক্ত" দেখলে stone-জোড়া মেলানো ছাড়ো — row আর column-কেই node বানাও, প্রতিটা stone তার row+col union করুক, group-সংখ্যা থেকে n − group ফেরাও। Element নয়, তার coordinate-কে node ভাবা — এটাই DSU-র সবচেয়ে সৃজনশীল ও interview-গুরুত্বপূর্ণ চাল।

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