Bidirectional Search

Hello people! In this post we will talk about Bidirectional Search, a powerful search strategy which can be used if you have a goal directed agent in a (possibly infinite) search space. The idea behind Bidirectional search is to run two simultaneous searches, one forward from the source state and the other backward from the goal, hoping that the two searches meet somewhere in the middle.

In this post we will talk about Bidirectional Breadth First Search, where we apply BFS from the source and goal simultaneously until search routes intersect. Visually, the way regular BFS would progress would be something like this –

Regular BFS Theory of ProgrammingBut if we applied BFS simultaneously from source (S) and goal (G), visually it would look something like this –

Bidirectional search visualisation Theor of ProgarmmingWe can already start to seem some improvement as the number of vertices visited would be lesser.

In terms of complexity, if branching factor is b, and distance from source to goal is d, then, BFS would take O(bd), but Bidirectional search would take O(bd/2 + bd/2) ⇒ O(bd/2), which is quite better than O(bd). So in many cases a bidirectional search is faster as the amount of exploration done is lesser.

Properties of Bidirectional search

  • Our goal in Bidirectional search is to find a path from source to goal.
  • We can use any search algorithm on both sides, Bidirectional search is more of a strategy than a fixed algorithm. Using BFS on both sides is the most popular option as it guarantees an optimal path.
  • Bidirectional search must be used only when your goal is well defined. Eg. for a Rubik’s cube, your goal is to fill each side with one color, which is your goal and your current configuration of cube is your source state. We could use Bidirectional search in this scenario. But in chess, your goal is to checkmate the other player, but a checkmate can happen in thousands of ways. Bidirectional search isn’t feasible in chess.
  • Bidirectional search using BFS needs the edge weights to be same or non-existent. So usually Bidirectional BFS is used in undirected unweighted graphs.

Code

Writing the code for Bidirectional BFS is easier if you have already written the code for Breadth First Search using queue. Basically, all the variables we used in BFS get doubled here. That is, for Bidirectional BFS, we will use 2 queues and 2 parent arrays. One set will be used for applying BFS from source and other set will be used for applying BFS from goal. So we can call them –

  • sourceParent – the parent array to construct paths for BFS from source vertex.
  • sourceQueue – the queue for BFS from source vertex.
  • goalParent – the parent array to construct paths for BFS from goal vertex.
  • goalQueue – the queue for BFS from goal vertex.

Although we are using a separate set of variables for BFS from source and goal, the way in which they operate will be the same, i.e., the steps like picking first element in queue, enqueuing its adjacent vertices, etc. We can put that logic in a separate method called BFSExplore().

So how will we know if the BFS from source and goal have an intersecting node? After expanding a layer on either side, we will check if a vertex has been marked as visited in both of the BFS. If yes, then that is our intersection node. Recall, that we can check if a vertex has been visited if its parent value has been set.

Now the only thing left is to return the final path. There’s no genius logic for this, just do it in a brute force way 😛 . Add all vertices from source → intersecting_vertex using sourceParent into a collection. Then add all the vertices from intersecting_vertex → goal using goalParent into the same collection. Be careful, don’t add the intersecting_vertex twice in the path 😉

I have given you all the theory you need to write the code for Bidirectional BFS. It may take some time, but do try your best to write the code yourself. You can refer to my code below if you get stuck –

I hope this has given you a good understanding of Bidirectional search. Keep practicing! Happy coding! 😀

Iterative Deepening Depth First Search (IDDFS)

Hello people! In this post we will talk about another search algorithm Iterative deepening depth first search (IDDFS) or Iterative deepening search (IDS). This algorithm is used when you have a goal directed agent in an infinite search space (or search tree).

Why do Breadth First Search (BFS) and Depth First Search (DFS) fail in the case of an infinite search space?

  • In DFS, you would recursively look at a node’s adjacent vertex. DFS may not end in an infinite search space. Also, DFS may not find the shortest path to the goal. DFS needs O(d) space, where d is depth of search.
  • BFS consumes too much memory. BFS needs to store all the elements in the same level. In the case of a tree, the last level has N / 2 leaf nodes, the second last level has N / 4. So, BFS needs O(N) space.

