Given an array of n elements, where each element is at most k away from its target position, you need to sort the array optimally.
Example 1:
Input:
n = 7, k = 3
arr[] = {6,5,3,2,8,10,9}
Output: 2 3 5 6 8 9 10
Explanation: The sorted array will be
2 3 5 6 8 9 10
Example 2:
Input:
n = 5, k = 2
arr[] = {3,1,4,2,5}
Output: 1 2 3 4 5 
Note: DO NOT use STL sort() function for this question.
Your Task:
You are required to complete the method nearlySorted() which takes 3 arguments and returns the sorted array.
Expected Time Complexity : O(nlogk)
Expected Auxilliary Space : O(n)
Constraints:
1 ≤ n ≤ 10^{6}
1 ≤ k < n
1 ≤ arr_{i }≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    

    #Function to return the sorted array.

    def nearlySorted(self,a,n,k):

        

        # code here

Solutions:
from heapq import *

class Solution:

	def nearlySorted(self, arr, n, k):
		heap = []
		for i in range(k):
			heappush(heap, arr[i])
		ans = []
		for i in range(k, n):
			heappush(heap, arr[i])
			ans.append(heappop(heap))
		while heap != []:
			ans.append(heappop(heap))
		return ans


from heapq import *

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		ans = []
		for ele in a:
			if len(heap) < k:
				heappush(heap, ele)
			else:
				top = heap[0]
				if ele < top:
					ans.append(ele)
				else:
					ans.append(heappop(heap))
					heappush(heap, ele)
		for i in range(k):
			ans.append(heappop(heap))
		return ans


class Solution:

	def nearlySorted(self, a, n, k):
		a.sort()
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		hq = []
		for i in range(k + 1):
			heapq.heappush(hq, a[i])
		res = []
		j = k + 1
		while hq:
			out = heapq.heappop(hq)
			res.append(out)
			if j < n:
				heapq.heappush(hq, a[j])
			j += 1
		return res


class Solution:

	def nearlySorted(self, a, n, k):
		arr = a[:k + 1]
		heapq.heapify(arr)
		index = k + 1
		i = 0
		while len(arr):
			a[i] = heapq.heappop(arr)
			if index < len(a):
				heapq.heappush(arr, a[index])
				index += 1
			i += 1
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		arr = a[:k + 1]
		heapq.heapify(arr)
		final = list()
		index = k + 1
		while len(arr):
			final.append(heapq.heappop(arr))
			if index < len(a):
				heapq.heappush(arr, a[index])
				index += 1
		return final


from queue import PriorityQueue

class Solution:

	def nearlySorted(self, a, n, k):
		a.sort()
		return a


from heapq import heappop, heappush, heapify

class Solution:

	def nearlySorted(self, a, n, k):
		win = a[:k]
		heapify(win)
		for i in range(n):
			if i + k < n:
				heappush(win, a[i + k])
			a[i] = heappop(win)
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		a.sort()
		p = a.copy()
		return p


class Solution:

	def nearlySorted(self, a, n, k):
		l = []
		for i in range(n):
			l.append(a[i])
		l.sort()
		return l


import heapq as h

class Solution:

	def nearlySorted(self, arr, n, k):
		(mylist, res) = ([], [])
		heapq.heapify(mylist)
		for i in range(n):
			heapq.heappush(mylist, arr[i])
			if len(mylist) > k:
				res.append(heapq.heappop(mylist))
		while len(mylist) > 0:
			res.append(heapq.heappop(mylist))
		return res


from heapq import *

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		curr = 0
		for i in a:
			heappush(heap, i)
		while heap:
			a[curr] = heappop(heap)
			curr += 1
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		return sorted(a)


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		ans = []
		temp = []
		for i in range(n):
			heapq.heappush(temp, a[i])
			if len(temp) > k:
				ans.append(heapq.heappop(temp))
		while len(temp):
			ans.append(heapq.heappop(temp))
		return ans


