Java + Intuition + LIS + Binary Search
Intuition:\nThe intuition behind this solution is that we extract all k-separated subsequences and find out the longest increasing subsequence (LIS) for each k-
**Intuition:**\nThe intuition behind this solution is that we extract all k-separated subsequences and find out the longest increasing subsequence (LIS) for each k-separated subsequences and then for each of these extracted subsequences we calculate the min operations (delete/update) to make it sorted/increasing.\n\n```\nMin operations to make it increasing = Length of extracted subsequence - LIS of the extracted subsequence\n```\n\nWe add the min operations for each of the k-separated subsequences which should give us the answer for the original problem.\n\nLet\'s take an example to understand better -\n\n```\narr = [4,1,5,2,6,2,8,9,11,15]\n       1     1     1      1\n         2     2     2\n           3     3     3 \nk=3\n\nk-seperated subsequences of arr:\n#   subsequence      length     LIS      Operations(length - LIS)\n1   [4,2,8,15]          4        3           1\n2   [1,6,9]             3        3           0\n3   [5,2,11]            3        2           1\n--------------------------------------------------\nTotal Operations =                           2\n-------------------------------------------------\n```\n\n**Code:**\n\n```\nclass Solution {\n  public int kIncreasing(int[] arr, int k) {\n    int total = 0;\n    for(int i=0; i < k; i++){\n      List<Integer> list = new ArrayList<>();\n      for(int j=i; j < arr.length; j = j+k)\n        list.add(arr[j]);\n      total += list.size() - lengthOfLIS(list);\n    }\n    return total;\n  }\n  \n  // Get the length of LIS by building an increasing List so as to perform binary search on it \n  // in case the current element is lesser than the last element in the increasing List. \n  // In such case we get the next greater element from the increasing List by doing a binary Search and \n  // replace that with the the current element in the increasing List, as the other element is no longer relevant in participating in LIS. \n  // The increasing List remains sorted and always maintain the max length of the increasing subsequence.\n  public int lengthOfLIS(List<Integer> nums){\n    List<Integer> incrList = new ArrayList<>();\n    incrList.add(nums.get(0));\n\n    for(int i=1; i < nums.size(); i++){\n      int lastItem = incrList.get(incrList.size()-1);\n      if(nums.get(i) >= lastItem){\n        incrList.add(nums.get(i));\n      } else {\n        int idx = nextGreaterItem(incrList, nums.get(i));\n        incrList.set(idx, nums.get(i));\n      }\n    }\n    return incrList.size();\n  }\n\n  // Perform Binary Search to get the next greater element\n  int nextGreaterItem(List<Integer> list, int num){\n    int left = 0, right = list.size()-1;\n    while(left < right) {\n      int mid = left + (right - left) / 2;\n      if(num >= list.get(mid))\n        left = mid + 1;\n      else\n        right = mid;\n    }\n    return left;\n  }\n}\n```
['Binary Tree', 'Java']