Iterative deepening depth first search (IDDFS) is a hybrid of BFS and DFS. In IDDFS, we perform DFS up to a certain “limited depth,” and keep increasing this “limited depth” after every iteration.

Let us take an example to understand this –

Our starting node (A) is at a depth of 0. Our goal node (R) is at a depth of 4. The above example is a finite tree, but think of the above tree as an infinitely long tree and only up to depth = 4 is shown in the diagram.

As stated earlier, in IDDFS, we perform DFS up to a certain depth and keep incrementing this allowed depth. Performing DFS upto a certain allowed depth is called Depth Limited Search (DLS). As Depth Limited Search (DLS) is important for IDDFS, let us take time to understand it first.

Let us understand DLS, by performing DLS on the above example. In Depth Limited Search, we first set a constraint on how deep (or how far from root) will we go. Let’s say our limit (DEPTH) is 2. Now, in the above diagram, place your hand to cover the nodes at depth 3 and 4. Now, by looking at the rest of the nodes, can you tell the order in which a normal DFS would visit them? It would be as follows –

A B E F C G D H

Can you do it for DEPTH = {0, 1, 2, 3, 4} ? Just cover the nodes you don’t need with your hand and try to perform DFS in you mind. You should get answers like this –

DEPTH DLS traversal
0 A
1 A B C D
2 A B E F C G D H
3 A B E I F J K C G L D H M N
4 A B E I F J K O P C G L R D H M N S

Now that you have got an idea of Depth Limited Search, Iterative deepening depth first search is just one loop away! The pseudo-code for IDDFS is as below –

IDDFS(tree):
    for depth = 0 to infinity:
        if (DLS(tree, depth)):
            return true

    return false

Before you race off to code, here are a few things –

  • IDDFS is used to check if the goal is reachable from start node. So its return type is boolean.
  • IDDFS is only used to check, not return the path from start node to goal. So we don’t maintain anything like parent array (like in DFS).
  • IDDFS is meant to run DLS from 0 → ∞, but we will write our IDDFS program to run DLS from 0 → MAX_DEPTH. Because in real world we never run anything up to ∞.
  • First code the DLS method, then add the IDDFS method which calls the DLS method.
  • IDDFS is meant to run in an infinite space tree. So, you can use a binary tree if you want, but in my opinion using an N-ary tree makes more sense. So, in my code below I use N-ary tree, the code taken from my article on N-ary tree.

You should be capable of writing the code for Iterative deepening depth first search now. Try it, I’m sure you can 😉 You can refer to my code if you get stuck –

JavaOutput
A
   B
      E
         I
      F
         J
         K
            O
            P
   C
      G
         L
            R
   D
      H
         M
         N
            S
Depth = 0, DLS Traversal => A, 
Depth = 1, DLS Traversal => A, B, C, D, 
Depth = 2, DLS Traversal => A, B, E, F, C, G, D, H, 
Depth = 3, DLS Traversal => A, B, E, I, F, J, K, C, G, L, D, H, M, N, 
Goal node = R is not reachable at a depth of 3
Depth = 0, DLS Traversal => A, 
Depth = 1, DLS Traversal => A, B, C, D, 
Depth = 2, DLS Traversal => A, B, E, F, C, G, D, H, 
Depth = 3, DLS Traversal => A, B, E, I, F, J, K, C, G, L, D, H, M, N, 
Depth = 4, DLS Traversal => A, B, E, I, F, J, K, O, P, C, G, L, R, 
Goal node = R is reachable at a depth of 4

In the output, the tree is printed first, then the IDDFS traversals. Purposefully, I took the goal node as a node which is not reachable by depth = 3 but is reachable by depth = 4. As you have noticed from the output above, we visit the nodes at depth = 0 a lot, the nodes at depth = 2 a little fewer but we visit them multiple times too, and we visit the nodes at depth = DEPTH_MAX only once. This may seem inefficient, but it is actually not. This is because, there are very few nodes at depth = 0, but a lot of nodes at depth = DEPTH_MAX. If ‘d‘ is depth, and ‘b‘ is the branching factor in the search tree (this would be N for an N-ary tree), then mathematically –

Iterative deepening depth first search time complexity Theory of ProgrammingThe time complexity remains O(bd) but the constants are large, so IDDFS is slower than BFS and DFS (which also have time complexity of O(bd)).

