সার্কুলার অ্যারে
যে অ্যারেতে শেষ এলিমেন্টের পরের এলিমেন্ট হলো প্রথম এলিমেন্ট, তাকে সার্কুলার অ্যারে বলে। বাস্তবে ডেটা কনটiguous মেমোরিতে থাকে, সার্কুলার অ্যারে বেশি একটি কনসেপ্ট।
সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি সার্কুলার ইন্টিজার অ্যারে arr একমাত্র আর্গুমেন্ট হিসেবে নেবে। ফাংশনটি একটি অ্যারে কনস্ট্রাক্ট করে রিটার্ন করবে যেটিতে মূল অ্যারের প্রতিটি উপাদানের জন্য এর পরের বড় এলিমেন্ট (Next Greater Element) থাকবে। সার্কুলার সার্চ করলে বড় এলিমেন্ট পাওয়া যেতে পারে। না পেলে -1 দিয়ে থাকবে।
উদাহরণ:
const arr = [7, 8, 7];
আউটপুট হবে:
const output = [8, -1, 8];
আউটপুট ব্যাখ্যা
দুইটি ৭-এর জন্য নেক্সট গ্রেটার ৮, কিন্তু ৮-এর জন্য কোনো বড় এলিমেন্ট নেই, তাই -1।
উদাহরণ
কোডটি নিচের মতো (মনোটোনিক স্ট্যাক):
const arr = [7, 8, 7]; const nextGreaterElement = (arr = []) => { const res = []; const stack = []; if (!arr || arr.length < 1){ return res; }; for (let i = 0; i < arr.length; i++) { while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) { const small = stack.pop(); res[small] = arr[i]; }; stack.push(i); } for (let i = 0; i < arr.length; i++) { while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) { const small = stack.pop(); res[small] = arr[i]; }; } const rem = stack.length; for (let i = 0; i < rem; i++) { res[stack.pop()] = -1; } return res; }; console.log(nextGreaterElement(arr)); কোড ব্যাখ্যা:
ইটারেশন সময় স্ট্যাকে থাকা এলিমেন্ট চেয়ে বড় এলিমেন্ট পাওয়া গেলে রেজাল্ট আপডেট করা হয়। দ্বিতীয় পাসে সার্কুলার সার্চ করা হয়। অবশেষে স্ট্যাকে থাকা এলিমেন্টগুলোকে -1 দিয়ে ফিল করা হয়।
আউটপুট
কনসোলে আউটপুট:
[8, -1, 8]
