Algos

/*
Rating of Confidence: 80% 
Practiced Date: 04/15/2022 

Q. Given an array of positive integers, find the first element that occurs k number of times. If no element occurs k times, return -1, and you may assume k is greater than 0. 

Examples:
• Given an array: [1, 2, 2, 3, 3], k: 2 // returns 2
• Given an array: [], k: 1 // returns -1
*/

function firstKTimes(array, k) {
  const counts = new Map(); 

  for(const el of array) {
    const count = (counts.get(el) || 0) + 1; 
    console.log(count); 
    if(count === k ) return el; 
    counts.set(el, count); 
  }
  return -1
}

// Test Cases
console.log(firstKTimes([1, 2, 2, 3, 3], 2)) // 2
console.log(firstKTimes([1, 2, 2, 3, 3], 3)) // -1
console.log(firstKTimes([], 1)) // -1

/*Merge Sort*/

//sort an unsorted array using mergeSort 
// Merge Sort Implentation (Recursion)
//

function mergeSort (unsortedArray) {
  // No need to sort the array if the array only has one element or empty
  if (unsortedArray.length <= 1) {
    return unsortedArray;
  }
  // In order to divide the array in half, we need to figure out the middle
  const middle = Math.floor(unsortedArray.length / 2);

  // This is where we will be dividing the array into left and right
  const left = unsortedArray.slice(0, middle);
  const right = unsortedArray.slice(middle);

  // Using recursion to combine the left and right
  return merge(
    mergeSort(left), mergeSort(right)
  );
}

// Merge the two arrays: left and right
function merge (left, right) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;

  // We will concatenate values into the resultArray in order
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      resultArray.push(left[leftIndex]);
      leftIndex++; // move left array cursor
    } else {
      resultArray.push(right[rightIndex]);
			rightIndex++; // move right array cursor
    }
  }

  // We need to concat to the resultArray because there will be one element left over after the while loop
  return resultArray
          .concat(left.slice(leftIndex))
          .concat(right.slice(rightIndex));
}


// Q. Given an unsorted array, perform selection sort in descending  order. Change line 27 arr[max] < arr[j] to change to ascending 

// Examples:
// • Given an array: [1] // returns [1]
// • Given an array: [3, 1, 2, 4] // returns [1, 2, 3, 4]
/*

1 2 3 4.   min = 2
        |
j
 big loop 
  min =  i 
  j = i+1 small loop
    arr[min] > arr[j]
      min = j
   
  if min != i
    arr[i] = arr[min]
O(n^2) where n = array.length
O(1)
*/

function selectionSort(arr) {
    for (let i=0; i< arr.length; i++) {
      let max = i; 
        for (let j=i+1; j< arr.length; j++) {
          if(arr[max] < arr[j]){
            max = j; 
          }
        }

        if(max !== i) {
          let temp = arr[i]; 
          arr[i] = arr[max]; 
          arr[max] = temp; 
        }
    }
    return arr; 
}

// Test Cases
console.log(selectionSort([])) // []
console.log(selectionSort([1])) // [1]
console.log(selectionSort([3, 1, 2, 4])) // [1, 2, 3, 4]
console.log(selectionSort([-10, 1, 3, 8, -13, 32, 9, 5])) // [-13, -10, 1, 3, 5, 8, 9, 32]