কনটেন্টে যান

009 — Two Sum II - Input Array Is Sorted

Problem link ও উৎস

  • 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-ই পাশাপাশি রেখে তুলনা করো

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা সাজানো (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 নয়)

Input ও 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 টাকার দুটো জিনিস কিনতে চাও। বাঁ দিক থেকে সবচেয়ে সস্তা আর ডান দিক থেকে সবচেয়ে দামি জিনিসে আঙুল রাখো। যোগফল বেশি হলে দামি আঙুলটা একটু সস্তার দিকে সরাও; কম হলে সস্তা আঙুলটা একটু দামির দিকে সরাও। দুই আঙুল মাঝখানে এসে মিললেই জোড়া পেয়ে গেছ — পুরো তালিকা বারবার পড়তে হলো না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

দুটো বিকল্প:

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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-হওয়াকে কাজে না লাগিয়ে।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

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 বাদ দিচ্ছে।

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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-হওয়াকে এটা ব্যবহারই করে না।

Output মিলিয়ে দেখা

দুটো 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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।