Sort Almost Sorted Array Editorial

Practice Problem Link: Sort Almost Sorted Array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A of size n, which is almost sorted. Each element is misplaced by no more than

k positions from the correct sorted order. You need to find an efficient way to properly sort the array.

Naive Approach

A simple way to solve this problem is just to sort the given array.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<int> sortAlmostSorted(vector<int> &arr, int k) {
   sort(arr.begin(), arr.end());
   return arr;
}

Java

class Solution {
   int[] sortAlmostSorted(int[] arr, int k) {
       Arrays.sort(arr);
       return arr;
   }
}

Optimal Approach

An efficient way to sort this array is by using Min Heap. 

• Store the first k+1 elements in the heap then the minimum of those elements must be on the 0-th index in the sorted array as the elements in the array is misplaced by at most k positions.
• Remove the minimum element from the heap and place it at the right position and add a new element in the heap from the remaining elements in the array.
• The above two steps will be repeated for all the indexes until the array is sorted.

Analysis

• Time Complexity: O(n * log(k))
• Auxiliary Space Complexity: O(k)

Implementation

C++

vector<int> sortAlmostSorted(vector<int> &arr, int k) {
   int n = arr.size();
   priority_queue <int, vector<int>, greater<int> > minHeap;
   for (int i = 0; i <= k; i++) {
       minHeap.push(arr[i]);
   }
   int indx = 0;
   for (int i = k + 1; i < n; i++) {
       arr[indx++] = minHeap.top();
       minHeap.pop();
       minHeap.push(arr[i]);
   }
   while(!minHeap.empty()) {
       arr[indx++] = minHeap.top();
       minHeap.pop();
   }
   return arr;
}

Java

class Solution {
   int[] sortAlmostSorted(int[] arr, int k) {
       int n = arr.length;
       PriorityQueue <Integer> minHeap = new PriorityQueue<> ();
       for (int i = 0; i <= k; i++) {
           minHeap.add(arr[i]);
       }
       int indx = 0;
       for (int i = k + 1; i < n; i++) {
           arr[indx++] = minHeap.peek();
           minHeap.poll();
           minHeap.add(arr[i]);
       }
       Iterator<Integer> itr = minHeap.iterator();
       while(itr.hasNext()) {
           arr[indx++] = minHeap.peek();
           minHeap.poll();
       }
       return arr;
   }
}