Given an array of integers arr where each element is at most k places away from its sorted position, code an efficient function sortKMessedArray that sorts arr. For instance, for an input array of size 10 and k = 2, an element belonging to index 6 in the sorted array will be located at either index 4, 5, 6, 7 or 8 in the input array.
Analyze the time and space complexities of your solution.
Example:
input: arr = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9], k = 2
output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Constraints:
[time limit] 5000ms
[input] array.integer arr
1 ≤ arr.length ≤ 100 [input] integer k
1 ≤ k ≤ 20 [output] array.integer
My approach improved :
import java.io.*;
import java.util.*;
class Solution {
static int[] sortKMessedArray(int[] arr, int k) {
int arrLen = arr.length;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
//Store the first k+1 elements in the heap
for( int i = 0; i <= k; i++ )
queue.add(arr[i]);
for( int i = k+1; i < arrLen; i++ )
{
//Extract the minimum element in the priority queue
arr[i - (k + 1)] = queue.poll();
//Add the next element to the queue
queue.add(arr[i]);
}
//Extract the remaining elements from the queue and put it in the next index available
for( int i = 0; i <= k; i++ )
arr[ arrLen - k - 1 + i] = queue.poll();
return arr;
}
public static void main(String[] args) {
int [] arr = sortKMessedArray(new int[]{1,0},1);
for( int m : arr )
System.out.println(m);
}
}
I have the following questions regarding my approach:
1) How can I further improve my approach?
2) Is there a better way to solve this question?
3) Are there any grave code violations that I have committed?
4) Can space and time complexity be further improved?
1 Answer 1
You should add a bounds check that k
is not larger than your array, because I don't see that explicitly mentioned in the problem statement.
for( int i = 0; i <= k; i++ )
queue.add(arr[i]);
I think you should always add braces, but that's my personal opinion.
//Store the first k+1 elements in the heap
for( int i = 0; i <= k; i++ )
queue.add(arr[i]);
for( int i = k+1; i < arrLen; i++ )
{
//Extract the minimum element in the priority queue
arr[i - (k + 1)] = queue.poll();
//Add the next element to the queue
queue.add(arr[i]);
}
This bit would make more sense if you kept i as your arr
index. Then swap the statement to get rid of the +1, ...
//Store the first k+1 elements in the heap
int i = 0;
for(; i < k; i++ )
queue.add(arr[i]);
for( ; i < arrLen; i++ )
{
//Add the next element to the queue
queue.add(arr[i]);
//Extract the minimum element in the priority queue
arr[i - k] = queue.poll();
}
This also makes the next section pretty readable;
for( i -= k; i < arrLen; i++ ) //convert i into sorted array index by removing the k offset
arr[i] = queue.poll();
You should also initialize the PriorityQueue with the capacity you're going to need; that's k + 1
.
-
\$\begingroup\$ Thanks for the valuable advice, @Pimgd. I didn't check whether k is larger than the array length as I assumed that the k's that I will be testing won't exceed the array length ever. \$\endgroup\$Anirudh Thatipelli– Anirudh Thatipelli2018年05月28日 06:24:30 +00:00Commented May 28, 2018 at 6:24
Explore related questions
See similar questions with these tags.