Minimum Operations To Make The Array K - Increasing, C++ Explained Solution
Do Upvote If Found Helpful !!!\n\n# Approach\n Describe your approach to solving the problem. \nThe problem here is quite interesting and requires a bit of an o
**Do Upvote If Found Helpful !!!**\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem here is quite interesting and requires a bit of an observation. Basically for each set of numbers present at a distance of **K**, we need to find minimum operations to make that set of numbers a non-decreasing sequence. This hints at finding the **length of the longest non-decreasing subsequence** for each set of numbers, as these are the numbers already present in sorted order and we only need to change **len(seq) - LNDS** amount of numbers in sequence where **LNDS stands for Longest Non Decreasing Subsequence**. This can be easily done with dynamic programming but the basic DP approach would result in quadratic time. An optimised way of finding the **LNDS** brings down the overall time complexity and our solution easily passes.\n\n# Complexity\n- Time complexity: **O(NlogN)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(N)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        ios_base::sync_with_stdio(0);\n        int n = arr.size(),ans = 0; vector<bool>visited(n,false);\n        for(int i = 0; i < n; i++){\n            if(!visited[i]){\n                int j = i,c = 0; multiset<int>st;\n                while(j < n){    // Finding all numbers in sequence, marking them visited and finding LNDS. A special note that for LIS, use lower bound.\n                    c++;\n                    st.insert(arr[j]);  \n                    auto e = st.upper_bound(arr[j]);\n                    if(e != st.end()){\n                        st.erase(e);\n                    }\n                    visited[j] = true;\n                    j += k;\n                }\n                ans += c - st.size();\n            }\n        }\n        return ans;\n    }\n};\n```
['Math', 'Dynamic Programming', 'C++']