Quickselect

To find the kth smallest element in an unsorted list (O(n))

Choose pivot, partition array, if the pivot’s new position is:
1. k: we found the element
2. k: element must be in the left partition, continue there
3. <k: element must be in right partition, continue there

Queue

Initial State: Start with n teams, ranked $T_{1}$ through $T_{n}$ . The team $T_{i}$ is initially in position $i$ .
Game Results: Process $m$ game results chronologically. Each result is of the form “team $T_{i}$ beat team $T_{j}$ .”
The Ranking Rule: When a game result is processed, rankings only change if a team at a lower rank (higher-n position) beats higher rank (lower-n position).
How to Update: If team $T_{i}$ beats $T_{j}$ and $p_{i} > p_{j}$ , then team $T_{i}$ moves up one position, and team $T_{j}$ moves down one position.
Then output final ranking how: For each result, find position of $T_{i}$ and $T_{j}$ (using array), check the rule, perform the swap, update positions

Two input strings, both sorted: e.g. ahjmnoy and acijjkll
Merge both to a sorted output: aachijjjkllmnoy How: take one character from each string, add the “smaller” one to the output

Given an integer array nums, need to find the length of the shortest continuous subarray such that if you only sort this subarray, then the whole array will be sorted How:

O(n log n): Sort original array, then find the max and min indexes of the unsorted elements
O(n): Find unsorted end, from left to right, find the current max, if current element is less than current max, update it as the end, otherwise update current max to the current element; repeat opposite to find unsorted start. If begin was not set, means array is already sorted and return 0, else return end - begin + 1