Minimum Operations to Make the Array K Increasing | Leetcode

This video explains about an interesrting interview problem based on optimal Longest Increasing Subsequence in O(NlogN) which is from leetcode 2111.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]
🟣 𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐚𝐥𝐥 𝐨𝐮𝐫 𝐂𝐨𝐮𝐫𝐬𝐞𝐬: techdose.co.in/
🔵 LinkedIn: / surya-pratap-kahar
🔴 INSTAGRAM: / techdose_official
🟢 𝐓𝐞𝐜𝐡𝐝𝐨𝐬𝐞-𝟏𝟎𝟎 𝐬𝐡𝐞𝐞𝐭: docs.google.co...
---------------------------------------------------------------------------------------------------------------------------------------------------------------
𝐋𝐈𝐒: gist.github.co...
𝐂𝐎𝐃𝐄 𝐋𝐈𝐍𝐊: gist.github.co...

[@deepaksingh7042]

We can optimise it to O(N) i think. Let me know if I am correct. Here is the approach. Intialise countChanges = 0 Now, for each of the k jump list we do the following - 1. Check if current element is greater than the next element in that list . If current is greater then replace its value with the previous element in that list and do countChanges++ , else do nothing. (NOTE: if previous element not present i.e. if we are at first element of that list then consider previous as zero) 2. Move forward to next element in same list. Repeat step 1 until that list is exhausted. After this step we get minimum no. of changes required for that list to make it non-decreasing. 3. Now start with the next k jump list and perform same operations mentioned in step-1 and step-2. For example, If given list is [1,2,3,4,5,6,7,8,9] , and k =3, then perform step-1 and step-2 for following lists - [1,4,7] [2,5,8] [3,6,9] Sum up all the countChanges for above sequences to get final answer