এই সমস্যায়, আমাদের n সংখ্যক পূর্ণসংখ্যা সম্বলিত একটি অ্যারে arr[] দেওয়া আছে। আমাদের কাজ হল অ্যারেতে নেক্সট স্মলার অফ নেক্সট গ্রেটার খুঁজে বের করা।
সমস্যা বর্ণনা - আমরা অ্যারেতে বর্তমান এলিমেন্ট থেকে বড় একটি এলিমেন্ট খুঁজব এবং তারপর সেই বড় এলিমেন্ট থেকে ছোট একটি এলিমেন্ট খুঁজব। এবং যদি নেক্সট স্মলার বা নেক্সট গ্রেটার এলিমেন্ট অ্যারেতে না থাকে তবে -১ রিটার্ন করব।
উদাহরণ
ইনপুট
arr[] = {4, 2, 8, 3, 9, 1}
আউটপুট
{3, 3, 1, 1, -1, -1}
ব্যাখ্যা
নেক্সট গ্রেটার এলিমেন্টের অ্যারে: {8, 8, 9, 9, -1, -1}। ৯ অ্যারেতে সবচেয়ে বড় এলিমেন্ট এবং ১ শেষ এলিমেন্ট, তাই তাদের নেক্সট গ্রেটার নেই।
নেক্সট স্মলার অফ নেক্সট গ্রেটার এলিমেন্টের অ্যারে: {3, 3, 1, 1, -1, -1}
সমাধানের পদ্ধতি
এই সমস্যার সহজ সমাধান হল অ্যারেটি ইটারেট করে প্রতিটি এলিমেন্টের জন্য:
- অ্যারেতে নেক্সট গ্রেটার এলিমেন্ট খুঁজুন।
- বাকি অ্যারেতে সেই গ্রেটার এলিমেন্ট থেকে ছোট এলিমেন্ট খুঁজুন।
এই সমাধান কাজ করে কিন্তু টাইম কমপ্লেক্সিটি O(n²)।
উন্নত সমাধান স্ট্যাক ও ইন্ডেক্স ব্যবহার করে করা যায়।
আমরা বর্তমান এলিমেন্টের নেক্সট গ্রেটার ও স্মলার এলিমেন্টের ইন্ডেক্স দুটি অ্যারে nextGreater[] ও nextSmaller[] এ স্টোর করব। এর মানে nextGreater[i] এ বর্তমান এলিমেন্টের নেক্সট গ্রেটার এলিমেন্টের ইন্ডেক্স থাকবে। nextSmaller[]-র জন্যও একই।
তবে নেক্সট গ্রেটার এলিমেন্টের নেক্সট স্মলার এলিমেন্ট অ্যাক্সেস করতে, আমরা nextGreater[i] ইন্ডেক্সের নেক্সট স্মলার এলিমেন্ট খুঁজব। এটি দিবে আমাদের প্রয়োজনীয় এলিমেন্টের ইন্ডেক্স, অর্থাৎ প্রয়োজনীয় এলিমেন্ট হল arr[nextSmaller[nextGreater[i]]]।
এলিমেন্ট বের করার জন্য স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করব যা বাকি সাবঅ্যারের এলিমেন্ট স্টোর করবে। গ্রেটার এলিমেন্ট বের করার ফাংশন 이렇게 কাজ করবে:
- অ্যারেটি শেষ থেকে ট্রাভার্স করুন (i = n-1 থেকে 0)।
- যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের টপ বর্তমান এলিমেন্ট থেকে ছোট বা সমান হয় → পপ করুন, যতক্ষণ না বড় এলিমেন্ট পাওয়া যায় বা স্ট্যাক খালি হয়।
- যদি স্ট্যাক খালি হয় → কোনো গ্রেটার এলিমেন্ট নেই, -১ স্টোর করুন।
- অন্যথায় → নেক্সট গ্রেটার এলিমেন্ট স্ট্যাকের টপে আছে, সেটি স্টোর করুন।
- বর্তমান এলিমেন্টকে স্ট্যাকে পুশ করুন।
একই পদ্ধতিতে নেক্সট স্মলার এলিমেন্ট বের করা যাবে। এবং দুটো ইন্ডেক্স পাওয়া যাওয়ার পর আমরা অ্যারেতে প্রয়োজনীয় এলিমেন্ট বের করতে পারব।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
stack<int> nextGreater;
int i = n - 1;
while (i >= 0) {
while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i])
nextGreater.pop();
if (!nextGreater.empty())
next[i] = nextGreater.top();
else
next[i] = -1;
nextGreater.push(i);
i--;
}
}
void findNextSmaller(int arr[], int n, int next[]) {
stack<int> nextSmaller;
int i = n - 1;
while (i >= 0) {
while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
nextSmaller.pop();
if (!nextSmaller.empty())
next[i] = nextSmaller.top();
else
next[i] = -1;
nextSmaller.push(i);
i--;
}
}
void findNextSmallerOfNextGreaterElementArray(int arr[], int n) {
int nextGreaterIndex[n];
int nextSmallerIndex[n];
findNextGreater(arr, n, nextGreaterIndex);
findNextSmaller(arr, n, nextSmallerIndex);
for (int i = 0; i < n; i++) {
if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
cout << arr[nextSmallerIndex[nextGreaterIndex[i]]] << "\t";
else
cout << "-1\t";
}
}
int main() {
int arr[] = {4, 2, 8, 3, 9, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "All next smaller of next greater elements of the array are ";
findNextSmallerOfNextGreaterElementArray(arr, n);
return 0;
}
আউটপুট
All next smaller of next greater elements of the array are 3 3 1 1 -1 -1