Time complexity Space complexity
DFS O(bd) O(d)
BFS O(bd) O(bd)
IDDFS O(bd) O(bd)

Iterative deepening depth first search may not be directly used in practical applications but the technique of iteratively progressing your search in an infinite search space is pretty useful and can be applied in many AI applications.

Congrats, your AI just got better! Keep practicing! Happy coding! 😀

N-ary tree or K-way tree data structure

Hello people! In this post, we will talk about a generic tree data structure which is N-ary tree or also known as k-way tree. N-ary tree is defined as a rooted tree which has at most N children for any node. So, a binary tree is a special case of the N-ary tree, where N = 2. Example –

N-ary tree Theory of ProgrammingThe above example is a N-ary tree with N = 3. You can observe that each node has no more than 3 children.

In many scenarios, having a binary tree many not be enough as a situation can often lead to more than 2 situations. In such cases, we must form a N-ary tree of sufficiently large N.

Implementing N-ary tree using structures

Implementing N-ary tree is very simple. It is even more easy if you already know how to implement a Trie Tree. Now, in the case of binary tree, the node structure was like this –

class TreeNode {
    String label;
    Node leftChild, rightChild;
}

Having two references was enough for us then because we knew we would have at most 2 children. Now, we can have at most N children. How will you store a collection of N references? By using an array! In the case of Java, I’d like to use an ArrayList rather than an array. In the case of C++, I’d suggest you go for a C++ STL vector. So now our node structure will look like this –

class NaryTreeNode {
    String label;
    ArrayList<NaryTreeNode> children;
    int n;
}

Storing the value of N inside the node will enable us to put a restriction on the number of children. So we will add methods inside our newly formed NaryTreeNode class to manipulate the member variables. Some important methods would be –

  • addChild(child) – to add a child node.
  • getChildren() – to get all the child nodes.
  • getChild(index) – to get child at a certain index.
  • print(root) – to print the tree. (This can be a static method, where we just supply the root node).

Also, don’t forget to add a constructor to your class! Now you are all set to write the code for N-ary tree. Try to code it, this is something you should be able to code in 1-3 attempts. You can refer to my code below if you get stuck –

JavaOutput
    
Matter
   Pure
      Elements
         Metals
         Metalloids
         Non-metals
      Compounds
         Water
         Carbon dioxide
         Salt
   Mixture
      Homogeneous
         Air
         Vinegar
      Heterogeneous
         Colloids
         Suspensions

I have added a helper method for printing the tree so that the tree can be printed more legibly based on the depth of nodes. I have also modified the addChild() method a little. It only accepts the new child’s label as it’s N value can be deduced from the parent node. The code should be easy to understand. Do leave a comment if you have any doubts 🙂

Implementing N-ary tree using arrays

Remember you can implement a binary tree using arrays. Similarly, you can also implement an N-ary tree using arrays. It is very similar to how you would do it in the case of binary trees, so here the formula for computing child node and parent node changes.

Parent node Child node
Binary tree Parent node in binary tree Left child –
Left child in binary tree
Right Child –
Right child in binary tree
N-ary Tree Parent node in N-ary tree Cth child –
Child in an N-ary tree

Using the above table, you can find the parent and child node for a node at index i. Generally, I like to implement the tree using structures, but if you have a complete n-ary tree, then the array representation will you a better compact storage.

I hope this article was able to give you an idea of how to implement an N-ary tree. Keep practicing! Happy coding! 😀

Rotate matrix clockwise

Problem statement – Given an array of N rows and N columns (square matrix), rotate the matrix by 90° in clockwise direction.

Rotate matrix Theory of ProgrammingSolution – This is an implementation based problem, which means that when asked in an interview, the interviewer is mainly testing your skill to write a program which follows some set of rules. There are no tricky cases here but you might struggle in the interview if you don’t have the right approach.

For this problem, let us define a cycle like this –

Rotate matrix Theory of ProgrammingSo the cycle is a ring of elements which consists of mirroring row and column. We will solve this problem cycle-by-cycle, which means, we will rotate the 0th cycle, then the 1st cycle and so on.

Now our rotation will start from the upper left corner element. This element’s vertices (i, j) can be easily evaluated from the cycle number it is in.

