Daily Algorithm - Sort by Height

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees.

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

• [execution time limit] 3 seconds (java)

• [input] array.integer a

  If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ith position.

  Guaranteed constraints:
  5 ≤ a.length ≤ 15,
  -1 ≤ a[i] ≤ 200.

• [output] array.integer

  Sorted array a with all the trees untouched.

Solution

import java.util.Arrays;

public class SortbyHeight {
    static int[] sortByHeight(int[] a) {
        int[] result = new int[a.length];
        int[] copyArray = new int[a.length];

        System.arraycopy(a, 0, copyArray, 0, a.length);
        Arrays.sort(copyArray);

        for (int i = 0, j = 0; i < a.length; i++) {
            if (a[i] != -1) {
                while (copyArray[j] == -1) {
                    j++;
                }

                result[i] = copyArray[j];
                j++;
            }
            else
                result[i] = a[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] a = { -1, 150, 190, 170, -1, -1, 160, 180 };
        a = sortByHeight(a);

        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}