121 — Manhattan Distance Tricks

এই problem-টা একটা সত্যিকারের "magic trick" শেখায়: coordinate গুলোকে 45° ঘুরিয়ে দিলে কঠিন Manhattan distance হঠাৎ সহজ Chebyshev distance হয়ে যায়! এই একটা রূপান্তর জানা থাকলে "n বিন্দুর মধ্যে সর্বোচ্চ Manhattan দূরত্ব কত" — যেটা সরল ভাবে O(n²) — সেটা O(n)-এ নেমে আসে। Geometry-তে মনে রেখো: ছবি না এঁকে code লেখা নিষেধ, তাই এই note-এ ASCII ছবিগুলো মন দিয়ে দেখো।

Source

• Original source: Classic CP trick (Manhattan ↔ Chebyshev rotation)
• Platform: — (classic competitive programming technique)
• Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
• Difficulty: Medium
• Pattern: 45° rotation (coordinate ঘুরিয়ে Manhattan-কে Chebyshev বানানো)
• Basic idea inherited from: 113 — Distance Between Points

1. Problem in simple words

দুটো বিন্দুর Manhattan distance হলো |x1 − x2| + |y1 − y2| — অর্থাৎ গ্রিড ধরে (শুধু আড়াআড়ি-খাড়া, কোনাকুনি নয়) হাঁটলে যত ঘর পেরোতে হয়। এটা নিজে সহজ। আসল মজা শুরু হয় যখন অনেক বিন্দু থাকে আর জিজ্ঞেস করা হয়:

nটা বিন্দুর মধ্যে যেকোনো দুটোর সর্বোচ্চ Manhattan distance কত?

সরল উপায় — প্রতিটা জোড়া ধরে দূরত্ব মাপা, O(n²)। কিন্তু একটা চমৎকার coordinate-trick দিয়ে এটা O(n)-এ নামানো যায়। এই note-এ আমরা trick-টা শিখব, তারপর সেটা দিয়ে "max pairwise Manhattan distance" দ্রুত বের করব।

মনে রাখো — Manhattan distance-এ ওই + চিহ্নটাই (দুটো absolute যোগ) সব জোড়া একসাথে optimize করা কঠিন করে; trick-টা সেই +-কে সরিয়ে দেয়।

2. What is the math idea?

মূল গাণিতিক রূপান্তর — প্রতিটা বিন্দু (x, y)-কে নতুন coordinate-এ পাঠাও: u = x + y, v = x − y (এটাই 45° ঘোরানো + scaling)। তখন আশ্চর্য সত্য:

Manhattan distance |Δx| + |Δy| = Chebyshev distance max(|Δu|, |Δv|)।

কেন? |Δx| + |Δy| সবসময় max(|Δx + Δy|, |Δx − Δy|)-এর সমান (চারটে চিহ্ন-সমন্বয় খুলে দেখলেই মেলে)। আর Δu = Δx + Δy, Δv = Δx − Δy — তাই max(|Δu|, |Δv|)।

এর বড় লাভ: Chebyshev distance-এ u আর v আলাদা আলাদা optimize করা যায় (max আর min independent), কিন্তু Manhattan-এ যোগের কারণে তা যেত না। তাই max pairwise Manhattan = max( max(u) − min(u), max(v) − min(v) ) — সব বিন্দু একবার ঘেঁটে u, v-এর max/min বের করলেই হলো, O(n)।

3. Which basic idea does this inherit from?

এটা দাঁড়িয়ে আছে 113 — Distance Between Points-এর উপর। 113-এ তুমি দূরত্বের ভিত্তি (Euclidean squared distance, আর coordinate পার্থক্য Δx, Δy) শিখেছিলে। এখানে সেই coordinate-পার্থক্যের ধারণাকেই একটা নতুন coordinate system-এ নিয়ে যাচ্ছি — distance-এর সংজ্ঞা একই রকম থাকছে, শুধু অক্ষ দুটো 45° ঘুরে যাচ্ছে।

নতুন যেটা যোগ হলো — Manhattan vs Chebyshev-এর সম্পর্ক, আর coordinate transform-কে একটা সমস্যা-সরলীকরণের হাতিয়ার হিসেবে ব্যবহার করা। এই "অক্ষ ঘুরিয়ে সমস্যা সহজ করা" চিন্তাটা 122 (Rotate Matrix)-এও ফিরবে অন্য মোড়কে। তাই 113-এর distance-ভিত্তি + একটা চালাক রূপান্তর = এই problem।

