41. First Missing Positive - Leetcode, Hard
সহজ প্রবলেম ডেসক্রিপশন,
N সাইজের একটা Array দেয়া আছে, সব গুলাই Integer এবং Positive/Negative সব ধরনের নাম্বার ই থাকতে পারে।
ঐ নাম্বার গুলা থেকে সব থেকে ছোটো এবং পজিটিভ যে নাম্বার টা মিসিং সেটা আমাদেরকে বের করতে হবে।
যেমন,
N = 5, Array[5] = {1, 2, 3, 4, 5}
এখানে মিসিং পজিজিটিভ এবং ছোটো নাম্বার টা হচ্ছে 6
আবার,
N = 5, Array[5] = {0, -10, 1, 3, -20}
এখানে মিসিং পজিটিভ এবং ছোটো নাম্বার টা হচ্ছে ২
প্রবলেম সলুশ্যন আইডিয়া খুবই সোজা, ইলিমেন্ট গুলাকে সর্ট করে অথবা সেটে রেখে মিসিং নাম্বার বের করা যেতে পারে খুব সহজেই। তাহলে এটা Hard ক্যাটাগরির প্রবলেম কেনো ?
আমাদেরকে এই প্রবলেম টা এক্সট্রা কোনো মেমোরি ইউজ না করে অর্থ্যাত O(1) এবং লিনিয়ার অর্থ্যাত O(N) এ সলভ করতে হবে।
আইডিয়াঃ
প্রথম কেইজ,
সব থেকে ছোটো মিসিং পজিটিভ নাম্বার কত হইতে পারে ? 1 (One), Right ?
হ্যা,
এখন পুরো এরেতে যদি ১(এক) না থাকে তাহলে ১ ই আমাদের কাঙ্ক্ষিত রেজাল্ট।
দ্বিতীয় কেইজ,
সহজ চিন্তা, ১ থেকে N এর মধ্যে যদি রেজাল্ট এক্সিস্ট না করে তাহলে রেজাল্ট অবশ্যই N+1, উপরের প্রথম উদাহরন টা।
এই কেইজের হিসাব আলাদা ভাবে করার দরকার নাই, বোঝার সুবিধার্থে বললাম।
তৃতীয় কেইজ,
আমাদের কাঙ্ক্ষিত রেজাল্ট সবসময় ১ থেকে N এর মধ্যে এক্সিস্ট করবে একটু চিন্তা করলেই বোঝা যাবে। অর্থ্যাত যেকোনো নেগেটিভ নাম্বার এবং N এর থেকে বড় নাম্বার গুলা কে আমরা ইগ্নোর করবো।
ইগ্নোর ব্যাপার টা আরেকটু ভালোভাবে বলি,
উপরের দ্বিতীয় উদাহরন টা খেয়াল করি,
Index = 0 1 2 3 4
Array[5] = {0, -10, 1, 3, -20}
এখানে মিসিং পজিটিভ নাম্বার ২, যে নাম্বার গুলা আমাদের দরকার নাই অর্থ্যাৎ নেগেটিভ এবং N এর থেকে বড় ঐ নাম্বার গুলাকে আমরা 1 দিয়ে Replace করে দিবো।
আর হ্যা, Zero কেও 1 দ্বারা রিপ্লেস করে দিবো।
তাহলে এখন Array টা দাঁড়ায়,
Array[5] = {1, 1, 1, 3, 1}
খেয়াল করলে দেখা যাবে এই Array তে ১ থেকে N এর বাইরে কোনো নাম্বার নাই, কারন আমরা আগেই বলছিলাম আমাদের রেজাল্ট ১ থেকে N এর মধ্যে এক্সিস্ট করবে, আর আমরা সেভাবেই আগাচ্ছি।
এখন এই Array তে ছোটো একটা Operation করবো,
বর্তমান পজিশন যদি i হয়, তাহলে
Index = Array[i] - 1; // এটা দিয়ে আমরা একটা আমরা নতুন একটা Index বানাইলাম, মাইনাস ১ করলাম কারন, আমাদের Array 0 based.
এখন Array[Index] এ যেই ভ্যালু আছে , সেটা যদি পজিটিভ হয় তাহলে সেটাকে নেগেটিভ করে দিবো, আর যদি আগেই নেগেটিভ করা থাকে তাহলে ইগ্নোর করবো ।
এইভাবে সব গুলা ভ্যালুকে এইভাবে মডিফিকেশন করার পর , প্রথম যে Index এর ভ্যলু পজিটিভ পাবো, সেই Index+1 ই হবে আমাদের কাঙ্ক্ষিত রেজাল্ট।
Lets Modify,
Index = 0 1 2 3 4
Array[5] = {1, 1, 1, 3, 1}
i = 0,
Index = Array[0] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, 1, 3, 1}
i = 1,
Index = Array[1] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 // already -1 , no need to change
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, 1, 3, 1}
i = 2,
Index = Array[2] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 // already -1 , no need to change
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, 1, 3, 1}
i = 2,
Index = Array[2] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 // already -1 , no need to change
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, 1, 3, 1}
i = 3,
Index = Array[3] - 1 = 3-1 = 2
Array[Index] = Array[2] = -1
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, -1, 3, 1}
i = 4,
Index = Array[4] - 1 = 1-1 = 0
Array[Index] = Array[0] = -1 // already -1 , no need to change
New Array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, -1, 3, 1}
So, we got our final Modify array,
Index = 0 1 2 3 4
Array[5] = {-1, 1, -1, 3, 1}
এখানে প্রথম থেকে ১ নাম্বার Index এর ভ্যালু পজিটিভ, তাহলে ১+১ = ২ আমাদের মিসিং পজিটিভ নাম্বার।
এখনোও বুঝতে না পারলে কোড
