সর্ববৃহৎ শূন্য সাবম্যাট্রিক্স খোঁজা#

আপনাকে n সারি ও m কলামবিশিষ্ট একটি ম্যাট্রিক্স দেওয়া আছে। শুধুমাত্র শূন্য দিয়ে গঠিত সর্ববৃহৎ সাবম্যাট্রিক্স খুঁজুন (সাবম্যাট্রিক্স হলো ম্যাট্রিক্সের একটি আয়তক্ষেত্রাকার অংশ)।

অ্যালগরিদম#

ম্যাট্রিক্সের উপাদানগুলো হবে a[i][j], যেখানে i = 0...n - 1, j = 0... m - 1। সরলতার জন্য, আমরা সব অশূন্য উপাদানকে ১ হিসেবে বিবেচনা করব।

ধাপ ১: সহায়ক ডায়নামিক#

প্রথমে, আমরা নিম্নলিখিত সহায়ক ম্যাট্রিক্স হিসাব করি: d[i][j], a[i][j]-র উপরে নিকটতম সেই সারি যেখানে ১ আছে। আনুষ্ঠানিকভাবে বলতে গেলে, d[i][j] হলো সর্ববৃহৎ সারি নম্বর (0 থেকে i - 1 পর্যন্ত), যেখানে j-তম কলামে ১ সমান কোনো উপাদান আছে। উপরে-বাম থেকে নিচে-ডানে ইটারেট করার সময়, যখন আমরা i সারিতে থাকি, আমরা পূর্ববর্তী সারির মানগুলো জানি, তাই শুধু ১ মানবিশিষ্ট উপাদানগুলো আপডেট করাই যথেষ্ট। আমরা মানগুলো একটি সাধারণ অ্যারে d[i], i = 1...m - 1-এ সংরক্ষণ করতে পারি, কারণ পরবর্তী অ্যালগরিদমে আমরা ম্যাট্রিক্স একবারে একটি সারি করে প্রসেস করব এবং শুধু বর্তমান সারির মান প্রয়োজন।

vector<int> d(m, -1);
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        if (a[i][j] == 1) {
            d[j] = i;
        }
    }
}

ধাপ ২: সমস্যার সমাধান#

আমরা সারিগুলোর মধ্য দিয়ে ইটারেট করে, সাবম্যাট্রিক্সের সম্ভাব্য প্রতিটি বাম ও ডান কলাম বিবেচনা করে $O(n m^2)$-এ সমস্যাটি সমাধান করতে পারি। আয়তক্ষেত্রের নিচের দিক হবে বর্তমান সারি, এবং d[i][j] ব্যবহার করে আমরা উপরের সারি খুঁজতে পারি। তবে, আরো এগিয়ে গিয়ে সমাধানের কমপ্লেক্সিটি উল্লেখযোগ্যভাবে উন্নত করা সম্ভব।

এটা স্পষ্ট যে কাঙ্ক্ষিত শূন্য সাবম্যাট্রিক্স চারদিক থেকে কিছু ১ দ্বারা আবদ্ধ, যা এটিকে আকারে বাড়তে এবং উত্তর উন্নত করতে বাধা দেয়। সুতরাং, আমরা নিম্নলিখিতভাবে কাজ করলে উত্তর মিস করব না: i সারির প্রতিটি ঘর j-র জন্য (সম্ভাব্য শূন্য সাবম্যাট্রিক্সের নিচের সারি) আমরা d[i][j]-কে বর্তমান শূন্য সাবম্যাট্রিক্সের উপরের সারি হিসেবে নেব। এখন শূন্য সাবম্যাট্রিক্সের সর্বোত্তম বাম ও ডান সীমানা নির্ধারণ করা বাকি, অর্থাৎ j-তম কলাম থেকে এই সাবম্যাট্রিক্সকে সর্বাধিক বাম ও ডানে প্রসারিত করা।