from heapq import heapify, heappop, heappush

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		heapify(heap)
		res = []
		for i in range(n):
			heappush(heap, a[i])
			if len(heap) == k + 1:
				res.append(heappop(heap))
		while len(heap):
			res.append(heappop(heap))
		return res


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		minheap = []
		heapq.heapify(minheap)
		ans = []
		for i in a:
			heapq.heappush(minheap, i)
			if len(minheap) > k:
				ans.append(heapq.heappop(minheap))
		while len(minheap) > 0:
			ans.append(heapq.heappop(minheap))
		return ans


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		minh = []
		ans = []
		heapq.heapify(minh)
		for i in a:
			heapq.heappush(minh, i)
			if len(minh) > k:
				x = heapq.heappop(minh)
				ans.append(x)
		while minh:
			ans.append(heapq.heappop(minh))
		return ans


import heapq as hq

class Solution:

	def nearlySorted(self, a, n, k):
		heap = [i for i in a]
		hq.heapify(heap)
		i = 0
		while heap:
			a[i] = hq.heappop(heap)
			i += 1
		return a


from heapq import heapify, heappush, heappop

class Solution:

	def nearlySorted(self, a, n, k):
		h = []
		heapify(h)
		ans = []
		for el in a:
			heappush(h, el)
			if len(h) > k:
				ans.append(heappop(h))
		while h:
			ans.append(heappop(h))
		return ans


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		mylist = []
		heapq.heapify(a)
		for i in range(n):
			mylist.append(heapq.heappop(a))
		return mylist


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		for i in range(k + 1):
			heapq.heappush(heap, a[i])
		i = 0
		k += 1
		while i < n:
			if k < n:
				a[i] = heap[0]
				i += 1
				heapq.heappush(heap, a[k])
				k += 1
				heapq.heappop(heap)
			else:
				a[i] = heap[0]
				i += 1
				heapq.heappop(heap)
		return a


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		h = []
		ans = []
		for i in range(k + 1):
			heapq.heappush(h, a[i])
		j = k + 1
		while len(ans) != n:
			ans.append(h[0])
			heapq.heappop(h)
			if j < n:
				heapq.heappush(h, a[j])
				j += 1
		return ans


class Solution:

	def nearlySorted(self, a, n, k):
		h = []
		l = []
		for i in range(0, k):
			heapq.heappush(h, a[i])
		for j in range(k, len(a)):
			l.append(heapq.heappushpop(h, a[j]))
		while h:
			l.append(heapq.heappop(h))
		return l


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		hp = [a[0]]
		heapq.heapify(hp)
		l = 0
		for i in range(1, n):
			if len(hp) < k + 1:
				heapq.heappush(hp, a[i])
			elif len(hp) == k + 1:
				a[l] = heapq.heapreplace(hp, a[i])
				l += 1
		while hp:
			a[l] = heapq.heappop(hp)
			l += 1
		return a


import heapq
from heapq import heappop, heappush, heapify

class Solution:

	def nearlySorted(self, arr, n, k):
		heap = arr[:k + 1]
		heapify(heap)
		target_index = 0
		for rem_elmnts_index in range(k + 1, n):
			arr[target_index] = heappop(heap)
			heappush(heap, arr[rem_elmnts_index])
			target_index += 1
		while heap:
			arr[target_index] = heappop(heap)
			target_index += 1
		return arr


from heapq import heapify, heappush, heappop

class Solution:

	def nearlySorted(self, arr, n, k):
		res = arr[:k + 1]
		heapify(res)
		j = k
		result = []
		for i in range(n):
			if j + 1 < n:
				result.append(heappop(res))
				j += 1
				heappush(res, arr[j])
			else:
				result.append(heappop(res))
		return result


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		h = []
		res = []
		k += 1
		for i in range(k):
			heapq.heappush(h, a[i])
		for i in range(k, n):
			res.append(heapq.heappop(h))
			heapq.heappush(h, a[i])
		while h:
			res.append(heapq.heappop(h))
		return res