Rotate matrix Theory of ProgrammingSo, if the upper left corner element of a cycle is in the cycle number c, then its position in the matrix will be (c, c). Now that we have defined one corner of our cycle, let us find the others. If n is the size of the matrix, can you find the indexes of other corners?

Rotate matrix Theory of ProgrammingOkay so n – 1 – c seems to be an important term, let us call it l (like last index).

Rotate matrix Theory of ProgrammingNow to rotate these values, we need to do –

  • int temp = arr[c][c];
  • arr[c][c] = arr[l][c];
  • arr[l][c] = arr[l][l];
  • arr[l][l] = arr[c][l];
  • arr[c][l] = temp;

Now, if we go to the next element of the ring –

Rotate matrix Theory of ProgrammingTo rotate these values, we need to do –

  • int temp = arr[c][c + 1];
  • arr[c][c + 1] = arr[l – 1][c];
  • arr[l – 1][c] = arr[l][l – 1];
  • arr[l][l – 1] = arr[l];
  • arr[c + 1][l] = temp;

Similarly, for the next item in the ring.

Rotate matrix Theory of ProgrammingWe see that the indices vary by 0, 1, 2, etc. This can be generalized into a loop variable, say i

Rotate matrix Theory of ProgrammingSo, for any matrix, number of cycles c will be from [0, … n / 2]. If you think about it even number sized matrices have n / 2 cycles. Odd number sized matrices have n / 2 + 1 cycles, but the inner-most cycle would be a single integer which doesn’t need to be touched.

Value of i will be from [0 … , l – c). Why? Because we need to increment i, until c + i < l. So i < l – c.

So you have two loops and inside them, we need to write those 5 statements which make the rotation. Simple isn’t it? Try to code it, you can refer to my code below if you get stuck.

Code

public static void rotate(int[][] arr) {
    int n = arr.length;

    for (int c = 0; c < n / 2; ++c) {
        int l = n - 1 - c;

        for (int i = 0; i < l - c; ++i) {
            int temp = arr;

            arr = arr[l - i];
            arr[l - i] = arr[l][l - i];
            arr[l][l - i] = arr[l];
            arr[l] = temp;
        }
    }
}

Keep practicing! Happy Coding! 😀

Print matrix in spiral order

Problem statement – Given a 2D array (or matrix) of N rows and M columns, print it in a spiral order. Example, for the below matrix –

int[] arr = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
            };

The output is –

1 2 3 6 9 8 7 4 5

Solution – When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn’t tough because it doesn’t have any corner cases, but it is quite tough to solve if you start over thinking.

Let us label the rows/columns which we must print –

Print matrix in spiral order Theory of ProgrammingSo, our top-most row is top, bottom-most row is bottom, left-most column is left and right-most column is right. As we keep printing elements of the matrix, we will bring them closer to each other. Initially –

  • top = 0
  • right = M – 1
  • bottom  = N – 1
  • left = 0

As per the arrow indication, in our top row, we will print elements from left to right. So the loop to print it will look something like –

for (int i = left; i <= right; ++i) {
    print arr[top][i];
}

++top;

As you have noticed, the ++top is to bring it towards the center. Similarly, for printing the right column –

for (int i = top; i <= bottom; ++i) {
    print arr[i][right];
}

--right;

Similarly, for printing the bottom row –

for (int i = right; i >= left; --i) {
    print arr[bottom][i];
}

--bottom;

Similarly, for printing the left column –

for (int i = bottom; i >= top; --i) {
    print arr[i][left];
}

++left;

Now all that’s left is to execute this printing in a proper order. We could have a control variable dir, which denotes the direction. If –

  • dir == 1, print top row
  • dir == 2, print right column
  • dir == 3, print bottom row
  • dir == 4, print left column

We must keep rotating the value of dir between 1, 2, 3, 4 as long as top ≤ bottom and left ≤ right. If you have understood the logic, you should be able to write the code easily. If you didn’t just go through the explanation once more, it is can be tricky 😛

Code

