Category Archives: algorithms

Print matrix elements in spiral order

This is one of the common interview questions used to test how cleanly you can code without ending up in knots handling the indexes.

Problem statement:

Given an N x M matrix, print the elements in spiral order.
Example for matrix:
[
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14]
]

Output would be 1 2 3 4 5 10 14 13 12 11 6 7 8 9

Solution:
There could be various ways of solving this. I am sharing the approach I used to solve it.
The idea is to keep 4 indexes to track the matrix boundaries, start with a direction value pointing to right initially and then once it hits the right most boundary, change direction and update the relevant boundary value.
For example, when we are going in right direction, and we hit the boundary, we need to go clockwise and change to go down next and we also need to increment the xMin value as we have covered the row corresponding to that xMin value.

public static void printSpiral(int[][] matrix, int n, int m) {
    int xMin = 0, yMin = 0, xMax = n - 1, yMax = m -1;
    // Current co-ordinates
    int x = 0, y = 0;
    char direction = 'r';
    while (xMin <= xMax && yMin <= yMax) {
        // Get the next direction
        switch(direction) {
        case 'd': if (x == xMax) {direction = 'l'; yMax--;} break;
        case 'r': if (y == yMax) {direction = 'd'; xMin++;} break;
        case 'u': if (x == xMin) {direction = 'r'; yMin++;} break;
        case 'l': if (y == yMin) {direction = 'u'; xMax--;} break;
        }
        // Print the current co-ordinates
        System.out.print(matrix[x][y] + " ");
        // Update the current co-ordinates
        switch(direction) {
        case 'd': x++; break;
        case 'r': y++; break;
        case 'u': x--; break;
        case 'l': y--; break;
        }
    }
}

Disproving Professor Bunyan's hypothesis on Binary search tree

Question (from Introduction to Algorithms by Cormen et al):

Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a ∈ Ab ∈ B, and c ∈ C must satisfy a ≤ b ≤ c. Give a smallest possible counterexample to the professor's claim.

I came across this question and was really wondering how do I find a counter-example to this claim which appeared right for my few initial trees that I made. After a few attempts, I was able to give a counterexample. I would suggest that do try a few more times, before you give up and peek into the solution.

Solution

Non-recursive tree traversal in O(n) using constant space

Question (from Introduction to Algorithms by Cormen et al):

Write an O(n)-time non-recursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

Each node has left, child and parent pointers.

Solution