4. Real-life analogy

ভাবো একটা শহরের রাস্তা সব উত্তর-দক্ষিণ আর পূর্ব-পশ্চিম বরাবর (গ্রিড শহর, যেমন ম্যানহাটান — তাই নাম!)। দুই জায়গার মধ্যে ট্যাক্সিকে শুধু রাস্তা ধরে যেতে হয়, কোনাকুনি বাড়ির ভেতর দিয়ে নয় — তাই দূরত্ব |Δx| + |Δy|।

এবার ভাবো একজন মানুষ যে শুধু কোনাকুনি (diagonal) হাঁটতে পারে, আর আড়াআড়ি/খাড়াও — অর্থাৎ রাজার মতো আট দিকে এক ঘর (Chebyshev)। তার কাছে দূরত্ব max(|Δx|, |Δy|)। trick-টা বলছে: ট্যাক্সির শহরের মানচিত্রটা যদি তুমি ঠিক 45° কাত করে ধরো, তাহলে ট্যাক্সির গ্রিড-দূরত্ব দেখতে হবে অবিকল রাজার কোনাকুনি-দূরত্বের মতো। মানে একই দূরত্ব, শুধু চোখটা 45° ঘুরিয়ে দেখলে হিসাবটা সহজ হয়ে যায় — যোগের ঝামেলা মিলিয়ে গিয়ে দুটো স্বাধীন max হয়ে যায়।

5. Visual explanation

প্রথমে Manhattan distance কী, একটা ছবি — গ্রিড ধরে হাঁটা:

Manhattan distance (1,2) থেকে (4,6):

 y=6 ........... B(4,6)
 y=5 .          .
 y=4 .          .   |Δx| = |4-1| = 3
 y=3 .          .   |Δy| = |6-2| = 4
 y=2 A(1,2) ----+   distance = 3 + 4 = 7
     x=1        x=4   (কোনাকুনি নয়, ধাপে ধাপে)

এবার 45° রূপান্তরের ছবি — (x,y) -> (u,v) = (x+y, x-y):

পুরোনো অক্ষ (x,y)          45° ঘুরিয়ে নতুন অক্ষ (u,v)
   y                              v   u
   |    /diamond\                  \ /
   |   /        \         ===>      X        u = x + y  (এক কর্ণ বরাবর)
   |  /  Manhattan          / \     v = x - y  (অন্য কর্ণ বরাবর)
   | /   "বল" (◇)
   +---------- x        Manhattan-এর হীরে (◇) -> Chebyshev-এর বর্গ (□)

সূত্র: |Δx| + |Δy|  =  max(|Δu|, |Δv|)

max pairwise distance কীভাবে O(n)-এ — শুধু u আর v-এর range:

বিন্দু: (0,0)  (4,0)  (0,4)  (2,2)
u=x+y:   0     4      4      4      -> max(u)-min(u) = 4-0 = 4
v=x-y:   0     4     -4      0      -> max(v)-min(v) = 4-(-4) = 8
max pairwise Manhattan = max(4, 8) = 8   (যেমন (4,0) ও (0,4): 4+4=8)

6. Example input and output

দুই-বিন্দু Manhattan:
  (1,2),(4,6)   -> 7      (3 + 4)
  (0,0),(0,0)   -> 0      (একই বিন্দু)
  (-1,-1),(2,3) -> 7      (3 + 4)

max pairwise Manhattan (বিন্দুর তালিকা):
  [(0,0),(4,0),(0,4),(2,2)]   -> 8    ((4,0)–(0,4))
  [(1,1),(1,1)]               -> 0    (সব একই)
  [(0,0),(10,0)]              -> 10   (এক জোড়া)
  [(-5,-5),(5,5),(0,0)]       -> 20   ((-5,-5)–(5,5): 10+10)

