৫টি সহজ Array কোডিং প্রবলেম ও সমাধান (Java)

সিরিজের পঞ্চম ফাইল। Array হলো ইন্টারভিউয়ের সবচেয়ে বড় ময়দান — এখানকার প্যাটার্নগুলো: HashMap দিয়ে complement খোঁজা, one-pass tracking (min/max), two pointer (in-place), Kadane's algorithm, prefix product। এই ৫টি প্রবলেম এমনভাবে বাছা যে প্রতিটি একটি করে নতুন প্যাটার্ন শেখায়।

প্রবলেম ১: Two Sum (LeetCode 1)

প্রশ্ন: একটি array ও একটি target দেওয়া। যে দুটি সংখ্যার যোগফল target, তাদের index রিটার্ন করুন। [2,7,11,15], target 9 → [0,1]।

চিন্তার ধাপ: পৃথিবীর সবচেয়ে বিখ্যাত ইন্টারভিউ প্রশ্ন। Brute force: প্রতিটি জোড়া চেক — O(n²)। চাবিকাঠি: প্রতিটি সংখ্যার জন্য প্রশ্নটা উল্টে দিন — "আমার complement (target − আমি) কি আগে দেখা গেছে?" HashMap-এ দেখা সংখ্যা ও তার index রাখুন — এক pass-এই শেষ।

সমাধান:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();  // value → index

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];

        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);  // চেকের *পরে* রাখুন
    }
    return new int[]{};  // প্রশ্নমতে সমাধান সবসময় আছে
}

Complexity: Time O(n), Space O(n)।

ইন্টারভিউ টিপ: seen.put(...) টি complement চেকের পরে — আগে রাখলে target = 6, nums = [3, ...]-এ 3 নিজেকেই নিজের জোড়া বানিয়ে ফেলবে। এই ক্রমটাই প্রবলেমের আসল ফাঁদ। নিশ্চিত follow-up: "array টি sorted হলে?" → তখন HashMap লাগে না — দুই প্রান্ত থেকে two pointer, O(1) space (LeetCode 167)। Sorted শুনলেই two pointer/binary search মাথায় আসা চাই।

প্রবলেম ২: Best Time to Buy and Sell Stock (LeetCode 121)

প্রশ্ন: প্রতিদিনের শেয়ারের দাম দেওয়া। একবার কিনে একবার বেচে সর্বোচ্চ লাভ কত? [7,1,5,3,6,4] → 5 (১-এ কিনে ৬-এ বেচা)। কেনা অবশ্যই বেচার আগে।

চিন্তার ধাপ: One-pass tracking — হাঁটতে হাঁটতে দুটি জিনিস মনে রাখুন: এ পর্যন্ত দেখা সর্বনিম্ন দাম, আর "আজ বেচলে লাভ কত" (আজকের দাম − সর্বনিম্ন)। প্রতিদিন সর্বোচ্চ লাভ update করুন। ভবিষ্যৎ জানার দরকার নেই — অতীতের minimum-ই যথেষ্ট।

সমাধান:

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;                      // নতুন সর্বনিম্ন কেনার দাম
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;          // আজ বেচলে বেশি লাভ?
        }
    }
    return maxProfit;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: দাম শুধু কমতেই থাকলে ([7,6,4,3,1]) উত্তর 0 — "কিনবই না" ও একটি বৈধ সিদ্ধান্ত; maxProfit = 0 দিয়ে শুরু করাতেই সেটা সামলে যায়। এটি আসলে ছদ্মবেশী Kadane's algorithm (পরের প্রবলেম) — প্রতিদিনের দামের পার্থক্যের উপর maximum subarray। এই সংযোগটি বলতে পারলে দারুণ।

প্রবলেম ৩: Maximum Subarray (LeetCode 53) — Kadane's Algorithm

প্রশ্ন: যে টানা (contiguous) subarray-র যোগফল সর্বোচ্চ, সেই যোগফলটি দিন। [-2,1,-3,4,-1,2,1,-5,4] → 6 ([4,-1,2,1])।

চিন্তার ধাপ: Kadane's algorithm — প্রতিটি ঘরে দাঁড়িয়ে একটাই সিদ্ধান্ত: "আগের subarray-র সাথে যোগ দেব, নাকি এখান থেকে নতুন শুরু করব?" আগের চলতি যোগফল ঋণাত্মক হলে সেটি বোঝা — ফেলে দিয়ে নতুন শুরু। এই এক লাইনের সিদ্ধান্তই পুরো অ্যালগরিদম।

