Untitled

/Back-end complete function Template for Java
class Solution {
    // Non-static method, so you need to call it on an instance of the class
    public void nearlySorted(int[] arr, int k) {
        int num = arr.length;

        // Implementing MinHeap using PriorityQueue and storing first k+1 elements in it
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add the first k+1 elements to the priority queue
        for (int i = 0; i <= k && i < num; i++) {
            pq.add(arr[i]);
        }

        int id = 0;

        // Process the remaining elements
        for (int i = k + 1; i < num; i++) {
            arr[id++] =
                pq.poll(); // Extract the minimum element and put it in the sorted array
            pq.add(arr[i]); // Add the current element to the priority queue
        }

        // Empty the priority queue
        while (!pq.isEmpty()) {
            arr[id++] = pq.poll(); // Extract the remaining elements
        }
    }
}