C++ में सरणी को सख्ती से बढ़ता हुआ बनाना (Make Array Strictly Increasing)

समस्या विवरण

दो सरणियाँ arr1 और arr2 दी गई हैं। हम arr1[i] = arr2[j] असाइनमेंट कर सकते हैं। arr1 को सख्ती से बढ़ता हुआ (strictly increasing) बनाने के लिए न्यूनतम ऑपरेशन्स (operations) ज्ञात करने हैं। यदि असंभव है तो -1 लौटाएं।

उदाहरण

इनपुट

arr1 = [1,5,3,7,8], arr2 = [1,3,2,5]

आउटपुट

व्याख्या: 5 को 2 से बदलें → [1,2,3,7,8]

समाधान दृष्टिकोण (DP + बाइनरी सर्च)

arr2 को क्रमबद्ध करें और डुप्लिकेट हटाएं।
DP स्थिति: dp[i][j] = सूचकांक i से शुरू करके, arr2 में सूचकांक ≥ j से मान लेकर, पिछला मान prev दिए जाने पर, न्यूनतम ऑपरेशन्स।
प्रत्येक स्थिति पर दो विकल्प:
- arr1[i] रखें (यदि prev < arr1[i])
- arr2 से अगला वैध मान लें (upper_bound का उपयोग करके)
मेमोइजेशन के साथ पुनरावर्ती हल करें।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector& arr1, vector& arr2, int i, int j, int prev, 
              vector>& dp) {
        if (i >= arr1.size()) return 0;
        j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
        if (dp[i][j] != -1) return dp[i][j];
        
        int ret = arr2.size() + 1; // अनंत
        if (prev < arr1[i]) {
            ret = min(ret, solve(arr1, arr2, i+1, j, arr1[i], dp));
        }
        if (j < arr2.size()) {
            ret = min(ret, 1 + solve(arr1, arr2, i+1, j, arr2[j], dp));
        }
        return dp[i][j] = ret;
    }
    
    int makeArrayIncreasing(vector& arr1, vector& arr2) {
        sort(arr2.begin(), arr2.end());
        arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
        int n = arr1.size(), m = arr2.size();
        vector> dp(n+1, vector(m+1, -1));
        int ans = solve(arr1, arr2, 0, 0, INT_MIN, dp);
        return ans > m ? -1 : ans;
    }
};

int main() {
    Solution ob;
    vector v1 = {1,5,3,7,8}, v2 = {1,3,2,5};
    cout << ob.makeArrayIncreasing(v1, v2);
    return 0;
}