Problem
Given an Array A[], find the maximum j - i such that A[j] > A[i].
For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1)
Time Complexity should be less then O(n^2)
Solution
1. Build a tree containing value and index
2. When inserting a right leaf, update its j
3. Compare the index difference of i and j, which can be done in the process of building tree
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the maximum j - i such that A[j] > A[i]
Created Date : 24-July-2013
Last Modified :
===========================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
typedef struct binTree
{
int key;
int indexI;
int indexJ;
struct binTree* left;
struct binTree* right;
}BinTree;
BinTree* NewBinTreeNode(int value, int indexI)
{
BinTree *node = new BinTree;
node->key = value;
node->indexI = indexI;
node->indexJ = -1;
node->left = NULL;
node->right = NULL;
return node;
}
void AddBinTreeNode(BinTree **root, int value, int indexI)
{
if(*root == NULL){
*root = NewBinTreeNode(value, indexI);
}
else{
if(value < (*root)->key){
if((*root)->left == NULL){
(*root)->left = NewBinTreeNode(value, indexI);
}
else{
AddBinTreeNode(&((*root)->left), value, indexI);
}
}
else{
if((*root)->right == NULL){
(*root)->right = NewBinTreeNode(value, indexI);
(*root)->indexJ = indexI;
}
else{
AddBinTreeNode(&((*root)->right), value, indexI);
(*root)->indexJ = indexI;
}
}
}
}
void TraverseTree(BinTree *root, int& indexI, int& indexJ)
{
if(root == NULL) return;
if(indexJ - indexI < root->indexJ - root->indexI){
indexJ = root->indexJ;
indexI = root->indexI;
}
if(root->left != NULL){
TraverseTree(root->left, indexI, indexJ);
}
if(root->right != NULL){
TraverseTree(root->right, indexI, indexJ);
}
}
void DelTree(BinTree *root)
{
if(root == NULL) return;
DelTree(root->left);
DelTree(root->right);
delete root;
}
void DoTest(int* arr, int len)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
BinTree* root = NULL;
for(int i = 0; i < len; ++i)
{
AddBinTreeNode(&root, arr[i], i);
}
int indexI = 0;
int indexJ = -1;
TraverseTree(root, indexI, indexJ);
if(indexJ != -1){
cout << "The max is " << indexJ - indexI;
cout << " (j = " << indexJ;
cout << ",i= " << indexI << ")" << endl;
}
else{
cout << "The array is in descendant order" << endl;
cout << "Nothing is found" << endl;
}
DelTree(root);
cout << "----------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = { 34,8,10,3,2,80,30,33,1};
DoTest(arr, sizeof(arr)/ sizeof(arr[0]));
int arr1[] = { 1,2,3,4,5,6,7,8,9};
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]));
int arr2[] = { 91,82,73,64,55,46,37,28,19};
DoTest(arr2, sizeof(arr2)/ sizeof(arr2[0]));
return 0;
}
Output
The array is
34 8 10 3 2 80 30 33 1
The max is 6 (j = 7,i= 1)
----------------------------------
The array is
1 2 3 4 5 6 7 8 9
The max is 8 (j = 8,i= 0)
----------------------------------
The array is
91 82 73 64 55 46 37 28 19
The array is in descendant order
Nothing is found
----------------------------------
Press any key to continue . . .