মূল edge case: একই বিন্দু (দূরত্ব 0), negative coordinate (absolute নিলে ঠিকই কাজ করে), আর সব বিন্দু একই (max pairwise 0)। trick-এ negative নিয়ে ভয় নেই — u, v negative হলেও range (max − min) ঠিক থাকে।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — সব জোড়া বিন্দু ধরো, প্রতিটার Manhattan distance মাপো, সবচেয়ে বড়টা রাখো:

def max_pair_brute(points):
    n = len(points)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            best = max(best, d)
    return best

এটা প্রতিটা জোড়া পরীক্ষা করে, তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট তালিকায় চমৎকার ও পড়তে সহজ।

8. Why brute force may be slow

জোড়ার সংখ্যা n(n−1)/2 — O(n²)। n = 100000 হলে প্রায় 500 কোটি জোড়া, contest-এ নিশ্চিত Time Limit Exceeded।

n = 100000 হলে:
  brute (সব জোড়া): ~5,000,000,000 distance হিসাব   (ধীর, O(n^2))
  rotation trick   : ~100,000 × 2 ধাপ                (O(n), এক pass-এ u,v range)

মূল অপচয় — আমরা সব জোড়া আলাদা করে দেখছি, যেখানে max distance আসলে নির্ভর করে শুধু কয়েকটা "প্রান্তিক" বিন্দুর উপর (u বা v-তে সবচেয়ে বড়/ছোট)। Manhattan-এর + চিহ্নের কারণে সরাসরি সেই প্রান্ত ধরা যায় না — কিন্তু 45° ঘুরিয়ে দিলে যায়, কারণ তখন u আর v স্বাধীন।

9. Better thinking

মূল insight — (x, y) -> (u, v) = (x + y, x − y) রূপান্তরে Manhattan = Chebyshev, আর Chebyshev-এ u, v আলাদা optimize হয়। তাই দুই-বিন্দুর দূরত্ব এক সূত্রে, আর max pairwise এক pass-এ:

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

def max_pair_manhattan(points):
    us = [x + y for x, y in points]
    vs = [x - y for x, y in points]
    return max(max(us) - min(us), max(vs) - min(vs))

us আর vs বানাতে O(n), তাদের max/min বের করতে O(n)। সব মিলিয়ে O(n) — O(n²) থেকে বিশাল লাফ। (একই trick 3D/higher-D-তেও বাড়ে, প্রতিটা চিহ্ন-সমন্বয়ের জন্য একটা অক্ষ।)

10. Thinking tweak

আসল "magic" — Manhattan distance-এর |Δx| + |Δy| (যোগ) = max(|Δx + Δy|, |Δx − Δy|) (দুই স্বাধীন রাশির max)। এই সমতাটাই গোটা trick।

কেন এটা শক্তিশালী? "যোগফল max করা" সব জোড়াকে একসাথে বাঁধে (একটা বিন্দুর x বড় হলেও y ছোট হলে যোগফল মাঝারি), তাই সহজে প্রান্ত ধরা যায় না। কিন্তু max(|u|, |v|)-এ u আর v আলাদা — তাই max distance = u-এর সবচেয়ে দূর জোড়া বা v-এর সবচেয়ে দূর জোড়া, যা শুধু চারটে প্রান্তিক মান (max u, min u, max v, min v) দেখলেই পাওয়া যায়। "Manhattan + অনেক বিন্দু + max/min খুঁজতে হবে" দেখলেই এই 45° রূপান্তর মাথায় আসুক।

11. Step-by-step dry run

points = [(0,0), (4,0), (0,4), (2,2)]-এ max pairwise Manhattan বের করি:

1. শুরু: প্রতিটা বিন্দুর u = x + y আর v = x − y হিসাব করি।
2. us = [0+0, 4+0, 0+4, 2+2] = [0, 4, 4, 4]।
3. vs = [0−0, 4−0, 0−4, 2−2] = [0, 4, −4, 0]।
4. u-এর range: max(us) − min(us) = 4 − 0 = 4।
5. v-এর range: max(vs) − min(vs) = 4 − (−4) = 8।
6. উত্তর: max(4, 8) = 8।

যাচাই: v-তে সবচেয়ে দূর জোড়া হলো max v (=4, বিন্দু (4,0)) আর min v (=−4, বিন্দু (0,4))। তাদের Manhattan = |4−0| + |0−4| = 4 + 4 = 8 — মিলে গেল, brute force-এর সাথেও।

