Day 21 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/nearly-sorted-1587115620/1

Nearly sorted

Difficulty: Medium Accuracy: 75.25%

Given an array arr[], where each element is at most k positions away from its correct position in the sorted order.
Your task is to restore the sorted order of arr[] by rearranging the elements in place.
Note: Don't use any sort() method.
Examples:
Input: arr[] = [2, 3, 1, 4], k = 2
Output: [1, 2, 3, 4]
Explanation: All elements are at most k = 2 positions away from their correct positions.
Element 1 moves from index 2 to 0
Element 2 moves from index 0 to 1
Element 3 moves from index 1 to 2
Element 4 stays at index 3
Input: arr[]= [7, 9, 14], k = 1
Output: [7, 9, 14]
Explanation: All elements are already stored in the sorted order.
Constraints:
1 ≤ arr.size() ≤ 106
0 ≤ k < arr.size()
1 ≤ arr[i] ≤ 106

Solution:
import heapq

class Solution:
def nearlySorted(self, arr, k):
heap = []
n = len(arr)
index = 0

    for i in range(k + 1):
        if i < n:
            heapq.heappush(heap, arr[i])

    for i in range(k + 1, n):
        arr[index] = heapq.heappop(heap)
        index += 1
        heapq.heappush(heap, arr[i])

    while heap:
        arr[index] = heapq.heappop(heap)
        index += 1

    return arr