Topic 01 of 15
Array
A row of numbered lockers.
An array is a row of lockers. Every locker has a number, starting at 0, and you can open any locker right away if you know its number. Most interview problems start here: walk the row, keep two fingers on it, or remember what you saw in a notebook.
What you will be able to do
Two pointersPrefix sumsKadaneHash map lookupsSorting first
0/36
Meet the array
01 / 04
Five lockers in a row. The little numbers on top are the locker numbers. They start at 0.
- looking now
- checking
- path
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Reverse the arrayTurn a line of kids around so the last kid is first, by having kids from the two ends swap places until they meet in the middle.Two pointers
- 02Find the maximum and minimum element in an arrayFind the smallest and the biggest number in a list, using as few comparisons as possible.Compare in pairs
- 03Write a program to cyclically rotate an array by oneTurn a merry-go-round one notch: the last rider hops to the front and everyone else moves one seat back.In-place shifting
- 04Move all the negative elements to one side of the arraySend every negative number to the left side of the row and every other number to the right, by swapping in place.Two pointers
- 05Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algoSort an array that holds only 0s, 1s and 2s in one walk, by sending 0s to the front and 2s to the back.Three pointers
- 06Find the Union and Intersection of the two sorted arraysFrom two sorted lists, list every number that is in either one (union) and every number that is in both (intersection).Two pointers
- 07Find all pairs on integer array whose sum is equal to given numberFind every pair of numbers in a list that adds up to a target, by remembering what you have already seen.Hash map counting
- 08Find if there is any subarray with sum equal to 0Check if some unbroken stretch of the array adds up to exactly zero, by watching for a running total you have seen before.Prefix sum with a hash set
- 09Find Largest sum contiguous SubarrayFind the unbroken stretch of numbers with the biggest total, by carrying a running bag and dropping it whenever it goes negative.Kadane's algorithmMust do
- 10Kadanes AlgoWalk down a street where some houses give you candy and some take it away, and find the stretch of houses in a row that leaves you with the most candy.Kadane running sumMust do
- 11Best time to buy and Sell stockBuy a sticker on one day and sell it on a later day, and find the most money you can earn.Running minimum
- 12Find maximum product subarrayFind the unbroken stretch of numbers whose product is biggest, remembering that two negatives make a positive.1D dynamic programming
- 13Find the Kth max and min element of an arrayFind the k-th smallest and the k-th largest number without fully sorting the list.Quickselect
- 14Find duplicate in an array of N+1 Integersn + 1 numbers from 1 to n means one number repeats; find it without changing the array and without extra room.Fast and slow pointers
- 15Merge 2 sorted arrays without using Extra spaceTwo sorted shelves of books must end up as one sorted run, with the small books on the first shelf and the big ones on the second, and no spare shelf to help.Gap method (shell sort)
- 16Find common elements In 3 sorted arraysFind the numbers that appear in all three sorted lists by walking one finger along each list.Two pointers
- 17Find the triplet that sum to a given valueFind three numbers in a list that add up to a target, by fixing one and squeezing the other two from both ends.Two pointers
- 18Find longest consecutive subsequenceFind the longest run of numbers that follow each other, like 1, 2, 3, 4, hidden anywhere in a messy list.Hash set lookups
- 19Find whether an array is a subset of another arrayCheck whether every number of a small list can be found in a big list, using each copy in the big list only once.Hash map counting
- 20Chocolate Distribution problemHand one chocolate packet to each kid so the biggest and smallest packets given out are as close as possible.Sort then sliding window
- 21Smallest Subarray with sum greater than a given valueFind the shortest run of piggy banks in a row whose coins add up to more than a target, by stretching and shrinking a window over the row.Sliding window
- 22Three way partitioning of an array around a given valueSort toys into three boxes, small, medium and big, in one pass along the shelf by swapping, without any extra boxes.Dutch national flag
- 23Merge IntervalsPlaydates on a calendar overlap, so you join every group of overlapping playdates into one long block of busy time.Greedy by sorting
- 24Next PermutationRearrange number cards into the very next bigger order, like turning a car odometer forward by the smallest possible step.Two pointers
- 25Count InversionCount how many pairs in a line are in the wrong order, where a bigger number stands before a smaller one.Divide and conquer
- 26Rearrange the array in alternating positive and negative items with O(1) extra spaceLine up boys and girls so they alternate, keeping everyone in their original order, without a second line to help.In-place rotation
- 27Given an array of size n and a number k, find all elements that appear more than n/k timesFind every number that shows up more than n / k times, using a tiny bench of candidates instead of counting everything.Voting with k - 1 candidates
- 28Minimise the maximum difference between heightsEvery kid in the photo must either stand on a box or kneel down by the same amount, and you choose who does what so the tallest and shortest heads end up as close as possible.Greedy by sortingMust do
- 29Minimum no. of Jumps to reach end of an arrayHop along stepping stones where each stone says how far you may hop from it, and reach the last stone in as few hops as possible.Greedy window (BFS levels)
- 30Minimum swaps required bring elements less equal K togetherGet all the small kids to sit next to each other on one bench by swapping seats as few times as possible.Sliding window
- 31Trapping Rain water problemRain falls on a row of blocks of different heights, and you count how much water stays trapped in the dips between them.Two pointers
- 32Minimum no. of operations required to make an array palindromeGlue neighbouring train cars together until the train reads the same from the front and from the back, using as few glue steps as you can.Two pointers
- 33Find factorial of a large numberMultiply 1 * 2 * 3 * ... * n when the answer is far too long for any number type, by keeping one digit per box like on school paper.Big number arithmetic
- 34Maximum profit by buying and selling a share atmost twiceYou know the price of a toy for every day ahead, and you may buy and sell it at most two times, so find the most money you can earn.1D dynamic programming
- 35Median of 2 sorted arrays of equal sizeTwo sorted rows of the same length are mixed in your head, and you find the middle of all of them by cutting each row in the right place instead of mixing them for real.Binary search on the answer
- 36Median of 2 sorted arrays of different sizeTwo sorted lines of kids stand side by side, and you find the middle height of everyone together without merging the lines, by guessing where to cut each line.Binary search on the answer