4
\$\begingroup\$

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?

Reference

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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 May 28 '18 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.