Ronzii's Blog

Just your average geek's blog

Spiral Order Traversal in a Tree

void iterativeSpiralTraversal(TreeNode* root)
{
    stack<TreeNode*> currentLevel, nextLevel;
    currentLevel.push(root);
    bool direction = 1;
    while(!currentLevel.empty())
    {
        TreeNode* current = currentLevel.top();
        currentLevel.pop();
        if(current)
        {
            cout<<current->value<<" ";
            if(direction)
            {
                if(current->left)
                    nextLevel.push(current->left);
                if(current->right)
                    nextLevel.push(current->right);
            }
            else
            {
                if(current->right)
                    nextLevel.push(current->right);
                if(current->left)
                    nextLevel.push(current->left);
            }
        }
        if(currentLevel.empty())
        {
            cout<<endl;
            swap(currentLevel,nextLevel);
            direction = !direction;
        }
    }
}

April 1, 2012 Posted by | C++, Data Structures | , , , , | 1 Comment

Maximum Sum in a Tree

#include <iostream>
#include <climits>
using namespace std;
struct node
{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node TreeNode;
int treeMin = INT_MAX;
TreeNode* createNode(int n)
{
    TreeNode *temp = new TreeNode;
    temp->value = n;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int max5(int a, int b,int c, int d, int e)
{
    return max(a,max(b,max(c,max(d,e))));
}
int maxSumTree(TreeNode* current, int* sum)
{
    if(current==NULL)
    {
        *sum = treeMin;
        return treeMin;
    }
    else
    {
        int ls = INT_MIN,rs = INT_MIN;
        int l = maxSumTree(current->left,&ls);
        int r = maxSumTree(current->right,&rs);
        *sum = max5(*sum,current->value, ls+rs+current->value,ls+current->value,rs+current->value);
        return max(*sum,max(l,r));
    }
}

void binaryTreeMin(TreeNode* current)
{
    if(current==NULL)   return;
    binaryTreeMin(current->left);
    if(treeMin>current->value)
        treeMin = current->value;
    binaryTreeMin(current->right);
}
int main()
{
    TreeNode* root = createNode(17);
    root->left = createNode(15);
    root->right = createNode(-20);
    root->left->left  = createNode(13);
    root->left->left->left  = createNode(-15);
    root->left->left->right  = createNode(-7);
    root->right->left  = createNode(50);
    root->right->right  = createNode(-72);
    binaryTreeMin(root);
    int sum = treeMin;
    cout<<maxSumTree(root,&sum);
    return 0;
}

March 31, 2012 Posted by | C++ | , , , , , | 1 Comment

Quick Select

Find the kth smallest element of an array using kth order statistic

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int partition(int a[], int left, int right)
{
    int last = left;
    int key = a[left];
    for(int j=left+1; j<=right; j++)
    {
        if(a[j]<key)
        {
            last++;
            swap(a[last],a[j]);
        }
    }
    swap(a[left],a[last]);
    return last;
}
int findRank(int a[],int left, int right, int rank)
{
    int leftEnd  = partition(a,left,right);
    int leftSize = leftEnd - left + 1;
    if(leftSize==rank+1)
        return a[leftEnd];
    else if(rank<leftSize)
        return findRank(a,left,leftEnd-1,rank);
    else
        return findRank(a,leftEnd+1,right,rank-leftSize);
}
int main()
{
    srand(time(NULL));
    int a[] = {3,4,1,7,8,9,34};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
        cout<<findRank(a,0,n-1,i)<<" ";
    return 0;
}

March 31, 2012 Posted by | C++ | , , , | Leave a comment

Median in a stream of numbers

The brute force algorithm uses a vector and maintains a sorted list. In this case the complexity of adding an element is O(n). Therefore, for n elements, the worst case is O(n^2).
Instead we maintain 2 priority queues i.e minHeap, maxHeap. We keep adding the numbers in both such that the number of elements in the maxheap is at max 1 greater than number of elements in the minHeap. Maintaining this constraint, allows us to get the median in O(1) time. Also, insertion becomes O(logn). Therefore, overall complexity is O(nlogn).

#include <iostream>
#include <queue>
using namespace std;
void insert(priority_queue<int> &maxHeap,priority_queue<int,vector<int>, greater<int> > &minHeap, int n)
{
    if(maxHeap.size()==minHeap.size())
    {
        if(!minHeap.empty() && n>minHeap.top())
        {
            maxHeap.push(minHeap.top());
            minHeap.pop();
            minHeap.push(n);
        }
        else
            maxHeap.push(n);
    }
    else
    {
        if(n<maxHeap.top())
        {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(n);
        }
        else
            minHeap.push(n);
    }
}
double getMedian(priority_queue<int> maxHeap,priority_queue<int,vector<int>, greater<int> > minHeap)
{
    int a = minHeap.size();
    int b = maxHeap.size();
    if(a==0 && b==0) return -1;
    if((a+b)%2==0)
        return (double)(minHeap.top() + maxHeap.top())/2;
    else
        return maxHeap.top();
}
int main()
{
    priority_queue<int> maxHeap;
    priority_queue<int,vector<int>, greater<int> > minHeap;
    int a[] = {7,11,17,8,19,2,3,15,16};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
    {
        insert(maxHeap,minHeap,a[i]);
        cout<<getMedian(maxHeap,minHeap)<<endl;
    }
    return 0;
}

March 30, 2012 Posted by | C++ | , , , | 1 Comment

Modular Exponentiation

long long modulo(long long a,long long b,long long c)
{
    long long result=1;
    for(int i=0; i<b; i++)
    {
        result = result*a;
        result = result%c;
    }
    return result;
}

long long mulmod(long long a, long long b , long long c)
{
    long long x=0,y=a%c;
    while(b>0)
    {
        if(b & 1)
        {
            x = (x+y)%c;
        }
        y=(y*2)%c;
        b>>=1;
    }
    return x%c;
}
long long modulo2(long long a,long long b,long long c)
{
    long long y=a,x=1;
    printf("%lld %lld %lld\n",b,x,y);
    while(b>0)
    {
        if(b & 1)
        {
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b>>=1;
    }
    return x%c;
}

March 30, 2012 Posted by | C++ | , , , | Leave a comment

Maximum Sum Submatrix

Method 1 : 

This is in O(n^4) using dynamic programming. A huge improvement over the naive o(n^6), where the complexity to calculate the sum of a sub matrix was O(n^2). This time has been reduced to O(1) using DP.

#include <iostream>
#include <climits>
#define N 3
using namespace std;
int sumMatrix[N][N];
void preComputeMatrix(int a[][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(i==0 && j==0)
                sumMatrix[i][j] = a[i][j];
            else if(i==0)
                sumMatrix[i][j]+=sumMatrix[i][j-1] + a[i][j];
            else if(j==0)
                sumMatrix[i][j]+=sumMatrix[i-1][j] + a[i][j];
            else
                sumMatrix[i][j]+=sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1] + a[i][j];
        }
    }
}
int computeSum(int a[][N],int i1,int i2,int j1,int j2)
{
    if(i1==0 && j1==0)
        return sumMatrix[i2][j2];
    else if(i1==0)
        return sumMatrix[i2][j2] - sumMatrix[i2][j1-1];
    else if(j1==0)
        return sumMatrix[i2][j2] - sumMatrix[i1-1][j2];
    else
        return sumMatrix[i2][j2] - sumMatrix[i2][j1-1]- sumMatrix[i1-1][j2] + sumMatrix[i1-1][j1-1];
}
int getMaxMatrix(int a[][N])
{
    int maxSum = INT_MIN;
    for(int row1=0; row1<N; row1++)
    {
        for(int row2=row1; row2<N; row2++)
        {
            for(int col1=0; col1<N; col1++)
            {
                for(int col2=col1; col2<N; col2++)
                {
                    maxSum = max(maxSum,computeSum(a,row1,row2,col1,col2));
                }
            }
        }
    }
    return maxSum;
}
int main( void )
{
    int a[N][N] = {{-1,-2,-3},{-10,-5,-15},{6,-8,-20}};
    preComputeMatrix(a);
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
            cout<<sumMatrix[i][j]<<" ";
        cout<<endl;
    }
    cout<<getMaxMatrix(a);
    return 0;
}

Method 2
Kadane’s Algorithm 2D. Overall complexity is O(n^3)
Check out http://www.algorithmist.com/index.php/UVa_108 for the algorithm

#include <iostream>
#include <climits>
using namespace std;
int a[101][101];
int kadane2D(int n)
{
    int *columnSum = new int[n];
    int s=INT_MIN,S=INT_MIN,t;
    for(int row = 0; row<n; row++)
    {
        for(int i=0; i<n; i++) columnSum[i] = 0;
        for(int x = row; x<n; x++)
        {
            s = INT_MIN;
            t = 0;
            for(int i=0; i<n; i++)
            {
                columnSum[i]+=a[x][i];
                t+=columnSum[i];
                if(t>s)
                    s = t;
                if(t<0)
                    t = 0;
            }
            if(s>S)
                S = s;
        }
    }
    delete [] columnSum;
    return S;
}
int main( void )
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    cout<<kadane2D(n)<<endl;
    return 0;
}

March 16, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment