Problem link ও উৎস
- **Original source:** LeetCode — Rectangle Overlap
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Medium
- **Pattern:** interval logic
- **Basic idea inherited from:** — (স্বাধীন শাখা; এটা cross product নয়, per-axis interval-এর গল্প)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো axis-aligned rectangle দেওয়া (মানে বাহুগুলো x আর y অক্ষের সমান্তরাল, কাত করা নয়)। প্রতিটা rectangle বোঝানো হয় চারটা সংখ্যায় — `(x1, y1, x2, y2)`, যেখানে `(x1, y1)` নিচ-বাঁ কোণ আর `(x2, y2)` উপর-ডান কোণ।
বলতে হবে এই দুটো rectangle **overlap** করে কি না — মানে এদের সাধারণ একটা এলাকা (positive area) আছে কি না। (শুধু ধার বা কোণ ছুঁলে সেটা overlap ধরব কি না, সেটা সংজ্ঞার ব্যাপার — আমরা LeetCode-এর মতো "positive area লাগবে" ধরব, তাই শুধু ছোঁয়া overlap নয়।)
### Input ও output {#6-example-input-and-output}
```text
A (x1,y1,x2,y2) B (x1,y1,x2,y2) overlap?
-------------------------------------------------
(0,0,2,2) (1,1,3,3) True (কোণায় কোণায় ঢুকেছে)
(0,0,2,2) (2,2,4,4) False (শুধু কোণ ছোঁয়, positive area নেই)
(0,0,4,4) (1,1,2,2) True (B পুরো A-র ভেতরে)
(0,0,2,2) (3,0,5,2) False (A পুরো B-র বাঁয়ে, x-এ ফাঁক)
(0,0,2,2) (0,3,2,5) False (A পুরো B-র নিচে, y-এ ফাঁক)
(0,0,3,3) (2,2,5,5) True (অংশত মিলেছে)
```
খেয়াল করো দ্বিতীয় case: rectangle দুটো শুধু একটা কোণ (2,2)-তে ছোঁয় — সাধারণ এলাকা শূন্য (একটা বিন্দু), তাই positive-area সংজ্ঞায় overlap নয়। এটাই touching বনাম overlapping-এর সূক্ষ্ম পার্থক্য।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুটো জানালার পর্দা (rectangular) — তুমি জানতে চাও এরা একে অপরকে ঢেকে দেয় (overlap) কি না।
সরাসরি ভাবতে গেলে অনেক অবস্থা। চালাকি: আলাদা করে ভাবো। প্রথমে শুধু **আনুভূমিক** দিকে দেখো — পর্দা দুটোর x-পরিসর কি একে অপরকে ছোঁয়, নাকি একটা পুরো বাঁয়ে আরেকটা পুরো ডানে? তারপর শুধু **উল্লম্ব** দিকে একই প্রশ্ন — y-পরিসর কি ওভারল্যাপ করে? দুই দিকেই "হ্যাঁ ওভারল্যাপ" হলে তবেই পর্দা দুটো সত্যিকারের একটা অংশ একসাথে ঢাকছে। যেকোনো এক দিকে আলাদা থাকলেই — overlap নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা এই level-এর একটা **স্বাধীন শাখা** — cross product/orientation-এর পরিবারে নয় (তাই "inherited from: —")।
এর শিকড় বরং আরও সাধারণ একটা ধারণায়: **interval overlap** — "দুটো range কি ছেদ করে?" এটা sorting/greedy (Level 8) আর পরে interval scheduling-জাতীয় problem-এ বারবার ফিরবে। এখানে আমরা সেই 1D ধারণাটাকে দুটো অক্ষে আলাদা করে প্রয়োগ করছি। তাই এই problem মনে রাখার আসল মূল্য — **"কঠিন 2D-কে স্বাধীন 1D-তে ভাঙো"** এই decomposition-চিন্তাটা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea **per-axis interval overlap**, আর একটা সুন্দর negation trick।
সরাসরি না ভেবে উল্টো জিজ্ঞেস করি — **কখন overlap করে না?** একটা rectangle যদি পুরোপুরি অন্যটার বাঁয়ে, বা ডানে, বা উপরে, বা নিচে থাকে:
```
overlap করে না যদি:
A.x2 <= B.x1 (A পুরো B-র বাঁয়ে) OR
B.x2 <= A.x1 (A পুরো B-র ডানে) OR
A.y2 <= B.y1 (A পুরো B-র নিচে) OR
B.y2 <= A.y1 (A পুরো B-র উপরে)
overlap করে = not (উপরের কোনোটা)
```
গভীর সত্য: এটা আসলে দুটো 1D interval overlap — x-অক্ষে interval দুটো overlap করে **এবং** y-অক্ষে interval দুটো overlap করে, তবেই rectangle overlap। 2D প্রশ্ন দুটো স্বাধীন 1D প্রশ্নে ভেঙে গেল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যা মাথায় আসে — সব "কখন overlap করে" case সরাসরি গোনা, বা আরও স্থূলভাবে: ছোট ছোট ঘরে ভেঙে দেখা কোনো ঘর দুজনের মধ্যেই পড়ে কি না:
```python
def overlap_brute(A, B):
# প্রতিটা integer unit-cell দেখি — কোনোটা কি দুটোতেই আছে?
ax1, ay1, ax2, ay2 = A
bx1, by1, bx2, by2 = B
for x in range(ax1, ax2): # unit cell [x, x+1)
for y in range(ay1, ay2):
in_b = bx1 <= x < bx2 and by1 <= y < by2
if in_b:
return True
return False
```
এটা integer rectangle-এ ঠিক উত্তর দেয় (positive area থাকলে অন্তত একটা unit cell শেয়ার হবে), কিন্তু rectangle বড় হলে ভয়াবহ ধীর, আর float coordinate-এ একদমই চলে না।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
unit-cell scan-এর খরচ rectangle-এর ক্ষেত্রফলের সমান:
```text
A = 1000 x 1000 হলে:
brute force: প্রায় 1,000,000 cell scan (ধীর, O(area))
interval way: 4টা তুলনা (চোখের নিমেষে, O(1))
আর float coordinate (যেমন 1.5, 2.7) হলে unit-cell ধারণাই ভেঙে পড়ে।
```
মূল শিক্ষা: rectangle overlap একটা **নির্ণায়ক (geometric) প্রশ্ন** — সীমানার সংখ্যা কয়টা তুলনা করলেই উত্তর; ভেতরের প্রতিটা ঘর গোনা বিশাল অপচয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **overlap করে না-কে সংজ্ঞায়িত করা সহজ — একটা পুরো বাঁয়ে/ডানে/উপরে/নিচে।** তাই:
```python
def overlap(A, B):
no = (A[2] <= B[0] or B[2] <= A[0] or
A[3] <= B[1] or B[3] <= A[1])
return not no
```
চারটা সরল তুলনা, তারপর `not`। আর এটা ঠিক per-axis interval overlap — x-interval `[A.x1, A.x2]` আর `[B.x1, B.x2]` ছেদ করে, এবং y-interval-ও ছেদ করে। `<=` ব্যবহার করছি মানে শুধু ধার ছোঁয়াকে overlap ধরছি না (positive area লাগবে)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **কঠিন প্রশ্নটা সরাসরি না ভেবে তার negation ভাবো** — "কখন overlap করে?" এর জায়গায় "কখন overlap করে *না*?" — পরেরটার মাত্র চারটা পরিষ্কার case।
আর দ্বিতীয়, সমান গুরুত্বপূর্ণ tweak — **2D-কে দুটো স্বাধীন 1D-তে ভাঙো।** rectangle overlap = (x-interval overlap) AND (y-interval overlap)। এই "axis-এ আলাদা করে ভাবো" চিন্তাটা bounding-box, collision detection, sweep line — সর্বত্র ফিরবে। মনে রাখো: কঠিন আকার প্রায়ই সরল projection-এর যোগফল।
### ছবিতে বোঝা {#5-visual-explanation}
overlap তখনই, যখন x-interval **আর** y-interval দুটোই ছেদ করে:
```text
overlap করে: overlap করে না (A পুরো বাঁয়ে):
y y
4 +-----+ 4 +---+
| A +--+ | A | +---+
3 | +--+B | 3 3 +---+ | B |
+--+--+--+--- x +-------+---+--- x
x: [1,3]∩[2,4]=[2,3] ✓ x: A.x2=2 <= B.x1=3 -> আলাদা ✗
y: [3,4]∩... ✓ মানে এক axis-এই আলাদা -> overlap নেই
interval-এর ছবি (x-অক্ষ):
A: [---------]
B: [---------]
overlap = [এই অংশ] <- positive মাপ -> x-axis overlap ✓
```
লক্ষ করো — দ্বিতীয় ছবিতে A আর B হয়তো y-তে কাছাকাছি, কিন্তু x-অক্ষে A পুরো বাঁয়ে (`A.x2 <= B.x1`)। একটা অক্ষে আলাদা হলেই গোটা rectangle আলাদা।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `A = (0,0,2,2)`, `B = (1,1,3,3)` — overlap করে কি না:
1. শুরু: A নিচ-বাঁ (0,0) উপর-ডান (2,2); B নিচ-বাঁ (1,1) উপর-ডান (3,3)
2. `A[2] <= B[0]`? `2 <= 1`? না (A ডানে যথেষ্ট ছড়িয়ে)
3. `B[2] <= A[0]`? `3 <= 0`? না
4. `A[3] <= B[1]`? `2 <= 1`? না (A উপরে যথেষ্ট ওঠে)
5. `B[3] <= A[1]`? `3 <= 0`? না
6. `no = না OR না OR না OR না = False`
7. `return not False = True` → **overlap করে** ✓ (কোণায় কোণায় ঢুকেছে)
এবার শুধু-কোণ-ছোঁয়া `A=(0,0,2,2)`, `B=(2,2,4,4)`:
```text
A[2] <= B[0]? 2 <= 2? হ্যাঁ! -> no = True -> return False
মানে A ঠিক B-র বাঁয়ে শেষ হয়েছে যেখানে B শুরু; positive overlap নেই।
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def overlap(A, B):
"""দুটো rectangle (x1,y1,x2,y2) overlap করে কি না (positive area লাগবে)।
negation trick: একটা পুরো বাঁয়ে/ডানে/উপরে/নিচে থাকলে overlap নেই।"""
no_overlap = (A[2] <= B[0] or # A পুরো B-র বাঁয়ে
B[2] <= A[0] or # A পুরো B-র ডানে
A[3] <= B[1] or # A পুরো B-র নিচে
B[3] <= A[1]) # A পুরো B-র উপরে
return not no_overlap
def interval_overlap(a1, a2, b1, b2):
"""1D version: interval [a1,a2] আর [b1,b2] positive overlap করে কি?"""
return a1 < b2 and b1 < a2
def overlap_via_intervals(A, B):
"""একই উত্তর, কিন্তু পরিষ্কারভাবে দুটো 1D check হিসেবে।"""
x_ok = interval_overlap(A[0], A[2], B[0], B[2])
y_ok = interval_overlap(A[1], A[3], B[1], B[3])
return x_ok and y_ok
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert overlap((0, 0, 2, 2), (1, 1, 3, 3)) is True # কোণায় ঢুকেছে
assert overlap((0, 0, 2, 2), (2, 2, 4, 4)) is False # শুধু কোণ ছোঁয়
assert overlap((0, 0, 4, 4), (1, 1, 2, 2)) is True # B ভেতরে
assert overlap((0, 0, 2, 2), (3, 0, 5, 2)) is False # x-এ ফাঁক
assert overlap((0, 0, 2, 2), (0, 3, 2, 5)) is False # y-এ ফাঁক
assert overlap((0, 0, 3, 3), (2, 2, 5, 5)) is True # অংশত
# দুই পদ্ধতি একই উত্তর দেয় কি না
for A, B in [((0,0,2,2),(1,1,3,3)), ((0,0,2,2),(2,2,4,4)),
((0,0,2,2),(3,0,5,2)), ((0,0,4,4),(1,1,2,2))]:
assert overlap(A, B) == overlap_via_intervals(A, B)
assert interval_overlap(1, 3, 2, 4) is True # [1,3] ∩ [2,4]
assert interval_overlap(1, 2, 2, 4) is False # শুধু 2-তে ছোঁয়
print(overlap((0, 0, 2, 2), (1, 1, 3, 3))) # True
print(overlap((0, 0, 2, 2), (2, 2, 4, 4))) # False
print(overlap_via_intervals((0, 0, 3, 3), (2, 2, 5, 5))) # True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def overlap(A, B):
no_overlap = (A[2] <= B[0] or B[2] <= A[0] or
A[3] <= B[1] or B[3] <= A[1])
return not no_overlap
```
`A[2]` হলো A-র ডান প্রান্ত (x2), `B[0]` হলো B-র বাঁ প্রান্ত (x1)। `A[2] <= B[0]` মানে A পুরো B-র বাঁয়ে। চারটা শর্তের যেকোনোটা সত্যি হলে overlap নেই। `not` দিয়ে উল্টে আসল উত্তর। `<=` মানে শুধু ধার ছোঁয়াকে overlap ধরছি না।
```
def interval_overlap(a1, a2, b1, b2):
return a1 < b2 and b1 < a2
```
1D-তে দুটো interval positive overlap করে যদি একটা শুরু অন্যটার শেষের আগে আর উল্টোটাও — `a1 < b2 and b1 < a2`। `<` মানে শুধু ছোঁয়া যথেষ্ট নয়।
```
def overlap_via_intervals(A, B):
x_ok = interval_overlap(A[0], A[2], B[0], B[2])
y_ok = interval_overlap(A[1], A[3], B[1], B[3])
return x_ok and y_ok
```
এটাই decomposition-টা স্পষ্ট দেখায় — x-অক্ষে interval overlap **এবং** y-অক্ষে interval overlap, তবেই rectangle overlap।
বাকি `assert` লাইনগুলো — কোণ-ছোঁয়া, ভেতরে-থাকা, ফাঁক, আর দুই পদ্ধতির মিল — সব যাচাই করছে; সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
True
False
True
সব test pass!
```
প্রথম: (0,0,2,2) আর (1,1,3,3) কোণায় কোণায় ঢুকেছে → True। দ্বিতীয়: (0,0,2,2) আর (2,2,4,4) শুধু কোণ (2,2) ছোঁয়, positive area নেই → False। তৃতীয়: interval পদ্ধতিতেও (0,0,3,3) আর (2,2,5,5) overlap → True। তার আগের সব `assert` চুপচাপ pass করেছে। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — চারটা তুলনা (বা দুটো interval check), input-নির্বিশেষে ধ্রুবক। rectangle যত বড়ই হোক, কাজ একই।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু কয়েকটা bool variable। কোনো বাড়তি data structure নেই।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`<` আর `<=` মিশিয়ে ফেলা** — শুধু ধার/কোণ ছোঁয়াকে overlap ধরবে কি না, সংজ্ঞা না পড়ে ভুল operator; positive area চাইলে negation-এ `<=` (এখানে যেমন)।
2. **সব "করে" case সরাসরি গোনার চেষ্টা** — case-এর জঙ্গল; negation ("করে না") চারটা পরিষ্কার শর্তে নামায়।
3. **এক অক্ষ ভুলে যাওয়া** — শুধু x বা শুধু y দেখলে ভুল; দুটো অক্ষেই overlap লাগবে।
4. **কোণ-input ভুল ধরা** — `(x1,y1)` নিচ-বাঁ, `(x2,y2)` উপর-ডান ধরে নিয়েছি; কেউ width/height বা অন্য কোণ দিলে আগে normalize করো।
5. **কাত করা (rotated) rectangle-এ এই trick খাটানো** — এটা শুধু axis-aligned-এ; rotated হলে আলাদা (separating axis) দরকার।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Rectangle Area** (