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 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 ...

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).

Problem : A Sorted Array is rotated by a certain number of elements, find the point of rotation.   Example, For [3,4,5,1,2] , since [1,2] was rotated to the back, point of rotation is 3. And of course, for a sorted array the point of rotation can be assumed 0. Naive Solution: This is pretty obvious Linear Solution, simply scan the array for a pair a[i] > a[i+1]. If we find it, i is the point of rotation,   if there's no such pair, then i = 0 clearly. Time Complexity : O(n) Binary Search Variant:  Using a variation of Binary Search method, we can find the rotation point in O(logn) steps. At each iteration we compare the middle element of the list with the right (or left) element. For a rotated array, arr[left] > arr[right] , so every time we pick a middle element, the point of rotation can lie on either side of mid . If arr[mid] > arr[right] , it means the rotation point is in the second half of the array. So we move left to mid...

Problem : Implement a stack with push() , pop() and a min() (which returns the minimum element in the stack). All operations should be O(1). Another popular question, I've searched around a lot came across many answers, but only one had completeness. It's important to note that with the stack you don't have random access to the contents of the stack when implementing your solution. The solution I'm describing involves using 2 stacks, one is to store the data elements themselves ( mainstack ) and the other to store minimum values, which i'll refer to as minstack. Now we can have 2 parallel stacks where we push and pop on the minstack along with the mainstack, keeping track of the minimum value of course. But we can optimize this further. We only need to push values on the minimum stack only when you push a value on the main stack that is less than or equal to the current top element of the minstack. Here's are the two stacks after pushing 67,44,20,77,99,1...

Problem : Given an array of integers in strictly increasing order (no duplicates), find the first number not present in the array. Eg. [11,12,13,25,37,49] The output should be 14. Seems simple enough? Let's go with our intuition first and use a naive algorithm. Time Complexity : O(n) Notice, if we don't have any gaps, say [11,12,13,14,15] then the upper bound of the array is equal to the highest - lowest element in the array. (4 = 15 - 11). So we can check if there is a gap simply by checking if high - low == arr[high] - arr[low] Let's be clever about this fact and solve this in O(logn). We use our trusty Binary Search but instead of "finding" an element we're going to partition the array into two halves. We first check if the First Half is "complete", if it is, we find the gap in the second half else we check the first half. We keep doing this till we have just 2 elements left (which is trivial to solve). Here's a recursive algorith...

Problem : Given an array of integers of odd length such that each element is repeated twice except for one. Find the non-repeating element. Eg. For array [3,2,1,5,1,2,3] the solution is 5. A tiny variation of the question which doesn't really change the answer is as follows. Problem : Given an array of integers of odd length such that each element is repeated even number of times except for one element. Eg. For array [1,5,5,1,2,2,4,4,4] the solution is 4. Let's begin with the naive solution, we use a Hash Table to keep track of the frequencies of my each element in the array. Finally, we find the element in the Hash Table with the odd frequency which is the solution required. The space and time complexity is O(n). We'll try and reduce the space complexity. This is one of those questions which will be solved using our trusty Xor operator. You should know X ^ X = 0 and also Xor is Commutative and associative. ie X ^ Y is Y ^ X. Therefore, (X ^ Y) ^ X is ...