Leetcode_bubbleSort_Height Checker

Problem

Complexity

Time complexity: O(n^2)

Code

/**  

Height Checker

- students stand in single file line in non-decreasing order
- expected[i] -> i'th student

- heights : current order array
- return numbers of indices where heights[i] not equal to expected[i]

*/

const heights = [1,1,4,2,1,3]
const expected = [1,1,1,2,3,4]

var heightChecker = function(heights) {

  const expected = [...heights]

  // Get sorted array with bubble sort
  has_swapped = true;
  let count = 0;
  while (has_swapped) {
    has_swapped = false;

    for(let i = 0; i < expected.length; i++) {
      if(expected[i] > expected[i+1]) {
        [expected[i], expected[i+1]] = [expected[i+1], expected[i]]
        has_swapped = true;
      }
    }
  }

  // Get different elements by filtering
  const matchedElements = heights.filter((el, idx) => el != expected[idx])
  
  // return the numbers of different elements
  return matchedElements.length;
};

console.log(heightChecker(heights))