Lost in Compilation

Problem : Given an unsorted array, find the kth smallest element. The problem is called the Selection problem . It's been intensively studied and has a couple of very interesting algorithms that do the job. I'll be  describing an algorithm called QuickSelect . The algorithm derives its name from QuickSort. You will probably recognise that most of the code directly borrows from QuickSort. The only difference being there is a single recursive call rather than 2 in QuickSort. The naive solution is obvious, simply sort the array `O(nlogn)` and return the kth element. Infact, you can partially sort it and use the Selection sort to get the solution in `O(nk)` An interesting side effect of finding the kth smallest element is you end up finding the k smallest elements. This also effectively gives you (n - k) largest elements in the array as well. These elements are not in any particular order though. The version I'm using uses a random pivot selection, this part of the al...

Given an Array A[1..n] of distinct integers find out how many instances are there where A[i] > A[j] where i < j. Such instances can be called Inversions. Say, [100,20,10,30] the inversions are (100,20), (100, 10), (100,30), (20,10) and the count is of course 4 The question appears as an exercise in the  Chapter 4 of Introduction to Algorithms .  (3rd Edition) As per our tradition we'll start with the worst algorithm and incrementally improve upon it. So on with it. So the complexity of the algorithm is O(n^2). We can do this even faster using divide and conquer, more aptly if we use a variation of Merge Sort . To do this, unfortunately, we will have to mutate the array. The key to the algorithm is to understand that in an ascending sorted array the inversion count is zero. Say [10,20,30] If we perhaps have an element 100 before the rest of the array, the inversion count becomes 3. [100,10,20,30]. If we placed the 100 at the second position the in...

Given k-sorted array, find the minimum interval such that there is at least one element from each array within the interval. Eg. [1,10,14],[2,5,10],[3,40,50]. Output : 1-3 To solve this problem, we perform a k-way merge as described here . At each point of 'popping' an element from an array. We keep track of the minimum and maximum head element (the first element) from all the k-lists. The minimum and maximum will obviously contain the rest of the header elements of the k-arrays. As we keep doing this, we find the smallest interval (max - min). That will be our solution. Here's a pictorial working of the algorithm. And here's the Python code. Time Complexity : O(nlogk)

Problem - Given k-sorted lists, merge them into a single sorted list. A daft way of doing this would be to copy all the list into a new array and sorting the new array. ie O(n log(n)) The naive method would be to simply perform k-way merge similar to the auxiliary method in Merge Sort. But that is reduces the problem to a minimum selection from a list of k-elements. The Complexity of this algorithm is an abysmal O(nk). Here's how it looks in Python. We maintain an additional array called Index[1..k] to maintain the head of each list. We improve upon this by optimizing the minimum selection process by using a familiar data structure, the Heap! Using a MinHeap, we extract the minimum element from a list and then push the next element from the same list into the heap, until all the list get exhausted. This reduces the Time complexity to O(nlogk) since for each element we perform O(logk) operations on the heap. An important implementation detail is we need to keep track ...

Problem - Given an integer array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Let's start with the obvious solution, bruteforce every three element combination until we find a solution. Let's try to reduce this by searching left and right for each element, we search left for an element smaller than the current one, towards the right an element greater than the current one. When we find an element that has both such elements, we found the solution. The complexity of this solution is O(n^2). To reduce this even further, One can simply apply the longest increasing subsequence algorithm and break when we get an LIS of length 3. But the best algorithm that can find an LIS is O(nlogn) with O( n ) space . An O(nlogn) algorithm seems like an overkill! Can this be done in linear time? The Algorithm: We iterate over the array and keep track of two things. The minimum value iterated over (min) The minimum increa...

Problem - Given 4 arrays A,B,C,D. Find out if there exists an instance where A[i] + B[j] + C[k] + D[l] = 0 Like the Find the Triple problem, we're going to develop 4 algorithms to solve this. Starting with the naive O(n^4) solution. Then we proceed to eliminate the inner-most loop with a Binary Search, reducing the complexity to O(n^3 logn) Now, we replace the last 2 loops with the left-right traversal we did in the previous 3 posts. Now the complexity is O(n^3). Finally, we reduce the complexity to O(n^2 logn) at the cost of O(n^2) Space Complexity. We store every combination of A[i] + B[j] and store it in AB[]. Similarly we make CD[] out of C[i] + D[j]. So, AB = A x B CD = C x D We then sort AB and CD (which costs O(n^2 log(n^2)) ~ O(n^2 logn) ) and then run a left-right linear Algorithm on AB and CD. (Note : Their size is of the order O(n^2)) So the overall complexity is due to sorting the large array of size n^2. which is O(n^2 logn).

Problem : Given 3 Integer Arrays A,B,C. Find out if an instance exists where A[i] + B[j] + C[k] == 0. Very deceptive question but very similar to the  3SUM  Problem. The Naive solution is O(n^3). If you're a little clever, you can do a O(n^2 logn). At this point, you might give up assuming that this is pretty efficient. But then there is also a O(n^2) solution as well! Let's go from worst to best. The Naive solution is trivial. Try every combination until we hit a solution, if we don't there is no solution. So let's try to speed things up a bit, since the solution is already O(n^3), I think we can afford to sort any of the  arrays since nlogn = o(n^3). Therefore, we cleverly sort the Array C. Now in the third loop we replace the linear scan with a binary search to find (-A[i]-B[j]). The complexity is now reduced to O(n^2 logn) At this point, you've leveled up. The next algorithm might not be immediately apparent but works. In fact the method is simila...