class Solution:

	def nearlySorted(self, arr, n, k):
		heap = []
		for i in range(k):
			heapq.heappush(heap, arr[i])
		for i in range(k, len(arr)):
			heapq.heappush(heap, arr[i])
			arr[i - k] = heapq.heappop(heap)
		for i in range(len(arr) - k, len(arr)):
			arr[i] = heapq.heappop(heap)
		return arr


class Solution:

	def nearlySorted(self, A, n, k):
		if not A:
			return A
		n = len(A)
		(h, ans, start) = ([], [0] * n, 0)
		for i in range(n):
			if i < k:
				heapq.heappush(h, A[i])
			else:
				if h and h[0] < A[i]:
					ans[start] = heapq.heappop(h)
					start += 1
				heapq.heappush(h, A[i])
		while h:
			ans[start] = heapq.heappop(h)
			start += 1
		return ans


from heapq import *

class Solution:

	def nearlySorted(self, arr, n, k):
		heap = []
		ans = []
		for elm in arr:
			if len(heap) < k:
				heappush(heap, elm)
			elif elm <= heap[0]:
				ans.append(elm)
			else:
				ans.append(heappop(heap))
				heappush(heap, elm)
		for i in range(k):
			ans.append(heappop(heap))
		return ans


import bisect

class Solution:

	def nearlySorted(self, a, n, k):
		a.sort()
		return a


class Solution:

	def nearlySorted(self, arr, n, k):
		arr.sort()
		return arr


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		arr = []
		heapq.heapify(heap)
		for i in range(len(a)):
			heapq.heappush(heap, a[i])
			while len(heap) > k:
				arr.append(heapq.heappop(heap))
		while len(heap):
			arr.append(heapq.heappop(heap))
		return arr


class Solution:

	def nearlySorted(self, a, n, k):
		arr_ = []
		l_ = 0
		ans = []
		for i in a:
			heapq.heappush(arr_, i)
			l_ += 1
			if l_ > k:
				ans.append(heapq.heappop(arr_))
				l_ -= 1
		for i in range(l_):
			ans.append(heapq.heappop(arr_))
		return ans


class Solution:

	def nearlySorted(self, a, n, k):
		res = []
		heapq.heapify(a)
		while len(a) > 0:
			r = heapq.heappop(a)
			res.append(r)
		return res


class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		res = []
		for ele in a:
			heapq.heappush(heap, ele)
			if len(heap) > k:
				res.append(heapq.heappop(heap))
		while len(heap):
			res.append(heapq.heappop(heap))
		return res


class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		result = []
		for i in a:
			heapq.heappush(heap, i)
			if len(heap) > k:
				result.append(heapq.heappop(heap))
		while heap:
			result.append(heapq.heappop(heap))
		return result


class Solution:

	def nearlySorted(self, a, n, k):
		res = []
		heep = []
		for i in range(n):
			heapq.heappush(heep, a[i])
			if len(heep) > k:
				res.append(heapq.heappop(heep))
		while heep:
			res.append(heapq.heappop(heep))
		return res


import collections

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		res = []
		for i in a:
			heapq.heappush(heap, i)
			if len(heap) > k:
				res.append(heapq.heappop(heap))
		while len(heap) != 0:
			res.append(heapq.heappop(heap))
		return res


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		(myList, res) = ([], [])
		heapq.heapify(myList)
		for i in range(n):
			heapq.heappush(myList, a[i])
			if len(myList) > k:
				res.append(heapq.heappop(myList))
		while len(myList) > 0:
			res.append(heapq.heappop(myList))
		return res


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		res = []
		kq = []
		for i in range(n):
			if i < k:
				heapq.heappush(kq, a[i])
			if i == k:
				heapq.heappush(kq, a[i])
				res.append(heapq.heappop(kq))
			if i > k:
				heapq.heappush(kq, a[i])
				res.append(heapq.heappop(kq))
			while kq:
				res.append(heapq.heappop(kq))
		return sorted(res)


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		l = []
		size = 0
		for i in range(k):
			heapq.heappush(l, a[i])
			size = size + 1
		index = 0
		for j in range(k, n):
			heapq.heappush(l, a[j])
			size = size + 1
			if size > k:
				a[index] = heapq.heappop(l)
				size = size - 1
				index = index + 1
		while l:
			a[index] = heapq.heappop(l)
			index = index + 1
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		heap = a[:k + 1]
		heapq.heapify(heap)
		for i in range(k + 1, n):
			a[i - k - 1] = heapq.heappushpop(heap, a[i])
		for i in range(n - k - 1, n):
			a[i] = heapq.heappop(heap)
		return a