12. Python solution

def manhattan(p, q):
    """দুই বিন্দুর Manhattan distance |Δx| + |Δy|।"""
    return abs(p[0] - q[0]) + abs(p[1] - q[1])


def manhattan_via_rotation(p, q):
    """একই দূরত্ব, 45° রূপান্তরে: max(|Δu|, |Δv|), u=x+y, v=x-y।"""
    pu, pv = p[0] + p[1], p[0] - p[1]
    qu, qv = q[0] + q[1], q[0] - q[1]
    return max(abs(pu - qu), abs(pv - qv))


def max_pair_manhattan(points):
    """n বিন্দুর মধ্যে সর্বোচ্চ pairwise Manhattan distance — O(n)।"""
    us = [x + y for x, y in points]
    vs = [x - y for x, y in points]
    return max(max(us) - min(us), max(vs) - min(vs))


def max_pair_brute(points):
    """সব জোড়া পরীক্ষা — reference (O(n^2))।"""
    n = len(points)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, manhattan(points[i], points[j]))
    return best


# --- দুই-বিন্দু test (সরল ও rotation দুটো মেলে) ---
assert manhattan((1, 2), (4, 6)) == 7
assert manhattan((0, 0), (0, 0)) == 0
assert manhattan((-1, -1), (2, 3)) == 7
assert manhattan_via_rotation((1, 2), (4, 6)) == 7
assert manhattan_via_rotation((-1, -1), (2, 3)) == 7

# --- max pairwise test ---
assert max_pair_manhattan([(0, 0), (4, 0), (0, 4), (2, 2)]) == 8
assert max_pair_manhattan([(1, 1), (1, 1)]) == 0
assert max_pair_manhattan([(0, 0), (10, 0)]) == 10
assert max_pair_manhattan([(-5, -5), (5, 5), (0, 0)]) == 20

# --- cross-check: rotation == সরল, আর fast == brute (random) ---
import random
random.seed(1)
for _ in range(5000):
    p = (random.randint(-30, 30), random.randint(-30, 30))
    q = (random.randint(-30, 30), random.randint(-30, 30))
    assert manhattan(p, q) == manhattan_via_rotation(p, q), (p, q)
for _ in range(3000):
    n = random.randint(2, 8)
    pts = [(random.randint(-20, 20), random.randint(-20, 20)) for _ in range(n)]
    assert max_pair_manhattan(pts) == max_pair_brute(pts), pts

print(manhattan((1, 2), (4, 6)))                          # 7
print(max_pair_manhattan([(0, 0), (4, 0), (0, 4), (2, 2)]))   # 8
print("সব test pass!")

13. Line-by-line explanation

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

সরাসরি সংজ্ঞা — x-পার্থক্য আর y-পার্থক্যের absolute যোগ। এটাই "গ্রিড ধরে হাঁটার" দূরত্ব।

pu, pv = p[0] + p[1], p[0] - p[1]
...
return max(abs(pu - qu), abs(pv - qv))

প্রতিটা বিন্দুকে (u, v) = (x + y, x − y)-তে পাঠাই (45° রূপান্তর)। নতুন coordinate-এ Manhattan = Chebyshev = দুই অক্ষের পার্থক্যের max। এটা manhattan-এর সমান উত্তর দেয় (cross-check তাই প্রমাণ করে)।

us = [x + y for x, y in points];  vs = [x - y for x, y in points]
return max(max(us) - min(us), max(vs) - min(vs))

max pairwise distance-এর মূল চাল। সব বিন্দুর u আর v আলাদা list-এ রাখি। Chebyshev-এ u, v স্বাধীন বলে — সর্বোচ্চ দূরত্ব হয় u-অক্ষে সবচেয়ে দূর জোড়া (max u − min u) বা v-অক্ষে সবচেয়ে দূর জোড়া (max v − min v), দুটোর বড়টা। এক pass-এ চারটে প্রান্তিক মান বের করলেই উত্তর।

cross-check অংশে 5000 জোড়ায় দুই সূত্র, আর 3000 তালিকায় fast vs brute মিলিয়ে দেখা — সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

7
8
সব test pass!