সর্বাধিক বামে প্রসারিত করার অর্থ কী? এর অর্থ হলো এমন একটি ইনডেক্স k1 খুঁজে বের করা যার জন্য d[i][k1] > d[i][j], এবং একই সাথে k1 ইনডেক্স j-র বামে সবচেয়ে কাছে। এটা স্পষ্ট যে তাহলে k1 + 1 হবে প্রয়োজনীয় শূন্য সাবম্যাট্রিক্সের বাম কলাম নম্বর। যদি এমন কোনো ইনডেক্স না থাকে, তাহলে k1 = -1 রাখুন (এর অর্থ আমরা বর্তমান শূন্য সাবম্যাট্রিক্সকে ম্যাট্রিক্স a-র বাম সীমানা পর্যন্ত প্রসারিত করতে পেরেছি)।

একইভাবে, ডান সীমানার জন্য একটি ইনডেক্স k2 নির্ধারণ করা যায়: এটি j-র ডানে সবচেয়ে কাছের ইনডেক্স যেখানে d[i][k2] > d[i][j] (অথবা m, যদি এমন কোনো ইনডেক্স না থাকে)।

সুতরাং, ইনডেক্স k1 এবং k2, যদি আমরা এগুলো কার্যকরভাবে খুঁজতে শিখি, বর্তমান শূন্য সাবম্যাট্রিক্স সম্পর্কে সমস্ত প্রয়োজনীয় তথ্য দেবে। বিশেষ করে, এর ক্ষেত্রফল হবে (i - d[i][j]) * (k2 - k1 - 1)।

নির্দিষ্ট i এবং j-র জন্য এই ইনডেক্সগুলো কীভাবে কার্যকরভাবে খুঁজবেন? আমরা গড়ে $O(1)$-এ এটি করতে পারি।

এই কমপ্লেক্সিটি অর্জন করতে, নিম্নলিখিতভাবে স্ট্যাক ব্যবহার করা যায়। প্রথমে ইনডেক্স k1 কীভাবে খুঁজতে হয় শিখি, এবং বর্তমান সারি i-তে ম্যাট্রিক্স d-তে প্রতিটি ইনডেক্স j-র জন্য এর মান d1[i][j]-এ সংরক্ষণ করি। এটি করতে, আমরা বাম থেকে ডানে সব কলাম j দেখব, এবং স্ট্যাকে শুধু সেই কলামগুলো রাখব যাদের d[][] কঠোরভাবে d[i][j]-র চেয়ে বেশি। স্পষ্টতই কলাম j থেকে পরবর্তী কলামে যাওয়ার সময়, স্ট্যাকের বিষয়বস্তু আপডেট করা প্রয়োজন। যখন স্ট্যাকের শীর্ষে অনুপযুক্ত উপাদান থাকে (অর্থাৎ d[][] <= d[i][j]) তখন এটি পপ করুন। বোঝা সহজ যে স্ট্যাক থেকে শুধু এর শীর্ষ থেকে অপসারণ করাই যথেষ্ট, অন্য কোনো স্থান থেকে নয় (কারণ স্ট্যাকে কলামগুলোর একটি ক্রমবর্ধমান d ক্রম থাকবে)।

প্রতিটি j-র জন্য d1[i][j]-র মান হবে সেই মুহূর্তে স্ট্যাকের শীর্ষে থাকা মান।

ইনডেক্স k2 খোঁজার জন্য ডায়নামিক্স d2[i][j] একইভাবে বিবেচনা করা হয়, শুধু কলামগুলো ডান থেকে বামে দেখতে হবে।

এটা স্পষ্ট যে প্রতিটি সারিতে স্ট্যাকে ঠিক mটি উপাদান যোগ হয়, তাই মোছাও এর বেশি হতে পারে না, কমপ্লেক্সিটির যোগফল লিনিয়ার হবে, তাই অ্যালগরিদমের চূড়ান্ত কমপ্লেক্সিটি $O(nm)$।

এটাও উল্লেখ করা উচিত যে এই অ্যালগরিদম $O(m)$ মেমোরি ব্যবহার করে (ইনপুট ডেটা — ম্যাট্রিক্স a[][] — বাদ দিয়ে)।

ইমপ্লিমেন্টেশন#

int zero_matrix(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();

    int ans = 0;
    vector<int> d(m, -1), d1(m), d2(m);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1)
                d[j] = i;
        }

        for (int j = 0; j < m; ++j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d1[j] = st.empty() ? -1 : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d2[j] = st.empty() ? m : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = 0; j < m; ++j)
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}