Topic 03 of 15
Searching & Sorting
Finding a page in a book.
When things are in order, you never need to look at all of them. Open a dictionary in the middle, see if your word comes before or after, and throw away the half you do not need. That is binary search, and it also works on answers, not just on arrays.
What you will be able to do
Binary searchBinary search on the answerMerge sort and counting inversionsQuick selectTwo pointers on sorted data
0/36
Meet binary search
01 / 04
Seven sorted cards. We want 23.
- looking now
- answer
- ignored
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Find first and last positions of an element in a sorted arrayIn a sorted list where a number can repeat, find where its run of copies starts and where it ends.Binary search
- 02Find a Fixed Point (Value equal to index) in a given arrayIn a sorted row of different numbers, find a box whose number is the same as its own position.Binary search
- 03Search in a rotated sorted arrayA sorted row of books was cut and its two parts swapped; find a book fast by always checking which half is still in order.Binary search
- 04Square root of an integerFind the biggest square of tiles you can build from a pile of x tiles, by guessing the side length higher or lower.Binary search on the answer
- 05Maximum and minimum of an array using minimum number of comparisonsFind the tallest and the shortest kid in a line by comparing kids two at a time, so you need fewer checks.Pair comparison
- 06Optimum location of point to minimize total distancePick the spot for a bus stop on a straight road so that the houses around it walk the least in total.Ternary search
- 07Find the repeating and the missingThe numbers 1 to n should each appear once, but one shows up twice and one is gone; find both.Math with sums
- 08Find majority elementFind the number that appears in more than half of the boxes, using no extra memory.Boyer-Moore voting
- 09Searching in an array where adjacent differ by at most kClimb a staircase where each step changes height by at most k, and skip the steps that cannot possibly be the height you want.Jump search
- 10Find a pair with a given differenceFind two numbers in a list that are exactly a given distance apart.Two pointers
- 11Find four elements that sum to a given valueFind every different group of four numbers in a list that adds up to a target.Two pointers
- 12Maximum sum such that no 2 elements are adjacentGrab the most candy from a row of jars when you are never allowed to take from two jars that stand side by side.1D dynamic programming
- 13Count triplet with sum smaller than a given valueCount how many ways you can pick three different numbers whose total stays under a limit.Two pointers
- 14Merge 2 sorted arraysTwo sorted shelves of books must end up as one sorted run across both shelves, without a spare table to put books on.Gap method (shell sort)
- 15Print all subarrays with 0 sumFind every stretch of days where your piggy bank ends exactly where it started, by remembering every running total you have seen.Prefix sum with hash map
- 16Product array PuzzleFor every kid in a line, multiply the numbers of everyone else, using what the kids to the left and to the right already worked out.Prefix and suffix products
- 17Sort array according to count of set bitsLine up numbers by how many lights are on in their binary form, most lights first, keeping ties in their original order.Counting sort by key
- 18Minimum no. of swaps required to sort the arrayKids sit in the wrong chairs. Count the fewest swaps to seat everyone right by finding the circles of kids who are sitting in one another's chairs.Cycle counting
- 19Bishu and SoldiersAnswer many questions of the form: how many soldiers are weak enough to beat, and how strong are they all together.Binary search
- 20Rasta and KheshtakFind the biggest square patch of tiles that appears in both of two tiled floors, by guessing a size and comparing fingerprints of all patches of that size.Binary search on the answer
- 21Kth smallest number againMany number ranges are poured into one bag without repeats; answer which number would be k-th if the bag were sorted.Merge intervals and binary search
- 22Find pivot element in a sorted arrayA sorted list was turned like a wheel; find the spot where it was turned, where the biggest number is followed by the smallest.Binary search
- 23K-th Element of Two Sorted ArraysFind the k-th smallest number of two sorted lists put together, without actually putting them together.Binary search on the answer
- 24Aggressive cowsPut grumpy cows into stalls along a line so that the two cows closest together are still as far apart as possible.Binary search on the answer
- 25Book Allocation ProblemSplit a row of books between students, each taking a run of books next to each other, so the busiest student reads as few pages as possible.Binary search on the answer
- 26EKOSPOJSet a saw blade as high as possible so that the tree tops it cuts off still add up to the wood you need.Binary search on the answer
- 27Job Scheduling AlgoEach job takes one hour, pays some money, and must be done by its deadline; pick and place jobs to earn the most.Greedy by sorting
- 28Missing Number in APFence posts are planted at equal steps but one post is missing; find it by checking whether each post stands where it should.Binary search
- 29Smallest number with at least n trailing zeroes in factorialCount the fives hiding inside a factorial to know its trailing zeros, then binary search for the first number with enough of them.Binary search on the answer
- 30Painters Partition ProblemSplit a row of fence boards among k painters, each painting boards that stand together, so the slowest painter finishes as early as possible.Binary search on the answer
- 31ROTI-Prata SPOJCooks who get slower with every prata work together; find the earliest minute when the whole order of pratas is ready.Binary search on the answer
- 32DoubleHelix SPOJWalk along two sorted number paths that cross at shared numbers, switching paths at crossings to collect the biggest total.Two pointers
- 33Subset SumsCount the ways to pick some toys so their total price lands in a range, by splitting the toys into two halves and matching the halves up.Meet in the middle
- 34Find the inversion countCount how many pairs in a line are in the wrong order, with a bigger number standing before a smaller one.Divide and conquer
- 35Implement Merge-sort in-placeSort by splitting in halves and merging them back, but do the merging inside the same array with no second array to copy into.Divide and conquer
- 36Partitioning and Sorting Arrays with Many Repeated EntriesSort a big pile of cards with only a few different numbers by splitting it into smaller, equal and bigger piles, and never touching the equal pile again.Three way partitioning