class Solution:

	def nearlySorted(self, a, n, k):
		j = 0
		from heapq import heapify, heappush, heappop
		h = []
		heapify(h)
		for i in a:
			heappush(h, i)
			if len(h) > k:
				a[j] = heappop(h)
				j += 1
		while h:
			a[j] = heappop(h)
			j += 1
		return a


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		for i in a:
			heapq.heappush(heap, i)
		sort = []
		while heap:
			sort.append(heapq.heappop(heap))
		return sort


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		pq = []
		ans = []
		for num in a:
			heapq.heappush(pq, num)
			if len(pq) > k:
				ans.append(heapq.heappop(pq))
		while len(pq):
			ans.append(heapq.heappop(pq))
		return ans


class Solution:

	def nearlySorted(self, a, n, k):
		heapq.heapify(a)
		res = []
		for i in range(len(a)):
			res.append(heapq.heappop(a))
		return res


class Solution:
	import heapq

	def nearlySorted(self, a, n, k):
		out = []
		h = a[0:k + 1]
		heapq.heapify(h)
		for i in range(k + 1, n):
			out.append(heapq.heappop(h))
			heapq.heappush(h, a[i])
		while len(h) > 0:
			out.append(heapq.heappop(h))
		return out


class Solution:

	def nearlySorted(self, a, n, k):
		min_heap = []
		ans = []
		for i in range(len(a)):
			heapq.heappush(min_heap, a[i])
			if len(min_heap) > k:
				ele = heapq.heappop(min_heap)
				ans.append(ele)
		for i in range(k):
			ele = heapq.heappop(min_heap)
			ans.append(ele)
		return ans


import heapq

class Solution:

	def nearlySorted(self, a, n, k):
		hp = a[:k + 1]
		heapq.heapify(hp)
		res = []
		for i in range(k + 1, n):
			res.append(heapq.heapreplace(hp, a[i]))
		while hp:
			res.append(heapq.heappop(hp))
		return res


class Solution:

	def nearlySorted(self, a, n, k):
		b = []
		for i in a:
			b.append(i)
		b.sort()
		return b


import heapq as h

class Solution:

	def nearlySorted(self, a, n, k):
		heap = []
		for i in a:
			h.heappush(heap, i)
		ans = []
		while heap:
			p = h.heappop(heap)
			ans.append(p)
		return ans


import heapq as hq

class Solution:

	def nearlySorted(self, arr, n, k):
		res = []
		min_heap = []
		for i in arr:
			hq.heappush(min_heap, i)
			if len(min_heap) > k:
				top = hq.heappop(min_heap)
				res.append(top)
		while len(min_heap) > 0:
			top = hq.heappop(min_heap)
			res.append(top)
		return res


import heapq as hq

class Solution:

	def nearlySorted(self, arr, n, k):
		res = []
		min_heap = []
		for i in range(n):
			hq.heappush(min_heap, (arr[i], i))
		i = 0
		while i < n and len(min_heap) > 0:
			(ele, ind) = hq.heappop(min_heap)
			if abs(ind - i) <= k:
				res.append(ele)
			i += 1
		return res


from heapq import heapify, heappop, heappush

class Solution:

	def nearlySorted(self, a, n, k):
		heap = a[:k + 1]
		heapq.heapify(heap)
		ind = 0
		for i in range(k + 1, n):
			a[ind] = heapq.heappop(heap)
			ind += 1
			heapq.heappush(heap, a[i])
		while heap:
			a[ind] = heapq.heappop(heap)
			ind += 1
		return a