Array

max element of an array

#include <iostream>
using namespace std;

int findMax(int arr[], int size) {
    // ১. প্রথম এলিমেন্টকে ম্যাক্সিমাম ধরে নাও
    int max = arr[0];

    // ২. লুপ চালিয়ে বাকিদের সাথে তুলনা করো
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i]; // নতুন বড় মান পেলে আপডেট করো
        }
    }
    return max;
}

int main() {
    int nums[] = {12, 45, 2, 67, 34};
    int size = sizeof(nums) / sizeof(nums[0]);

    cout << "Maximum Element: " << findMax(nums, size); // Output: 67

    return 0;
}

Second Largest Element

int findSecondLargest(int arr[], int size) {

  if(size <2) return -1;
  int largest = INT_MIN, secondLargest = INT_MIN;

  for(int i=0; i<size; i++){
    if(arr[i] >largest){
      secondLargest = largest;
      largest = arr[i];
    }else if(arr[i]> secondLargest && arr[i] !=largest){
      secondLargest = arr[i];
    }
  }
  return secondLargest == INT_MIN ? -1 : secondLargest;
}

Kth Largest Element in an Array

  void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            nums[lastNonZeroFoundAt] = nums[i];
            lastNonZeroFoundAt++;
        }
    }

    for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
        nums[i] = 0;
    }
    }

হিপ আসলে কী? (The Priority Ladder)

সাধারণত অ্যারেতে ডাটা থাকে ছড়ানো-ছিটানো। কিন্তু হিপ হলো ডাটা রাখার এমন একটা স্মার্ট কায়দা যেখানে সবার একটা প্রায়োরিটি বা পাওয়ার থাকে।

• Min-Heap: এখানে সবচেয়ে ছোট সংখ্যাটি থাকে সবার উপরে (গাছের মাথায়)।
• Max-Heap: এখানে সবচেয়ে বড় সংখ্যাটি থাকে সবার উপরে।

হিপ কেন দরকার? (The Efficiency Story)

মনে করো, তোমার কাছে ১ লাখ ডাটা আছে। তোমাকে বলা হলো সবচেয়ে বড় সংখ্যাটা দাও।

• অ্যারে দিয়ে করলে: তোমাকে পুরো ১ লাখ ডাটা খুঁজে দেখতে হবে ($O(n)$)।
• সর্টিং করে করলে: তোমাকে পুরোটা সাজাতে হবে ($O(n \log n)$)।
• হিপ দিয়ে করলে: হিপের একদম মাথায় যে বসে আছে তাকে তুলে নিলেই হবে! এটি সবসময় রেডি থাকে ($O(1)$ এ ডাটা দিতে)।

মেমোরিতে কাহিনীটা কীভাবে ঘটে? (The Visual Tree)

হিপ দেখতে একটা Binary Tree-এর মতো। এর দুইটা নিয়ম আছে:

• প্রতিটি বাবার (Parent) সর্বোচ্চ দুটি সন্তান (Child) থাকতে পারে।
• Min-Heap এর ক্ষেত্রে, বাবার মান সবসময় তার দুই সন্তানের চেয়ে ছোট বা সমান হতে হবে।

মজার ব্যাপার: যদিও আমরা এটাকে “গাছ” বলছি, কম্পিউটার কিন্তু এটাকে মেমোরিতে একটা সাধারণ অ্যারে হিসেবেই রাখে! শুধু ইনডেক্সিং এর একটা ম্যাজিক ব্যবহার করে:

• যদি কোনো নোড $i$ ইনডেক্সে থাকে, তবে তার বাম দিকের সন্তান থাকবে $2i + 1$ এ আর ডান দিকের সন্তান থাকবে $2i + 2$ এ।

  কখন হিপ ব্যবহার করবে?

যখনই দেখবে প্রশ্নে বলা আছে:

• Top K elements বের করো।
• Kth largest/smallest বের করো।
• সবচেয়ে বেশি ফ্রিকোয়েন্সির ডাটা দাও। তখনই চোখ বন্ধ করে Heap (Priority Queue) এর কথা ভাববে।

C++ STL-এ priority_queue ব্যবহার করে আমরা হিপের ৩টি প্রধান কাজ করি। চলো একটা Min-Heap (যেখানে ছোট সংখ্যা উপরে থাকে) দিয়ে অপারেশনগুলো দেখি:

push(x) - নতুন সদস্য যোগ করা

যখন তুমি একটা নতুন সংখ্যা হিপে ঢোকাও, সে সরাসরি উপরে গিয়ে বসে না। সে গাছের একদম শেষে ঢোকে এবং তারপর তার বাবার (Parent) সাথে তুলনা করে দেখে সে ছোট কি না। যদি ছোট হয়, সে বাবার সাথে জায়গা বদল করে উপরে উঠে আসে। একে বলে “Heapify Up”।

• টাইম কমপ্লেক্সিটি: $O(\log n)$ (কারণ তাকে বড়জোর গাছের উচ্চতা পর্যন্ত উপরে উঠতে হয়)।

