- Arrays, Blogathon, Mathematical, subarray

Minimize operations to make all array elements -1 by changing maximums of K-size subarray to -1

Given an array arr[] consisting of N integers and an integer K, the task is to find the minimum of operations required to make all the array elements -1 such that in each operation, choose a subarray of size K and change all the maximum element in the subarray to -1.Examples:Input: arr[] = {18, 11, 18, 11, 18}, K = 3 Output: 3Explanation:Following are the operations performed:Choosing the sub array from index 0 to 2 and by applying the operation, modifies the array to {-1, 11, -1, 11, 18}.Choosing the sub array form index 1 to 3 and by applying the operation, modifies the array to {-1, -1, -1, -1, 18}.Choosing the sub array form index 2 to 4 and by applying the operation, modifies the array to {-1, -1, -1, -1, -1}.After the above operations all the array elements become -1. Therefore, the minimum number of operations required is 3.Input: arr[] = {2, 1, 1}, K = 2Output: 2Approach: The given problem can be solved by sorting the array arr[] with indices and then counting the number of operations by choosing the array elements from the end where the difference between the indices is less than K. Follow the below steps to solve the problem:Below is the implementation of the above approach:C++  #include using namespace std;  int minOperations(int arr[], int N, int K){              vector vp;    for (int i = 0; i < N; i++) {                          vp.push_back({ arr[i], i });    }              sort(vp.begin(), vp.end());              int minCnt = 0;          while (!vp.empty()) {        int val, ind;                  val = vp.back().first;                  ind = vp.back().second;                  minCnt++;                                          while (!vp.empty()               && vp.back().first == val               && ind - vp.back().second + 1