ভূমিকা

এই পোস্টে আমরা Array সম্পর্কিত ৫টি মিডিয়াম লেভেলের কোডিং সমস্যা দেখব এবং Java ব্যবহার করে সেগুলোর বিস্তারিত সমাধান করব। প্রতিটি সমস্যার জন্য সমস্যার বিবরণ, চিন্তার পদ্ধতি এবং সম্পূর্ণ কোড দেওয়া হয়েছে।

---

সমস্যা ১: দুইটি সংখ্যার যোগফল (Two Sum)

সমস্যার বিবরণ

একটি integer array nums এবং একটি target সংখ্যা দেওয়া আছে। Array-এর এমন দুটি সংখ্যার index খুঁজে বের করতে হবে যাদের যোগফল target-এর সমান।

উদাহরণ:

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1]
• কারণ: nums[0] + nums[1] = 2 + 7 = 9

চিন্তার পদ্ধতি

Brute force পদ্ধতিতে দুটি loop ব্যবহার করলে সময় জটিলতা O(n²) হয়। কিন্তু HashMap ব্যবহার করলে আমরা এটি O(n) সময়ে সমাধান করতে পারি।

প্রতিটি element-এর জন্য complement = target - nums[i] বের করি। যদি এই complement আগে দেখা গিয়ে থাকে, তাহলে উত্তর পেয়ে গেছি।

সমাধান (Java)

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // complement -> index সংরক্ষণ করার জন্য HashMap
        Map<Integer, Integer> map = new HashMap<>();

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

            // complement আগে দেখা গেছে কিনা চেক করি
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            // বর্তমান element HashMap-এ রাখি
            map.put(nums[i], i);
        }

        return new int[]{};
    }

    public static void main(String[] args) {
        TwoSum solution = new TwoSum();
        int[] result = solution.twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println("Output: [" + result[0] + ", " + result[1] + "]");
        // Output: [0, 1]
    }
}

সময় জটিলতা: O(n) স্থান জটিলতা: O(n)

---

সমস্যা ২: সর্বোচ্চ লাভ খোঁজা (Best Time to Buy and Sell Stock)

সমস্যার বিবরণ

একটি array prices দেওয়া আছে যেখানে prices[i] হলো i-তম দিনে শেয়ারের মূল্য। শেয়ার কিনে এবং পরে বিক্রি করে সর্বোচ্চ লাভ বের করতে হবে। যদি কোনো লাভ না হয় তাহলে 0 return করতে হবে।

উদাহরণ:

• Input: prices = [7, 1, 5, 3, 6, 4]
• Output: 5
• কারণ: দিন ২-তে কিনুন (মূল্য = 1), দিন ৫-তে বিক্রি করুন (মূল্য = 6), লাভ = 6 - 1 = 5

চিন্তার পদ্ধতি

আমরা একটি pointer দিয়ে এখন পর্যন্ত সবচেয়ে কম মূল্য ট্র্যাক করব এবং প্রতিটি দিনে সম্ভাব্য লাভ হিসাব করব।

সমাধান (Java)

public class BestTimeToBuyAndSellStock {
    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;
    }

    public static void main(String[] args) {
        BestTimeToBuyAndSellStock solution = new BestTimeToBuyAndSellStock();
        System.out.println(solution.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        // Output: 5
        System.out.println(solution.maxProfit(new int[]{7, 6, 4, 3, 1}));
        // Output: 0 (কোনো লাভ নেই)
    }
}

সময় জটিলতা: O(n) স্থান জটিলতা: O(1)

---

সমস্যা ৩: সর্বোচ্চ যোগফলের Subarray (Maximum Subarray - Kadane's Algorithm)

সমস্যার বিবরণ

একটি integer array nums দেওয়া আছে। এর মধ্যে সবচেয়ে বড় যোগফলের contiguous subarray খুঁজে বের করতে হবে এবং সেই যোগফল return করতে হবে।

উদাহরণ:

• Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
• Output: 6
• কারণ: [4, -1, 2, 1] এর যোগফল = 6

চিন্তার পদ্ধতি

Kadane's Algorithm ব্যবহার করি। প্রতিটি position-এ দুটি সিদ্ধান্ত নিই: ১. বর্তমান element-কে পূর্ববর্তী subarray-এর সাথে যোগ করব কিনা ২. নতুন করে এই element থেকে শুরু করব কিনা

যদি পূর্ববর্তী যোগফল নেগেটিভ হয়, তাহলে নতুন করে শুরু করাই ভালো।

সমাধান (Java)

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

        for (int i = 1; i < nums.length; i++) {
            // বর্তমান element থেকে নতুন শুরু করব নাকি আগের সাথে যোগ করব?
            currentSum = Math.max(nums[i], currentSum + nums[i]);

            // এখন পর্যন্ত সর্বোচ্চ যোগফল আপডেট করি
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        MaximumSubarray solution = new MaximumSubarray();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(solution.maxSubArray(nums));
        // Output: 6
    }
}

