Introduction

Ready for an adventure in sorting algorithms? We will solve two fun problems: "Find the K-th Ordinal Number in a List" and "Count the Number of Flips in a List". These tasks portray situations where we need clever system design. Let's employ Quick Sort and Merge Sort to find efficient solutions. Buckle up!

Problem 1: Finding K-th Number in an Array

Picture an array of numbers and a number k. Your mission is to discover the k-th smallest number in that array. k starts from 1, so when k = 1, we seek the smallest number; when k = 2, we want the second smallest, and onwards.

Problem 1: Simple Solutions
Problem 1: Quick Sort to the Rescue

Quick Sort can provide an optimal solution. We’ll divide the array into two parts using a pivot: the left side contains numbers less than the pivot, while the right side has all greater numbers.

If the pivot's position equals k, that's our answer! If not, we repeat the process on the necessary partition.

Problem 1: Building the Solution – Partition

It's coding time! Let’s make a function for partitioning in JavaScript.

function partition(arr, low, high) {
  let pivot = arr[low];
  let i = low;

  for (let j = low + 1; j <= high; j++) {
    if(arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i], arr[low]] = [arr[low], arr[i]];
  return i;
}
Problem 1: Building the Solution – Main Logic

Now we use our partition function in the main logic. If the pivot's position equals k, return the pivot. Otherwise, check the appropriate partition!

function findKthSmallest(numbers, k) {
  if (!numbers || numbers.length < k) return Number.MIN_SAFE_INTEGER;
  return kthSmallest(numbers, 0, numbers.length - 1, k);
}

function kthSmallest(arr, start, end, k) {
  if (k > 0 && k <= end - start + 1) {
    let pos = partition(arr, start, end);
    if (pos - start === k - 1) {
      return arr[pos];
    }
    if (pos - start > k - 1) {
      return kthSmallest(arr, start, pos - 1, k);
    }
    return kthSmallest(arr, pos + 1, end, k - pos + start - 1);
  }
  return Number.MAX_SAFE_INTEGER;
}

console.log(findKthSmallest([1, 7, 2, 4, 2, 1, 6], 5));  // Prints 4

Number.MIN_SAFE_INTEGER is returned by findKthSmallest if the input array numbers is empty or has fewer elements than k. This could represent a case where the k smallest value doesn't exist.

Number.MAX_SAFE_INTEGER is used in the kthSmallest function if k is either less than 1 or greater than the length of the portion of the array being considered. This could mean that there's an error in the k parameter passed, or the array doesn't have enough elements.

These extreme values are used because they are unlikely to be a valid result in any normal situation, making it easy to spot when something has gone wrong. It's a convention to return values which clearly indicate error situations, aiding in debugging and error handling.

Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal