009 — Two Sum II - Input Array Is Sorted¶

Source¶

Original source: Classic sorted-array pair problem
Platform: LeetCode — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
Topic: hash map vs two pointers
Difficulty: Medium
Pattern: complement lookup vs two pointers
Basic idea inherited from: Two Sum — দুটো approach-ই পাশাপাশি রেখে তুলনা করো

1. Problem in simple words¶

একটা সাজানো (non-decreasing) সংখ্যার array numbers আর একটা target দেওয়া আছে। এমন দুটো position ফেরত দিতে হবে যাদের সংখ্যা যোগ করলে ঠিক target হয়। এখানে একটা ছোট্ট কিন্তু গুরুত্বপূর্ণ শর্ত: উত্তর 1-indexed (অর্থাৎ প্রথম element-এর position 1, 0 নয়), আর ধরে নাও উত্তর সবসময় একটাই।

numbers = [2, 7, 11, 15], target = 9
2 + 7 = 9  →  উত্তর [1, 2]  (position, index নয়)

2. Which basic idea does this inherit from?¶

এটা সরাসরি Two Sum (এই tracker-এর #1)-এর উপর দাঁড়িয়ে। সেখানে array এলোমেলো ছিল, তাই hash map দিয়ে complement মনে রাখা ছাড়া উপায় ছিল না। এখানে নতুন তথ্য একটাই — array sorted। এই একটা শব্দ পুরো খেলা বদলে দেয়: এখন তুমি দুটো রাস্তায় যেতে পারো, আর সেই দুটো তুলনা করাই এই note-এর আসল শিক্ষা।

3. What is the hidden math or logic?¶

লুকানো logic দুই স্তরের। প্রথম স্তর Two Sum-এর মতোই: a + b = target মানে a-র partner ঠিক target - a। দ্বিতীয় স্তর sorted-হওয়া থেকে আসে — যদি দুই প্রান্ত থেকে দুটো সংখ্যা নাও আর তাদের যোগফল target-এর চেয়ে বড় হয়, তাহলে বড় প্রান্তটা ছোট করলেই যোগফল কমবে; ছোট হলে ছোট প্রান্তটা বড় করলে যোগফল বাড়বে। অর্থাৎ প্রতিটা তুলনা একটা possibility একেবারে ছেঁটে ফেলে।

4. Which data structure is needed?¶

দুটো বিকল্প:

Two pointers: কোনো extra structure লাগে না — শুধু দুটো index lo আর hi। কাজ করে কারণ array sorted।
Hash map (dict, value → position): Two Sum-এর হুবহু রাস্তা, sorted-হওয়াকে উপেক্ষা করে।

5. Why this data structure fits¶

Sorted array-তে two pointers একদম মানানসই, কারণ ক্রমটাই তোমাকে বলে দেয় কোন দিকে সরতে হবে — তাই O(1) extra space-এই কাজ শেষ। Hash map-ও কাজ করে আর গড়ে O(1) lookup দেয়, কিন্তু O(n) extra জায়গা খায় যেটা এখানে অপ্রয়োজনীয়। মূল শিক্ষা: input-এর গঠন (sorted) জানা থাকলে data structure-এর খরচ কমানো যায়।

6. Real-life analogy¶

ভাবো একটা সাজানো দামের তালিকা ধরে তুমি ঠিক 9 টাকার দুটো জিনিস কিনতে চাও। বাঁ দিক থেকে সবচেয়ে সস্তা আর ডান দিক থেকে সবচেয়ে দামি জিনিসে আঙুল রাখো। যোগফল বেশি হলে দামি আঙুলটা একটু সস্তার দিকে সরাও; কম হলে সস্তা আঙুলটা একটু দামির দিকে সরাও। দুই আঙুল মাঝখানে এসে মিললেই জোড়া পেয়ে গেছ — পুরো তালিকা বারবার পড়তে হলো না।

7. Visual explanation¶

numbers = [2, 7, 11, 15], target = 9। lo বাঁ থেকে, hi ডান থেকে চাপ দেয়:

lo=0(2)            hi=3(15)   s=2+15=17 > 9  → hi-- (বড় দিকটা ছোট করো)
lo=0(2)        hi=2(11)       s=2+11=13 > 9  → hi--
lo=0(2)    hi=1(7)            s=2+7 =9  == 9 → return [lo+1, hi+1] = [1, 2]

প্রতিবার একটা প্রান্ত নড়ছে, আর প্রতিটা নড়া পুরো একটা সারি বা কলামের possibility বাদ দিচ্ছে।

8. Example input and output¶

Input : numbers = [2, 7, 11, 15], target = 9    Output: [1, 2]
Input : numbers = [2, 3, 4],      target = 6    Output: [1, 3]
Input : numbers = [-1, 0],        target = -1   Output: [1, 2]
Edge  : numbers = [5, 25, 75],    target = 100  Output: [2, 3]

9. Brute force thinking¶

প্রথম সরল চিন্তা Two Sum-এর মতোই: প্রতিটা জোড়া (i, j) ধরে দেখো যোগফল target কি না।

প্রতিটা i-র জন্য:
    প্রতিটা j > i-র জন্য:
        numbers[i] + numbers[j] == target হলে return [i+1, j+1]

10. Why brute force is slow¶

দুটো nested loop মানে O(n^2)। আর এখানে অপচয়টা আরও দৃষ্টিকটু, কারণ array sorted — অর্থাৎ ক্রমটা একটা বিনামূল্যের ইঙ্গিত দিচ্ছে কোন দিকে partner আছে, অথচ brute force সেই ইঙ্গিত পুরো ফেলে দিয়ে সব জোড়া পরীক্ষা করছে। জানা গঠন কাজে না লাগানোই এখানে আসল ভুল।

11. Key observation¶

মূল observation: sorted মানে দিক জানা। দুই প্রান্তের যোগফল target থেকে বড় হলে উত্তর আরও বাঁয়ে; ছোট হলে আরও ডানে। তাই প্রতিটা তুলনায় অন্তত একটা সংখ্যা চিরতরে বাদ পড়ে — খোঁজার জায়গা প্রতি ধাপে এক ঘর সংকুচিত হয়।

12. Optimized intuition¶

lo আর hi দুই প্রান্তে বসাও। যোগফল দেখো: সমান হলে জোড়া পেয়ে গেছ (1-indexed করে ফেরত দাও); বেশি হলে hi কমাও; কম হলে lo বাড়াও। lo আর hi মাঝখানে এসে মেলা পর্যন্ত চালাও — এক pass, O(n) time, O(1) space। বিকল্পে Two Sum-এর hash map রাস্তাও কাজ করে (O(n) time কিন্তু O(n) space) — sorted-হওয়াকে কাজে না লাগিয়ে।

13. Thinking tweak¶

মোচড়: sorted শুনলেই দুই প্রান্ত থেকে চাপ দেওয়ার কথা ভাবো। Two Sum-এ tweak ছিল "search না করে remember করো"; এখানে sorted-হওয়া আরও সস্তা একটা tweak খুলে দেয় — "remember করারও দরকার নেই, ক্রম ধরে দুদিক থেকে এগোও"। একই problem, কম জায়গা।

14. Step-by-step dry run¶

Input numbers = [2, 3, 4], target = 6:

শুরু: lo = 0 (মান 2), hi = 2 (মান 4)।
s = 2 + 4 = 6; 6 == 6 → জোড়া পেয়ে গেছি।
return [lo + 1, hi + 1] = [1, 3]।
শেষ: উত্তর [1, 3]।

15. Python solution¶

def two_sum_two_pointers(numbers, target):
    lo, hi = 0, len(numbers) - 1       # দুই প্রান্ত থেকে চাপ দাও
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s == target:
            return [lo + 1, hi + 1]    # problem 1-indexed উত্তর চায়
        elif s < target:
            lo += 1                    # যোগফল ছোট → বড় দিকে সরো
        else:
            hi -= 1                    # যোগফল বড় → ছোট দিকে সরো
    return []

def two_sum_hash(numbers, target):
    seen = {}                          # value -> 1-indexed position
    for i, x in enumerate(numbers):
        need = target - x
        if need in seen:
            return [seen[need], i + 1]
        seen[x] = i + 1
    return []

# ---- tests ----
for solve in (two_sum_two_pointers, two_sum_hash):
    assert solve([2, 7, 11, 15], 9) == [1, 2]
    assert solve([2, 3, 4], 6) == [1, 3]
    assert solve([-1, 0], -1) == [1, 2]
    assert solve([1, 2, 3, 4, 4, 9, 56, 90], 8) == [4, 5]
    assert solve([5, 25, 75], 100) == [2, 3]
print("সব test pass!")

16. Line-by-line code explanation¶

lo, hi = 0, len(numbers) - 1 — দুই প্রান্তে দুটো pointer বসাই।
while lo < hi — যতক্ষণ তারা পরস্পরকে পার না করছে।
s = numbers[lo] + numbers[hi] — এই মুহূর্তের জোড়ার যোগফল।
if s == target: return [lo + 1, hi + 1] — মিলে গেলে 1-indexed করে ফেরত।
elif s < target: lo += 1 — কম পড়েছে, বড় মানের দিকে সরি।
else: hi -= 1 — বেশি হয়েছে, ছোট মানের দিকে সরি।
দ্বিতীয় function two_sum_hash — Two Sum-এর হুবহু complement lookup, শুধু position 1-indexed করা; sorted-হওয়াকে এটা ব্যবহারই করে না।

17. Output walkthrough¶

দুটো function-ই একই উত্তর দেয়, তাই test একটা loop-এ দুটোকেই যাচাই করে। [2,7,11,15] target 9-এ two-pointer hi দুবার কমে 7-এ এসে থামে → [1, 2]; hash রাস্তা 7-এ এসে 2 আগে দেখা পায় → [1, 2]। [2,3,4] target 6 → [1, 3]। [-1,0] target -1 → [1, 2]। শেষে print: সব test pass!।

18. Time complexity¶

দুটো রাস্তাই O(n) — two pointers এক pass-এ array scan করে; hash map-ও এক pass, প্রতি element-এ গড়ে O(1) operation।

19. Space complexity¶

এখানেই পার্থক্য: two pointers O(1) extra (শুধু দুটো index), কিন্তু hash map O(n) extra (সব দেখা value জমে)। Sorted-হওয়াকে কাজে লাগিয়ে আমরা space O(n) থেকে O(1)-এ নামালাম।

20. Common mistakes¶

1-indexing ভুলে যাওয়া — problem position চায়, index নয়; +1 বাদ দিলে উত্তর এক ঘর সরে যায়।
sorted-হওয়া উপেক্ষা করে শুধু hash map লেখা — কাজ করবে, কিন্তু interview-তে "sorted দেখে কী সুবিধা পেলে?" প্রশ্নের উত্তর হারাবে।
while lo < hi-র বদলে lo <= hi লেখা — তখন একই element নিজের সাথে জোড়া বানিয়ে ভুল করতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি: Two Sum (#1)-এর complement lookup। নতুন সংযোজন হলো sorted-array-এর two-pointer চাল, যা arrays section-এর "দুই প্রান্ত থেকে এগোনো" idea-র সাথে এই chapter-এর pair-thinking মিশিয়ে দেয়। ../patterns.md-র Pattern 2 (complement lookup)-ই এর মূল।

22. Similar harder problems¶

Two Sum — https://leetcode.com/problems/two-sum/ (এই tracker-এর #1; unsorted মূল রূপ)
3Sum — https://leetcode.com/problems/3sum/ (sort + two pointers একসাথে)
4Sum II — https://leetcode.com/problems/4sum-ii/ (এই tracker-এর #16; pair-sum-এ complement)

23. Pattern learned¶

Complement lookup vs two pointers: unsorted হলে hash map দিয়ে partner মনে রাখো (O(n) space); sorted হলে দুই প্রান্ত থেকে চাপ দিয়ে একই কাজ O(1) space-এ সারো।

24. Final summary¶

ভবিষ্যতের আমাকে: "pair with sum" দেখলে complement মনে পড়বেই, কিন্তু সঙ্গে চোখ রাখবে input sorted কি না। Sorted হলে two pointers বেছে নাও — একই O(n) time, কিন্তু space O(n) থেকে O(1)। এই note-টা মূলত একটা তুলনা: একই problem, ভিন্ন তথ্য, ভিন্ন খরচ।

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