public static void printInSpiralOrder(final int[][] arr) {
    if (arr.length == 0 || arr[0].length == 0) {
        return;
    }

    int top = 0, bottom = arr.length - 1, left = 0, right = arr[0].length - 1;
    int dir = 1;

    while (top <= bottom && left <= right) {
        if (dir == 1) {    // left-right
            for (int i = left; i <= right; ++i) {
                System.out.print(arr[top][i] + " ");
            }

            ++top;
            dir = 2;
        } else if (dir == 2) {     // top-bottom
            for (int i = top; i <= bottom; ++i) {
                System.out.print(arr[i][right] + " ");
            }

            --right;
            dir = 3;
        } else if (dir == 3) {     // right-left
            for (int i = right; i >= left; --i) {
                System.out.print(arr[bottom][i] + " ");
            }

            --bottom;
            dir = 4;
        } else if (dir == 4) {     // bottom-up
            for (int i = bottom; i >= top; --i) {
                System.out.print(arr[i][left] + " ");
            }

            ++left;
            dir = 1;
        }
    }
}

Keep practicing! Happy Coding! 😀

Add one to digit array

Problem statement – Given a non-negative integer in the form of an array of digits, add one to digit array. The digits are stored such that the most significant digit is at the head of the list. Eg. –

    A = {1, 3, 5}, answer = {1, 3, 6}

Solution – When an interviewer asks questions like these, he is testing your implementation skills and you ability to discover the corner cases. The solution is simply to add 1 to the last digit and pass on the carry until the first digit. But there are a few cases to handle, like –

  • A = {2, 4, 9}, answer = {2, 5, 0}
  • A = {9, 9}, answer = {1, 0, 0}
  • A = {0, 0, 1, 9}, answer = {2, 0}
  • A = {0}, answer = {1}

If we have passed the carry value to the end of the array and we still have carry left, then that would be appended as the new most significant bit. The digit array may be having leading zeroes, you should trim them before proceeding to solve the problem. But don’t blindly trim all leading zeroes, you should also handle the case when we have just a 0.

This is a simple problem to code, if you are aware of all the corner cases. Try it on your own once. 🙂

Code

public ArrayList<Integer> plusOne(ArrayList<Integer> arr) {
    preprocessInput(arr);
    
    int carry = 1;
    
    for (int i = arr.size() - 1; i >= 0; --i) {
        if (carry == 0) {
            return arr;
        }
        
        int num = arr.get(i);
        
        num++;
        
        arr.set(i, num % 10);
        carry = num / 10;
    }
    
    if (carry == 1) {
        arr.add(0, carry);
    }
    
    return arr;
}

public void preprocessInput(ArrayList<Integer> arr) {
    while (arr.size() > 1) {
        if (arr.get(0) == 0) {
            arr.remove(0);
        } else {
            break;
        }
    }
}

Keep practicing! Happy Coding! 😀

Adjacency List with String vertices using C++ STL

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List using C++ STL where each vertex is a string instead of and integer. This code has been requested many times, so I decided to create a separate page for it. Some of the features of this code are –

  • The Adjacency List is an unordered map of list. Where each list item is a pair, from the utility header file. This pair stores two values, the destination vertex (string), (V2 in an edge V1 → V2) and the weight (integer) of the edge.
  • For adding an edge, all we have to do is to call push_back() function. Although it does not represent our addEdge() in the initial discussion where we had head insertion, it is tail insertion which is an O(1) insertion operation.
  • The vector representing the vertices is 1-indexed.
#include <iostream>
#include <string>
#include <unordered_map>
#include <list>

using namespace std;

int main()
{
    int vertices, edges, weight;
    string v1, v2;
     
    printf("Enter the Number of Vertices -\n");
    cin >> vertices;
     
    printf("Enter the Number of Edges -\n");
    cin >> edges;
     
    // Adjacency List is a map of <string, list>.
    // Where each element in the list is pair<string, int>
    // pair.first -> the edge's destination (string)
    // pair.second -> edge's weight
    unordered_map< string, list< pair<string, int> > > adjacencyList(vertices + 1);
     
    printf("Enter the Edges V1 -> V2, of weight W\n");
    for (int i = 1; i <= edges; ++i) {
        cin >> v1 >> v2 >> weight;
         
        // Adding Edge to the Directed Graph
        adjacencyList[v1].push_back(make_pair(v2, weight));
    }
    
    // Printing Adjacency List
    cout << endl << "The Adjacency List-" << endl;
    for (auto& value : adjacencyList) {
        string vertex = value.first;
        list< pair<string, int> > adjacentVertices = value.second;
        list< pair<string, int> >::iterator itr = adjacentVertices.begin();
        
        cout << "adjacencyList[" << vertex << "]";
         
        while (itr != adjacentVertices.end()) {
        	cout << " -> " << (*itr).first << " (" << (*itr).second << ")";
            ++itr;
        }
        
        cout << endl;
    }
	
    return 0;
}

Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! 😀