প্রথম লাইন: manhattan((1,2),(4,6)) = 3 + 4 = 7। দ্বিতীয়: max_pair_manhattan([(0,0),(4,0),(0,4),(2,2)]) → dry run-এ পাওয়া 8 ((4,0)–(0,4) জোড়া)। তার আগের সব assert (দুই-বিন্দু + max pairwise + 8000টা random cross-check) চুপচাপ pass। সবশেষে সব test pass! — rotation trick সরল হিসাবের সাথে সর্বত্র মিলেছে।

15. Time complexity

দুই-বিন্দু distance: O(1) — কয়েকটা বিয়োগ ও যোগ। max pairwise: O(n) — u, v list বানানো O(n), max/min বের করা O(n)। brute-এর O(n²) থেকে বিশাল সাশ্রয়, কারণ আর প্রতিটা জোড়া ছুঁই না, শুধু প্রান্তিক মান।

16. Space complexity

দুই-বিন্দু: O(1)। max pairwise: O(n) — us আর vs list রাখতে। চাইলে list না বানিয়ে এক pass-এ চারটে running max/min রেখে O(1) বাড়তি স্মৃতিতেও করা যায়। মূল গণনায় বাড়তি কিছু লাগে না।

17. Common mistakes

1. রূপান্তর ভুল লেখা — সঠিক u = x + y, v = x − y। চিহ্ন উল্টে গেলে Chebyshev সমতা ভাঙে; দুই-বিন্দু cross-check দিয়ে যাচাই করো।
2. max pairwise-এ শুধু এক অক্ষ দেখা — max(u)−min(u) আর max(v)−min(v) দুটোরই বড়টা নিতে হবে; একটা বাদ দিলে কম উত্তর।
3. negative coordinate ভয় পাওয়া — u, v negative হলেও range (max − min) ঠিক; আলাদা handle লাগে না।
4. Manhattan-কে Euclidean ভাবা — |Δx| + |Δy| (গ্রিড) আর √(Δx² + Δy²) (সরলরেখা) আলাদা; এই trick শুধু Manhattan-এ খাটে।
5. একই বিন্দুর জোড়া না ভাবা — সব বিন্দু এক হলে max pairwise 0; brute-এ i < j ঠিক রাখো (নিজের সাথে জোড়া বাদ)।

18. Harder problems that inherit this idea

• Codeforces — Watchmen (https://codeforces.com/problemset/problem/650/A) — Manhattan ও Euclidean দূরত্ব সমান হওয়া জোড়া গোনা; coordinate ভাবনা একই পরিবার।
• LeetCode — Max Points on a Line (https://leetcode.com/problems/max-points-on-a-line/) — coordinate-নির্ভর জোড়া বিশ্লেষণ, geometry pairing-এর আত্মীয়।
• LeetCode — Minimum Cost to Make at Least One Valid Path in a Grid (https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/) — গ্রিড-চলন ও Manhattan ভিত্তি; coordinate-geometry চিন্তার বিস্তার।

19. Pattern learned

Manhattan ↔ Chebyshev via 45° rotation — (x, y) -> (x + y, x − y) রূপান্তরে Manhattan distance Chebyshev হয়ে যায়; তখন দুই অক্ষ স্বাধীন, তাই max pairwise Manhattan = max(range of u, range of v), O(n)। বড় শিক্ষা: যোগফল-ভিত্তিক distance (যা জোড়া বাঁধে) coordinate ঘুরিয়ে max-ভিত্তিক করে ফেললে অক্ষগুলো আলাদা হয়ে যায় — তখন প্রান্তিক মান দেখলেই উত্তর, সব জোড়া নয়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Manhattan trick = (x,y)→(x+y, x−y); তখন |Δx|+|Δy| = max(|Δu|,|Δv|) (Chebyshev), আর max pairwise Manhattan = max(u-range, v-range) O(n)। Signal: 'Manhattan + অনেক বিন্দু + max/min' দেখলেই 45° রূপান্তর মনে পড়ুক — যোগ ভেঙে দুই স্বাধীন অক্ষ।"

পরের ধাপ → 122 — Rotate Matrix and Coordinates (আরেক রকম অক্ষ-ঘোরানো)। ভিত্তি → 113 — Distance Between Points। সম্পর্কিত → 119 — Circle and Point।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

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