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

The first solution might involve scanning and shrinking the array by removing the smallest number until you reach the k-th smallest. But this method, while straightforward, has a time complexity of O(n2)O(n^2) due to continuous array rewriting.

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