Sort_By_Height.md

🔷 Sort by Height 🔷

Challenge description

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. People can be very tall!

Example

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

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [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:
  1 ≤ a.length ≤ 1000,
  -1 ≤ a[i] ≤ 1000.

• [output] array.integer

  Sorted array a with all the trees untouched.

[Java] Syntax Tips

## Solutions:

• JS solution

  CodeSignalSolutions/Sort_By_Height/Sort_by_height.js

  Lines 1 to 23 in bfe6e99

  	function solution(array) {
  	var heights = []
  	array.forEach(num=> {
  	if(num!==-1)
  	heights.push(num)
  	})
  	for (let j = 0; j < heights.length - 1; j++) {
  	for (let i = 0; i < heights.length - 1 -j; i++) {
  	const current = heights[i]
  	if(current > heights[i+1]){
  	heights[i] = heights[i+1]
  	heights[i+1] = current
  	}
  	}
  	}
  	for (let i = 0, j = 0; i < array.length; i++) {
  	array[i] = array[i] !== -1? heights[j++]: -1
  	}
  	return array
  	}

  

• Java solution

  CodeSignalSolutions/Sort_By_Height/Sort_by_height.java

  Lines 16 to 38 in bfe6e99

  	static int[] solution(int[] a){
  	List<Integer> heights = new ArrayList<>(a.length);
  	for (int num : a)
  	if (num != -1)
  	heights.add(num);
  	for (int j = 0; j < heights.size() - 1; j++){
  	for (int i = 0; i < heights.size() - 1 - j; i++) {
  	int current = heights.get(i);
  	int next = heights.get(i+1);
  	if ( current > next) {
  	heights.set(i, next);
  	heights.set(i + 1, current);
  	}
  	}
  	}
  	for (int i = 0, j = 0; i < a.length; i++)
  	a[i] = a[i] == -1 ? -1 : heights.get(j++);
  	return a;
  	}