Category Archives: Algorithms

Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination.

For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total.

Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count which takes in the parameter amount N, and the index of current denomination, we can have pseudo code like this

Count(N, index)

  • Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominations
  • Base case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none.
  • Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term), or take the current denomination(second term) and recurse accordingly.

Since this recursive method solves the same problem multiple times, we can think of a dynamic programming solution for this problem. In dynamic programming, we solve the smaller sub problems first and use their results in solving bigger sub problems. We store the results in a table. Lets create a table[N+1][M] where N is the amount, and M is the denomination count.

  • table[0][j] = 1, Only one way to make 0.
  • table[i][0] = 1 if N is divisible by D[0], otherwise 0
  • table[i][j] = table[i][j-1] if D[j] > i
    = table[i][j-1] + table[i- D[j]][j]

Here is the Java code which implements the above approach.

Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence?

For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3.

This is a straight forward implementation problem (appeared on Codeforces). Following is an implementation of O(n) algorithm.

Check if an array has a sub-array with given sum

Given an array of numbers and a sum, how to check if there is any sub-array with the given sum.

For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is Yes. If we want to check for sum 14, we can not find a sub-array with that sum.

A simple method is to check if a sum can be found for all possible sub-arrays. This solution takes O(n3) time.

A more efficient method is the sliding window method. We maintain two indices, one indicates the beginning of the window, and the other indicates the ending of the window.

While iterating through the elements, we increment the end-index as long as the current sum is less than or equal to the target. If we find the target sum, then we are done. If we exceed the target sum, we deduct the beginning elements from the current sum until it is less than or equal to target sum.

This approach takes O(n) time. Here is the C++ code.

Decreasing string

Given a number K, Find the shortest and smallest string  which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed.

For example consider K = 1

“ba” is the shortest and smallest string possible. There are other possibilities like “ca”, “bad”. But “ca” cannot be the answer because “ba” is alphabetically smaller than “ca”. Similarly “bad” cannot be the answer because it’s length is greater than “ba”.

This problem is from Codechef. If you want to solve it, follow the problem link.

Here is how we can solve the problem. Let us look at some of the answers.

K = 1, “ba”

K = 2, “cba”

K = 3, “dcba”…

If you observe the pattern, this is simply reverse order of alphabets. We can happily reverse the alphabets if K < 26. What happens if K = 26? The pattern repeats, and the repeating pattern should be added in the beginning.

So for K = 26, the answer is “bazyxwvutsrqponmlkjihgfedcba”.

Here is the Python implementation of this algorithm.

Minimum difference between two elements in array

Given an array, how do we find the minimum difference between any two elements in that array?

For example consider the array [56, 18, 89, 24, 10], the minimum difference is 6 (between 18, and 24).

A straight forward method to find the minimum difference between any two pairs is to iterate through each possible pair and find the minimum difference. But this method takes O(n2) time.

This can be solved in O(n log n) time if we sort the array. Since the closest elements are always adjacent to each other in a sorted array, we can find the minimum difference in one iteration. Here is the C++ code for the same.

Up down array

Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]

For example consider the array A =[6, 9, 36, 24, 42]

The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.

We can solve this problem in a simpler way by sorting the array first. Considering the same example as above

Sorted(A) = [6, 9, 24, 36, 42]

Method1: Start from the second element and swap the elements in pairs

6, 9<-> 24, 36<-> 42 ===>  6, 24, 9, 42, 36

Method2: Interleave the elements of the second half into the first half in reverse order

It becomes 6, 42, 9, 36, 24

Linear search

Given an array of numbers, how do we search for a given number?

For example, given an array [6, 50, 24, 36, 42], the number 36 is present at the index 3 starting with 0. The number 17 is not present any where.

The simplest algorithm to solve this problem is to check each element of the array starting from the first element and search till the target element is found or we reach the end of the array. This most fundamental algorithm is called the linear search.

Here is the pseudo code for the same.

ind = 0 
while ind < length(Array)
   if Array[ind] == target     
      print ind
      break   
   ind = ind + 1 
print -1

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
  • One array stores the maximum element seen so far from the left.
  • Second array stores minimum element seen so far from the right

For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4] 

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above. 

Ambiguous permutations

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index ‘i’ indicates that the number ‘i’ is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

Following is the C++ code. It runs in O(n) time and O(n) space.