pop() - মাথা ছেঁটে ফেলা

হিপে আমরা মাঝখান থেকে কিছু মুছতে পারি না। সবসময় সবচেয়ে উপরের (Root) এলিমেন্টটা মুছি।

• মুছার নিয়ম: একদম শেষের এলিমেন্টটাকে টেনে মাথায় বসিয়ে দেওয়া হয়, তারপর তাকে নিচের সন্তানদের সাথে তুলনা করে সঠিক জায়গায় নামিয়ে দেওয়া হয়। একে বলে “Heapify Down”।
• টাইম কমপ্লেক্সিটি: $O(\log n)$।

top() - রাজাকে দেখা

এটি শুধু বলে দেয় এই মুহূর্তে হিপের মাথায় কে বসে আছে। এটা কোনো কিছু পরিবর্তন করে না।

• টাইম কমপ্লেক্সিটি: $O(1)$ (কারণ রাজা সবসময় ইনডেক্স ০-তে বা Root-এ থাকে)।

কেন minHeap ব্যবহার করলাম? (The Strategy)

আমাদের লক্ষ্য হলো পুরো অ্যারের মধ্যে সেরা $k$ জন (Top $k$) বড় সংখ্যাকে খুঁজে বের করা।

• আমরা যখন একটি minHeap নিই যার সাইজ $k$, তখন এই হিপের ভেতরে সবসময় সবচেয়ে বড় $k$ টি সংখ্যা জমা থাকে।
• minHeap এর বৈশিষ্ট্য হলো সে সবচেয়ে ছোট সংখ্যাটাকে উপরে (top) রাখে।

maxHeap ব্যবহার করলে কী সমস্যা হতো?

তুমি যদি maxHeap ব্যবহার করো:

• সে সবসময় সবচেয়ে বড় সংখ্যাটাকে উপরে রাখবে।
• তুমি যখনই pop() করবে, সে সবচেয়ে বড় সংখ্যাটাই বের করে দেবে।
• তাহলে $k$-তম বড় সংখ্যাটি পেতে হলে তোমাকে পুরো অ্যারেটা হিপে ঢোকাতে হবে এবং $k-1$ বার বড় সংখ্যাগুলোকে ডিলিট করতে হবে।
• মেমোরি সমস্যা: এতে হিপের সাইজ হবে $n$ (পুরো অ্যারের সমান)। যদি ১ কোটি ডাটা থাকে, তবে ১ কোটি সাইজের হিপ লাগবে।

Constraints (সীমাবদ্ধতা)

1. 1 <= nums.length <= 10^5 এর মানে হলো অ্যারেতে কমপক্ষে ১টি সংখ্যা থাকবে এবং সর্বোচ্চ ১ লাখ ($10^5$) সংখ্যা থাকতে পারে।
   • গুরুত্ব: যদি তুমি $O(n^2)$ লজিক ব্যবহার করো (যেমন লুপের ভেতর লুপ), তবে $10^5 \times 10^5 = 10,000,000,000$ বার কাজ করতে হবে। কম্পিউটার ১ সেকেন্ডে সাধারণত $10^8$ বার কাজ করতে পারে। তাই $O(n^2)$ কোড চালালে Time Limit Exceeded (TLE) খাবে। তোমাকে এমন কোড লিখতে হবে যা $O(n)$ বা $O(n \log n)$ এ কাজ শেষ করে।
2. -2^31 <= nums[i] <= 2^31 - 1 এটি বলছে অ্যারের ভেতরে যে সংখ্যাগুলো থাকবে সেগুলোর মান কত বড় বা ছোট হতে পারে।
   • গুরুত্ব: 2^31 - 1 হলো একটি সি++ int ভেরিয়েবলের সর্বোচ্চ ধারণক্ষমতা। এর মানে হলো তুমি এই সংখ্যাগুলো রাখার জন্য সাধারণ int ব্যবহার করতে পারবে, তোমাকে long long নেওয়ার প্রয়োজন নেই। তবে যোগ-বিয়োগ করার সময় সাবধান থাকতে হবে যেন মানটি এর চেয়ে বড় না হয়ে যায়।
3. 0 <= k <= 10^5 এর মানে তোমাকে সর্বোচ্চ ১ লাখ বার রোটেট করতে বলা হতে পারে।
   • গুরুত্ব: আমি যে Modulo Trick ($k = k \% n$) এর কথা বলেছিলাম, সেটা এখানে খুব জরুরি। ধরো অ্যারের সাইজ ৫, কিন্তু তোমাকে বলা হলো ১ লাখ বার রোটেট করতে। তুমি যদি ১ লাখ বার লুপ চালাও, তবে সময় নষ্ট হবে। কিন্তু $100,000 \% 5 = 0$ করলে তুমি ১ সেকেন্ডেই বুঝে যাবে যে আসলে কিছুই করতে হবে না!