সমাধান:

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
        // আগেরটা টেনে লাভ আছে? নাকি নতুন শুরু?
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: maxSum = 0 দিয়ে শুরু করা common ভুল — সব সংখ্যা ঋণাত্মক হলে ([-3,-1,-2] → উত্তর -1) ভুল আসবে; তাই nums[0] দিয়ে শুরু। Follow-up গুলো জেনে রাখুন: "subarray-টাও দেখান" → নতুন শুরুর index মনে রাখুন; "divide and conquer-এ করুন" → সম্ভব, O(n log n), কিন্তু Kadane-ই শ্রেষ্ঠ; "maximum product subarray হলে?" (LeetCode 152) → ঋণাত্মক × ঋণাত্মক = ধনাত্মক বলে min-ও track করতে হয়।

প্রবলেম ৪: Move Zeroes (LeetCode 283)

প্রশ্ন: Array-র সব 0 শেষে পাঠান, বাকি সংখ্যাগুলোর ক্রম ঠিক রেখে — in-place, নতুন array ছাড়া। [0,1,0,3,12] → [1,3,12,0,0]।

চিন্তার ধাপ: Two pointer (same direction / read-write pointer) — একটি pointer (write) দেখায় পরবর্তী nonzero সংখ্যাটি কোথায় বসবে; আরেকটি (read) পুরো array হাঁটে। Read যা-ই nonzero পায়, write-এর ঘরে বসিয়ে write এগিয়ে দেয়। শেষে write থেকে বাকি সব ঘরে 0।

সমাধান:

public void moveZeroes(int[] nums) {
    int write = 0;

    // Pass ১: সব nonzero সামনে জড়ো করুন
    for (int read = 0; read < nums.length; read++) {
        if (nums[read] != 0) {
            nums[write] = nums[read];
            write++;
        }
    }
    // Pass ২: বাকিটা 0 দিয়ে ভরাট
    while (write < nums.length) {
        nums[write] = 0;
        write++;
    }
}

Complexity: Time O(n), Space O(1)।

ইন্টারভিউ টিপ: এই read-write pointer প্যাটার্নটিই Remove Duplicates from Sorted Array (26), Remove Element (27) — সব in-place প্রবলেমের ছাঁচ। "In-place, order ঠিক রেখে" শুনলেই হাত এই প্যাটার্নে যাওয়া চাই। Follow-up: "লেখার সংখ্যা কমান" → nonzero হলে swap(nums[write], nums[read]) — এক pass, আগে থেকে সঠিক জায়গায় থাকা ঘরে লেখাও এড়ানো যায়।

প্রবলেম ৫: Product of Array Except Self (LeetCode 238)

প্রশ্ন: প্রতিটি index-এর জন্য বাকি সব সংখ্যার গুণফল দিন — ভাগ (division) ব্যবহার না করে, O(n)-এ। [1,2,3,4] → [24,12,8,6]।

চিন্তার ধাপ: i-তম উত্তর = (i-এর বামের সবার গুণফল) × (i-এর ডানের সবার গুণফল)। তাহলে: এক pass বাম থেকে prefix product, আরেক pass ডান থেকে suffix product। কৌশল: output array-তেই prefix রাখুন, suffix একটি চলমান variable-এ — বাড়তি array লাগে না।

সমাধান:

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // Pass ১ (বাম → ডান): result[i] = i-এর বামের সবার গুণফল
    result[0] = 1;
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] * nums[i - 1];
    }

    // Pass ২ (ডান → বাম): চলমান suffix গুণ করে দিন
    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= suffix;
        suffix *= nums[i];
    }
    return result;
}

Complexity: Time O(n), Space O(1) — output array space হিসেবে ধরা হয় না (প্রশ্নেই বলা)।

ইন্টারভিউ টিপ: "ভাগ দিয়ে তো সহজ — মোট গুণফল ÷ nums[i]" — বলুন, তারপর বলুন কেন নিষেধ: 0 থাকলে ভেঙে পড়ে (একটি 0 থাকলে ওই ঘর ছাড়া সব 0; দুটি 0 থাকলে সব 0 — ভাগ দিয়ে এই case সামলানো কুৎসিত)। এই prefix/suffix চিন্তাটিই বড় হয়ে prefix sum হয় — range sum query, subarray sum equals K (560) — Staff-level array প্রবলেমের মেরুদণ্ড।

Array প্যাটার্ন — মনে রাখুন

তিনটি সোনার নিয়ম:

১. "Sorted" শব্দটি একটি hint — sorted শুনলেই two pointer বা binary search ভাবুন; unsorted-এ HashMap। ২. Overflow-এর কথা মুখে বলুন — গুণফলের প্রবলেমে int overflow হতে পারে, "প্রয়োজনে long নেব" এক লাইনে বলা senior signal। ৩. Edge case-এর checklist: খালি array, এক element, সব ঋণাত্মক, সব একই — কোড লেখার আগে এগুলো উচ্চারণ করুন।

পরবর্তী ধাপ: medium-এ যান — 3Sum (15, Two Sum + sorting + two pointer), Container With Most Water (11), Subarray Sum Equals K (560, prefix sum + HashMap — এই ফাইলের প্রবলেম ১ ও ৫-এর মিলন), Merge Intervals (56)।