Minimax algorithm with Alpha-Beta Pruning

Hello people, in this post we will try to improve the performance of our Minimax algorithm by applying Alpha-Beta Pruning. Please read my post on Minimax algorithm if you haven’t already.

Alpha-beta pruning is based on the Branch and bound algorithm design paradigm, where we will generate uppermost and lowermost possible values to our optimal solution and using them, discard any decision which cannot possibly yield a better solution than the one we have so far.

Idea of Alpha-beta pruning

We will maintain two additional parameters α and β. α is the best score achievable by the max player so far and β is the best score achievable by the min player so far. These values will be passed down to recursion calls via arguments.

We will try to use α and β to prune our search tree by skipping choices which can’t possibly give us a better solution. Let us understand this with the help of an example. Look at the sketch below –

Minimax algorithm with alpha beta pruning Theory of ProgrammingLet us assume we have the above game tree formed by two agents (max and min) playing a hypothetical game. Here, the Max agent tries to maximize the score and Min agent tries to minimize the score. Now, for a normal Minimax algorithm, we would traverse all these nodes, but this time we will send the values of α and β.

The topmost Min node makes the first call. Initially, the values of α and β are null. Here val is the value which will be returned. Now what will happen next? Min has two possibilities above and the call goes to the first possibility, which is the first Max node in the above diagram. It passes on the values of α and β, which both happen to be null for the moment. What will Max do there?

Minimax algorithm with alpha beta pruning Theory of ProgrammingThe choices for Max are 2 and 4. Since Max always maximizes the score, it will choose 4. So we update the value to be returned to 4. Notice that the value of α = 4. α denotes the best possibility for Max so far. It doesn’t play a big role here, but you must have an idea on when to update α and β. Now, we return value 4 from the Max node.

Minimax algorithm with alpha beta pruning Theory of ProgrammingHmm, now the Min node sees that the first possible decision will give it a score of 4. Okay, so now β = 4. Remember, β is the best possible decision for Min node so far. Now what does Min do? It looks at the next possibility. It passes on values of α and β. α is anyway null, but β = 4.

Minimax algorithm with alpha beta pruning Theory of ProgrammingOkay, so the Max node receives the values of α and β. Now, α is null and β = 4. So Max node starts looking at all the possibilities one-by-one. The possibilities are 6 and 8.

Minimax algorithm with alpha beta pruning Theory of ProgrammingThis is important! Now, this is the case when Max has finished reading the first possibility which is 6. Remember, it hasn’t gone to the next possibility (which is 8) yet!

After reading 6, val = 6 and α = 6, because it is the best solution so far. Now, what if the values for the choices ahead returned a value lesser than 6? Then obviously Max would choose 6 since it is the highest. Okay, what if the values for the choices ahead returned a value greater than 6, say X? Then obviously Max would choose X, since it is greater than 6. But, even if it did, will it affect the decision of Min on top? No! Because between 4 and X, Min would obviously choose 4!

So no matter what the next value Max encounters, it cannot affect the decision of Min. How did Max node know Min already has a choice which yields 4? From the value of β!

Read the above case again and again if you didn’t understand it. If you’ve understood it then you’ve learned Minimax algorithm with alpha-beta pruning! 😉

So, we break further computation in Max, and return 6.

Minimax algorithm with alpha beta pruning Theory of ProgrammingSo we have managed to prune a node. This is a small example, but for a real-world scenario we would be able to prune a lot of nodes, especially when we hit the best solution earlier.

The pruning happens for these cases –

  • val ≥ β in a Max node
  • val ≤ α in a Min node

Now let’s try to write the pseudo-code for Minimax algorithm with alpha beta pruning. Before we do that, first try to write down the pseudo-code for a regular Minimax algorithm. If you could, that’s awesome! 😀 If not, take a look at the pseudo-code in my post on Minimax Algorithm, because I will only make slight modifications in that.