Problem - Given an Array of integers, A. Find out if there exists a triple (i,j,k) such that A[i] + A[j] + A[k] == 0. The 3SUM  problem is very similar to the 2SUM  problem in many aspects. The solutions I'll be discussing are also very similar. I highly recommend you read the previous post first, since I'll explain only the differences in the algorithm from the previous post. Let's begin, We start with the naive algorithm. An O(n^3) solution with 3 nested loops each checking if the sum of the triple is 0. Since O(n^3) is the higher order term, we can sort the array in O(nlogn) and add a guard at the nested loops to prune of parts of the arrays. But the complexity still remains O(n^3). The code is pretty simple and similar to the naive algorithm of 2SUM. Moving on, we'll do the same thing we did in 2SUM, replace the inner-most linear search with a binary search. The Complexity now drops to O(n^2 logn) Now, the hash table method, this is strictly not ...

Problem : Given an array with distinct elements. Find out if there exists an instance where sum of two distinct elements is equal to a given constant K. Say, A = [1,2,3,4], K = 7. Output should be 3,4 The naive solution for this problem is pretty trivial. Brute force every pair-sum and check if the sum is K. You could be a little smart about this. You initially sort the array O(nlogn) and iterate the array pairwise and quit when the sum exceeds K, you can quit the inner loop since the array is sorted the sum can only increase. For the rest of the article, I'll be assuming K = 0, this doesn't affect the solutions in any way and it's trivial to introduce a new variable into the code without major changes. Here's the code, should be easy to follow... I'll be using Java today. Now that the naive solution is out of the way, let's try and do some clever stuff. So notice we can afford to sort the array since the brute solution was already O(n^2) (which ...

As promised, this is the follow up to the first posted earlier that there was a more efficient algorithm for finding the longest increasing subsequence, better than the O(n^2) DP solution we came up with. It's not easy to understand, but once you get what the variables mean, it seems pretty straight forward. We'll be implementing another DP solution, similar to the previous one, except with an additional data structure that'll reduce the overall complexity to O(nlogn). The wikipedia seems no help. The explanation is contrived and not easy to visualize. Hope this post will clear a lot of doubts. So we need 3 arrays for solving an instance of LIS. M[i] - where M[i] is the minimum ending element of a increasing subsequence of length i. This is the key part of the new algorithm. Unlike the earlier solution where we kept the longest length discovered at index i , we store an Array which holds the minimum value of a subsequence of length i. I[i] - where M[i] = A[I[i]] si...

Problem: Given an array of positive non-zero integers. Find out the minimum hops required to traverse the array, if the value at an index denotes the maximum length you can hop from that index. To perform a brute force solution, we can use a depth first search with pruning. This usually explodes with arrays of size greater than 50. But never the less, it's important to understand how it works. Following our dismal performance using DFS, we move on to the big guns, Dynamic Programming. We define minHop[i]   as the minimum hops you need from index i to reach the end of the array. Therefore, minHop[i] = 1 { if arr[i] + i > len(arr) } needs just one hop, trivial. minHop[i] = 1 + min ( minHop[i+1 : i+arr[i]] ) { the minimum hop from my range which will reach the end of the array } We start with i = len(arr) - 1 and count down to i  = 0 . At which point minHop[0] will be the minimum hops required to reach the end of the array from index = 0. So here we hav...

Problem : In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn't know anyone in the party.  We can only ask questions like “does A know B? Find the celebrity in minimum number of questions. This is a very interesting problem. The answer, ie the least number of questions required, changes based on what's given. Are we guaranteed there's one celebrity in the party? Does every non-celeb know every other non-celeb? ( not very ideal, but under a best case scenario. ) Once again, the rules There is at most one celebrity at the party Everyone knows the celebrity. The celebrity knows no one. We can only ask the question "Does A know B?" When we ask the question, we can get a "yes" or "no". Each conveying information about both the participants in the question. Let's see those outcomes... If the Answer is "Yes", we know A is definitely not a celebrit...

Problem - Given an array of integers. Find the longest increasing subsequence in the array. Eg. [42, 91, 46, 73, 75, 91, 95]. The LIS for this array is 6 which is [42,46,73,75,91,95]. Note: Subsequence does not require the elements to be contiguous As always, we begin with our naive solution which is a DFS/Bruteforce search trying every possible combination until we get the longest sequence. This is simply exhaustive and will explode on bigger arrays. Time Complexity : O(2^n) ~ Exponential Now, If you notice we repeatedly try a prefix subsequence repeatedly. This tells us, the problem is a good candidate for a dynamic programming algorithm. We define lis[0...L] , where L is the length of the array. We define lis[i] as the length of longest increasing subsequence that ends at i.  lis[0] = 1 { trivial since, the longest increasing sequence that ends at the start of the array contains just the first element, also true for the arr[i] where arr[i] is the smaller th...

Problem - Write an algorithm capable of rotating a matrix, in-place without any auxiliary storage. I don't have an elaborate thought process to develop this algorithm. It's a few rules you ought to remember to implement rotations in the matrix. To implement these rules, you need some helper functions which are quite simple really. You need to be able to transpose a matrix, reverse a row, reverse a column. That's it. The rest is just a combination of these 3 functions. Python is awesome, isn't it? Note : These functions create copies of the matrix, we can design algorithms that modify the original matrix with ease for square matrices. For non-square matrices, we have to create new matrices. Okay, let's get to the rotations. So we need to perform three kinds of rotations. 90,180,270. 1) Rotation by 90/-270  degrees Transpose the Matrix Reverse each row 2) Rotation by 180/-180 degrees There are two methods: First Method, is clearly obviou...

Problem : Given a set of integers A, find out if there is a subset of A which add up to a particular integer K. Formally called the Subset Sum Problem , we are given an NP-Complete problem. To solve this, we have to exhaustively search every subset and verify if they add up to an integer K. Let's begin with a Brute force DFS search, we're going to construct subsets incrementally until the sum exceeds K. The elements are assumed sorted in the increasing order. So we perform a DFS trying to perform every combination of the elements in the set. The recursive function either will include an element in the sum or exclude it. The guard prunes off DFS paths that exceed the sum required. There is an efficient method for this, using Dynamic Programming. Essentially, we start with a single element, add the next element together to get the new sums possible. These new sums will be the input for the next iteration. I'll explain with an example, say we have {a,b,c} You...

This is a slightly trickier version of The Missing Duplicate Number . Instead of one single missing number, we have 2. Problem : Given an array of Integers. Each number is repeated even number of times. Except 2 numbers which occur odd number of times. Find the two numbers Ex. [1,2,3,1,2,3,4,5] The Output should be 4,5. The naive solution is similar to the previous solution. Use a hash table to keep track of the frequencies and find the elements that occur an odd number of times. The algorithm has a Time and Space Complexity of O(n). Say those two required numbers are a and b If you remember the previous post, we used the XOR over all the elements to find the required element. If we do the same here, we get a value xor which is actually a ^ b. So how can we use this? We know that a and b are different, so their xor is not zero. Infact their XOR value has its bit set for all its dissimilar bits in both a and b. (eg.  1101 ^ 0110 = 0011). It's important to notice ...

Word ladder is a word game invented by Lewis Carroll. A word ladder puzzle begins with two words, and to solve the puzzle one must find a chain of other words to link the two, in which two adjacent words (that is, words in successive steps) differ by one letter. Eg. SPORT <-> SHORT Source: Wikipedia If you've followed my previous Dijkstra's Shortest Path Algorithm Tutorial, you'll be able to solve this challenge with minimum effort. Essentially, we create a graph where each word is a vertex and there exists an edge if two words differ by a single character. To find the word ladder is basically running any shortest path algorithm. You could also use a Breadth First Search. Some important observations The length of the source and destination words must be the same for a path to exist. The path from source to destination  can only contain words of the same length. So we can prune off the rest of the dictionary. The graph is undirected. Here's my ...

Problem : Given an array A of integers, maximize A[j] - A[i] such that 0 <= i < j < len(A). A very interesting problem, as always lets begin with a naive solution. Clearly, the solution has quadratic time complexity. Now, step back and look at the solution. Essentially what we are doing is iterating over the array, splitting the array into two parts. From the first part we always pick the lowest element, (clearly since that will give us the maximum difference). Since we already know the minimum element we encountered, we simply need to check if the difference with the new element improves upon the earlier solution. This idea can be implemented in Linear Time. Here's how. Update : So I just discovered this problem is called the Single Sell Profit problem. It's been discussed quite thoroughly by templatetypedef here . It includes 4 solutions (including this one).

Here's  Part 1  and  Part 2 And now for the third and final part of the tutorial. We'll be implementing the actual algorithm here. But before we get started, let's go over some theory. Dijkstra's Shortest Path Algorithm, (V - Number of Vertices, E - Number of Edges) Applies to both Directed graph and Undirected graphs. Greedy Algorithm. Always picks the local minimum to extend it's solution. Uses Dynamic Programming. Stores solutions from source to every other vertex on the shortest path to the destination. Edges cannot be negative. Original Implementation by Dijkstra was O(V 2 ) since it did not use a Minimum Priority Queue. Tarjan & Fredman introduced the modern version of the algorithm using a Fibonacci Heap to pick the vertex closest to the source. The Complexity thus became O(E + V logV).  Using a Binary Heap instead of a Fibonacci Heap increases the complexity to  O( (E+V) log V). Variations. There are two variants of the algorithm, t...

This is an experimental post. I'm trying out Scarky.com . Seems promising, but we can't an create account and manage challenges. Apparently, I have to save this secret URL if I want to edit a challenge. Very inconvenient! :( I've created a simple programming challenge for my readers. If it's a hit, expect more.