ধরুন n সংখ্যক পূর্ণসংখ্যার একটি সিকোয়েন্স আছে a1, a2, ..., an। একটি ১৩২ প্যাটার্ন হলো একটি সাবসিকোয়েন্স ai, aj, ak যাতে i < j < k এবং ai < ak < aj। আমাদের একটি অ্যালগরিদম ডিজাইন করতে হবে যা n সংখ্যার একটি লিস্ট ইনপুট নেবে এবং চেক করবে তাতে ১৩২ প্যাটার্ন আছে কিনা। উদাহরণস্বরূপ, ইনপুট [-1, 3, 2, 0] হলে আউটপুট হবে true, কারণ তিনটি প্যাটার্ন আছে: [-1, 3, 2], [-1, 3, 0] এবং [-1, 2, 0]।
সমাধানের ধাপগুলো:
n := nums-এর সাইজ, যদি n 0 হয় তবে false রিটার্ন করুন
সাইজ n-এর একটি minVals অ্যারে ডিফাইন করুন, minVals[0] := nums[0] সেট করুন
i = 1 থেকে n – 1 পর্যন্ত লুপ চালান
minVals[i] := min(minVals[i - 1], nums[i])
একটি স্ট্যাক st তৈরি করুন
i = n – 1 থেকে ১ পর্যন্ত ডাউনওয়ার্ড লুপ চালান
minVal := minVals[i – 1]
curr := nums[j]
যখন st খালি নয় এবং st-এর টপ <= minVal
st থেকে ডিলিট করুন
যদি st খালি নয় এবং st-এর টপ < curr হয়, তবে true রিটার্ন করুন
nums[i] st-এ ইনসার্ট করুন
false রিটার্ন করুন
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: bool find132pattern(vector<int>& nums) { int n = nums.size(); if(!n) return false; vector <int> minVals(n); minVals[0] = nums[0]; for(int i = 1; i < n; i++){ minVals[i] = min(minVals[i - 1], nums[i]); } stack <int> s; for(int i = n - 1; i > 0; i--){ int minVal = minVals[i - 1]; int curr = nums[i]; while(!s.empty() && s.top() <= minVal) s.pop(); if(!s.empty() && s.top() < curr) return true; s.push(nums[i]); } return false; } }; main(){ vector<int> v = {-1,3,2,0}; Solution ob; cout << (ob.find132pattern(v)); }
ইনপুট
[-1,3,2,0]
আউটপুট
1