সময় জটিলতা: O(n) স্থান জটিলতা: O(1)

---

সমস্যা ৪: Array ঘোরানো (Rotate Array)

সমস্যার বিবরণ

একটি integer array nums এবং একটি সংখ্যা k দেওয়া আছে। Array-টিকে ডানদিকে k ধাপ ঘোরাতে হবে।

উদাহরণ:

• Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
• Output: [5, 6, 7, 1, 2, 3, 4]
• কারণ: ৩ বার ডানে ঘোরানোর পর শেষের ৩টি element সামনে চলে আসে

চিন্তার পদ্ধতি

Reverse পদ্ধতি ব্যবহার করব: ১. পুরো array reverse করি ২. প্রথম k টি element reverse করি ৩. বাকি (n-k) টি element reverse করি

এই পদ্ধতি O(1) extra space ব্যবহার করে।

সমাধান (Java)

public class RotateArray {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n; // k যদি n এর চেয়ে বড় হয়

        // ধাপ ১: পুরো array reverse করি
        reverse(nums, 0, n - 1);

        // ধাপ ২: প্রথম k টি element reverse করি
        reverse(nums, 0, k - 1);

        // ধাপ ৩: বাকি element reverse করি
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        RotateArray solution = new RotateArray();
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        solution.rotate(nums, 3);

        System.out.print("Output: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        // Output: 5 6 7 1 2 3 4
    }
}

সময় জটিলতা: O(n) স্থান জটিলতা: O(1)

---

সমস্যা ৫: Product of Array Except Self

সমস্যার বিবরণ

একটি integer array nums দেওয়া আছে। একটি নতুন array answer return করতে হবে যেখানে answer[i] হবে nums-এর সব element-এর গুণফল, শুধু nums[i] বাদে। Division operator ব্যবহার করা যাবে না এবং সময় জটিলতা O(n) হতে হবে।

উদাহরণ:

• Input: nums = [1, 2, 3, 4]
• Output: [24, 12, 8, 6]
• কারণ: answer[0] = 2*3*4 = 24, answer[1] = 1*3*4 = 12, ইত্যাদি

চিন্তার পদ্ধতি

Prefix এবং Suffix product ব্যবহার করব:

• প্রথমে বাম দিক থেকে prefix product হিসাব করি
• তারপর ডান দিক থেকে suffix product হিসাব করি
• প্রতিটি index-এ prefix[i] * suffix[i] হবে উত্তর

সমাধান (Java)

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

        // ধাপ ১: বাম দিক থেকে prefix product হিসাব করি
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // ধাপ ২: ডান দিক থেকে suffix product গুণ করি
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return result;
    }

    public static void main(String[] args) {
        ProductOfArrayExceptSelf solution = new ProductOfArrayExceptSelf();
        int[] result = solution.productExceptSelf(new int[]{1, 2, 3, 4});

        System.out.print("Output: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
        // Output: 24 12 8 6
    }
}

সময় জটিলতা: O(n) স্থান জটিলতা: O(1) (output array বাদে)

---

সারসংক্ষেপ

সমস্যা	পদ্ধতি	সময় জটিলতা	স্থান জটিলতা
Two Sum	HashMap	O(n)	O(n)
Best Time to Buy and Sell Stock	One Pass	O(n)	O(1)
Maximum Subarray	Kadane's Algorithm	O(n)	O(1)
Rotate Array	Reverse	O(n)	O(1)
Product Except Self	Prefix & Suffix	O(n)	O(1)

এই সমস্যাগুলো interview-এ খুবই সাধারণ। HashMap, Two Pointer, এবং Prefix/Suffix Sum-এর মতো pattern গুলো ভালোভাবে বুঝলে Array-এর বেশিরভাগ সমস্যা সমাধান করা সম্ভব।