22. Nearly Sorted
✅ GFG solution to the Nearly Sorted Array problem: efficiently sort an array where each element is at most k positions away from its target position using min heap. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are 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.
A nearly sorted array is one where each element is displaced by at most k positions from where it would be in a fully sorted array. The goal is to efficiently sort this array by leveraging this property.
📘 Examples
Example 1
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 3Example 2
Input: arr[] = [7, 9, 14], k = 1
Output: [7, 9, 14]
Explanation: All elements are already stored in the sorted order.🔒 Constraints
$1 \le \text{arr.size()} \le 10^6$
$0 \le k < \text{arr.size()}$
$1 \le \text{arr}[i] \le 10^6$
✅ My Approach
The optimal approach uses a Min Heap (Priority Queue) to efficiently sort the nearly sorted array by maintaining a window of k+1 elements:
Min Heap Approach
Initialize Min Heap:
Create a min heap and insert the first k+1 elements from the array.
These k+1 elements contain the smallest element that should be placed at index 0.
Process Remaining Elements:
For each remaining element in the array:
Extract the minimum from the heap and place it at the current sorted position.
Insert the next element from the array into the heap.
This maintains a sliding window of k+1 elements.
Empty the Heap:
After processing all elements, extract remaining elements from the heap.
Place them in their correct sorted positions.
Key Insight:
Since each element is at most k positions away, the smallest element in any window of k+1 consecutive elements belongs at the start of that window.
Using a min heap ensures O(log k) insertion and extraction operations.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log k), where n is the size of the array. We perform n insertions and n deletions on a heap of maximum size k+1, each operation taking O(log k) time.
Expected Auxiliary Space Complexity: O(k), as the min heap stores at most k+1 elements at any given time. This is constant relative to the array size when k is small.
🧑💻 Code (C++)
class Solution {
public:
void nearlySorted(vector<int> &arr, int k) {
priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.begin() + k);
int idx = 0;
for (int i = k; i < arr.size(); i++) {
pq.push(arr[i]);
arr[idx++] = pq.top();
pq.pop();
}
while (!pq.empty()) {
arr[idx++] = pq.top();
pq.pop();
}
}
};☕ Code (Java)
class Solution {
public void nearlySorted(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
int idx = 0, n = arr.length;
for (int i = 0; i <= Math.min(k, n - 1); i++) pq.add(arr[i]);
for (int i = k + 1; i < n; i++) {
arr[idx++] = pq.poll();
pq.add(arr[i]);
}
while (!pq.isEmpty()) arr[idx++] = pq.poll();
}
}🐍 Code (Python)
class Solution:
def nearlySorted(self, arr, k):
import heapq
h = arr[:min(k + 1, len(arr))]
heapq.heapify(h)
idx = 0
for i in range(k + 1, len(arr)):
arr[idx] = heapq.heappop(h)
heapq.heappush(h, arr[i])
idx += 1
while h:
arr[idx] = heapq.heappop(h)
idx += 1🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated