5
\$\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

asked May 27, 2018 at 14:39
\$\endgroup\$

1 Answer 1

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.

answered May 27, 2018 at 22:34
\$\endgroup\$
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\$ Commented May 28, 2018 at 6:24

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.