We know that pruning happens only in the above stated two cases. So the only modifications we need to make to our existing Minimax algorithm pseudo-code is that,

  • Add the parameters alpha and beta to the procedure.
  • Add the conditions to update alpha and beta.
  • Add conditions for pruning.

The final pseudo-code goes like this –

(score, move) maxTurn(game, depth, alpha, beta):
    if game is in terminal state:
        return (score(game, depth), none)
 
    max = (none, none)
 
    foreach emptySpace in game:
        game[emptySpace] = X
        currentMove = minTurn(game, depth + 1, alpha, beta)
         
        if currentMove.score > max.score:
            max = (currentMove.score, emptySpace)

        if currentMove.score >= beta:
            return max
        
        if currentMove.score > alpha:
            alpha = currentMove.score
 
        game[emptySpace] = none   // reverting change
 
    return max
 
(score, move) minTurn(game, depth, alpha, beta):
    if game is in terminal state:
        return (score(game, depth), none)
 
    min = (none, none)
 
    foreach emptySpace in game:
        game[emptySpace] = O
        currentMove = maxTurn(game, depth + 1, alpha, beta)
         
        if currentMove.score < min.score:
            min = (currentMove.score, emptySpace)

        if currentMove.score <= alpha:
            return min
        
        if currentMove.score < beta:
            beta = currentMove.score

        game[emptySpace] = none   // reverting change
 
    return min

So, now instead of 1 if condition, we have 3 if conditions in our methods. The order of the new conditions can be interchanged, I like to write it this way.

Now that you have the pseudo-code, can you use that to tell which nodes get pruned for the example below?

Minimax algorithm with alpha beta pruning Theory of ProgrammingTake 2 minutes, it is easy. When done, check your answers with mine –

Minimax algorithm with alpha beta pruning Theory of ProgrammingDid you get them right? If yes kudos! If not, you just have to try one more time. I’m sure you’ll get it! 🙂

Now you are more than capable of writing the code for Minimax algorithm with alpha beta pruning. It is just a matter of a few conditions if you have already written the code for Minimax algorithm. Try to code it, you can refer to my code if you get stuck (it is a modification of the code in my post on Minimax algorithm) –

Congratulations! You AI just got hell a lot faster! Keep practicing! Happy coding! 😀

First missing integer in an unsorted array

Problem statement – Given an unsorted integer array, find the first missing positive integer. Example,

  • If A = [-1, 4, 2, 3, 5], missing integer = 1.
  • If A = [1, 5, 2, 3, 4, 7], missing integer = 6.
  • If A = [-1, -2, -3, -4], missing integer = 1.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you make changes in the array such that you can mark which numbers in 1 to N are already present in the array?

Solution – This is a little difficult one, so pay attention! If you go through the problem statement carefully, your solution will be an integer between 1 to N + 1, where N is the size of the array. Why N + 1? If the array had all integers from 1 to N, then the missing integer would be N + 1!

Now that we know our solution will be an integer from 1 to N + 1, we need to come up with a mechanism to mark/flag the numbers in 1 to N + 1, which are already present in the array. If we could use O(N) space, then we could create a boolean array isPresent[] of size N + 1, and set isPresent[A[i]] = true. The solution would be something like this –

boolean[] isPresent = new boolean[N + 1];

for (int i = 0; i < A.length; ++i) {
    isPresent[A[i]] = true;
}

for (int i = 1; i < isPresent.length; ++i) {
    if (!isPresent[i]) {
        return i;
    }
}

return N + 1;

But since our solution should be O(1) in space, we need to do this marking in our input array itself. Can we take advantage of the fact that the indices of an array is a contiguous span of numbers from 1 to N? Yes!

We will do this by making numbers at certain indexes negative. The idea is that, let’s say, we have A[i] = 3, then we will make A[3] negative. So that, when we make another scan of the array A, and we see A[3] is negative, we know that 3 has occurred somewhere in the array. Read the previous sentence once more, let it sink in. Now let’s write it as a formula –

int value = A[i];
A[value] = -A[value];

Now the question is, what if A[i] is negative? Let’s handle that case in our newly born formula.

int value = Math.abs(A[i]);
A[value] = -A[value];

Now the question is, what if A[value] is already negative? Let’s handle that case in our formula –

