K Messed Array sort in Java 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&lt;Integer&gt; queue = new PriorityQueue&lt;Integer&gt;();

   //Store the first k+1 elements in the heap
   for( int i = 0; i &lt;= k; i++ )
      queue.add(arr[i]);

   for( int i = k+1; i &lt; 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 &lt;= 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?

Reference
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 &lt;= 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 &lt;= k; i++ )
   queue.add(arr[i]);

for( int i = k+1; i &lt; 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 &lt; k; i++ )
   queue.add(arr[i]);

for( ; i &lt; 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 &lt; 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.