First Missing Positive Number

 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 এর ভ্যালু পজিটিভ, তাহলে ১+১ = ২ আমাদের মিসিং পজিটিভ নাম্বার।

এখনোও বুঝতে না পারলে কোড