int value = Math.abs(A[i]);
A[value] = -Math.abs(A[value]);

So we will apply this formula to all the elements in the array by iterating over the whole array. Now, we will make another iteration over the array. If at any index i, we get A[i] as positive, then it means that the integer i was not present in the input array, otherwise A[i] would have been negative! So integer i is our missing integer. Read the solution again if you didn’t understand it in the first reading (I didn’t either 😛 )

Before you race off to code, there are a couple of issues we must handle. Firstly, what if we have negative integers or integers greater than N in our array? We know that our solution will be an integer between 1 and N + 1, so any other integer is junk for us. So we can replace all of them with a constant, say a variable called FLAG. So, when we encounter them in our formula loop, we can ignore them. Now keep in mind that they might have become negative because of some other element in the array. So, in our formula loop, we must ignore elements with values FLAG and -FLAG.

Secondly, up until now, for the sake of simplicity we spoke in terms of 1 indexed arrays, but we know that in real code, we have 0 indexed arrays. I guess you can handle that 😉

Code

public class Solution {
	public int firstMissingPositive(ArrayList<Integer> a) {
	    final int N = a.size();     // size
	    // a dummy value to replace
	    // integers below 0 and above N
	    final int FLAG = N + 2; 
	    
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) <= 0 || a.get(i) > N) {
	            a.set(i, FLAG);
	        }
	    }
	    
	    // Our formula loop
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) == FLAG || a.get(i) == -FLAG) {
	            continue;
	        }
	        
	        int value = Math.abs(a.get(i));
	            
	        a.set(value - 1, -Math.abs(a.get(value - 1)));
	    }
	    
	    // Loop through collection. Whichever
	    // index holds a +ve integer is the answer
	    for (int i = 0; i < N; ++i) { if (a.get(i) > 0) {
	            return i + 1;
	        }
	    }
	    
	    // If the collection has all integers
	    // from 1 to N, then answer is N + 1
	    return N + 1;
	}
}

Maximum sum contiguous sub-array

Problem statement – Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array A[0, 1, 2 … N], we need to find a sub-array A[i, i + 1, i + 2, … j] such that the sum of elements in the sub-array is maximum.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you think of a solution which solves the problem in a single scan of the array?

Solution – This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane’s Algorithm. In this algorithm, we keep adding elements to a sum variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the sum variable becomes negative, we cast off the the sub-array seen so far and reset sum variable. The final answer will be the maximum of all the values which were stored in sum over all iterations.

Example – For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]

A[i] Sub-array sum Max sub-array maxSum
-2 [-2] 0 [-2] -2
1 [1] 1 [1] 1
-3 [-3] 0 [1] 1
4 [4] 4 [4] 4
-1 [4, -1] 3 [4] 4
2 [4, -1, 2] 5 [4, -1, 2] 5
1 [4, -1, 2, 1] 6 [4, -1, 2, 1] 6
-5 [-5] 3 [4, -1, 2, 1] 6
4 [-5, 4] 3 [4, -1, 2, 1] 6

Code

public class Solution {
	public int maxSubArray(List<Integer> a) {
	    int sum = 0;
	    int maxSum = Integer.MIN_VALUE;
	    
	    for (int i = 0; i < a.size(); ++i) {
	        if (sum + a.get(i) < 0) {
	            // Adding this element will make the current
	            // subarray sum negative, so don't add this element
	            // and start a new subarray with next element
	            sum = 0;
	        } else {
	            // Adding this element will increase the
	            // current subarray sum, so add this
	            // element to the current subarray
	            sum += a.get(i);
	        }
	        
	        // maxSum is the maximum of -
	        //
	        // 1. maxSum so far
	        // 2. if sum == 0, then a.get(i) which is proably a -ve number
	        // 3. if sum != 0, then sum of subarray so far
	        maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum);
	    }
	    
	    return maxSum;
	}
}

If you didn’t understand why we need the “sum == 0 ? a.get(i) : sum” condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you’d want to return the largest among the negative values. Now remember, sum variable doesn’t store negative values, so when it holds 0, we consider A[i] instead of sum. Give it a little thought, I’m sure you’ll understand it. If you need a more explanation, refer to my post on Kadane’s Algorithm.