Write a function which does zig-zag traverse of binary tree and prints out nodes.

All the header files which are needed

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>
    

Brings all the named entities from std namespace into current declarative region

using namespace std;
    

This is the node structure we use to store the values and form the binary tree. For the simplicity, we use int data type to store the node data.

struct node {
  int val;
  struct node *left;
  struct node *right;
};

    

It prints the vector contents for debug purpose.

void printVector(vector<node *> list)
{
  for (vector<node *>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    if (NULL != *i)
      cout << "[" << (*i)->val << "] -> ";
    else
      cout << "[EMPTY] -> ";
  }
  cout << "NULL" << endl;
}

    

The input vector has all the nodes of a certain level (or depth) in the given tree, stored from left to right. This function is capable of printing either in the same order as the vector is created or in reverse order.

void printLevels(vector<node *>& level, int count, int forward)
{
  
  if (1 == forward) { // Print vector as it is
    for(vector<node *>::iterator it = level.begin(); it != level.end(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  } else { // Print vector in reverse order
    for(vector<node *>::reverse_iterator it = level.rbegin(); it != level.rend(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  }
  cout << endl;
}
    

The main function to trave level by level.

void traverse(node *binaryTree, bool ziczac)
{
  string zz = ziczac? "True":"False";
  cout << "ZicZac: [" << zz << "]" << endl;
  
  int count = 1;             // Initial count for the ROOT node (Level 1)
  int countNext = 0;         // Node count in the Next Level
  int forward = 1;           // Decides how to print the list
  vector<node *> nodeList;   // Store nodes level-by-level
  node *tmp = NULL;          // Store the node pointer temporarily 

  // Push the ROOT
  nodeList.push_back(binaryTree);
  
  while (0 != count) {
    // Print the nodes from the current level
    printLevels(nodeList, count, forward);
    
    // Iterate the nodes from current level and get the nodes from
    // the next level
    countNext = 0;
    for (int i=0; i<count;){
      tmp = nodeList.front();

      // Remove the node which is getting processed
      nodeList.erase(nodeList.begin());

      // Node is NULL. Don't count the NULL nodes
      if (NULL == tmp) {
        nodeList.push_back(NULL);
        nodeList.push_back(NULL);
      } else {
        i++;
      
        // Check the left child node
        if (tmp->left) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->left);
        } else {
          nodeList.push_back(NULL);
        }
        
        // Check the right child node
        if (tmp->right) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->right);
        } else {
          nodeList.push_back(NULL);
        }
      }
    }

    // update the current with the level count from the next level
    count = countNext;
    
    if (true == ziczac) {
      // Toggle the way the level is getting printed
      forward = (forward ^ 0x1) & 0x1;
    }
  }
}
    

Read the file with the following format,
('|' is the delimitor)
   1
   2|3
   4|5| |7
   8|9|0|1| | |2|3

and create the binary tree

node *createBinaryTreeFromFile(string filename)
{
  node *binaryTree = NULL;
  vector<node *> nodeList;
  vector<node *> childNodeList;
  vector<string> stringList;
  string line;
  
  try {

    // Open the given file
    ifstream inFile (filename);

    while ( getline (inFile, line) )
    {
      // First Line => ROOT node
      if (NULL == binaryTree) {
        binaryTree = new node;
        binaryTree->val = stoi(line);
        binaryTree->right = NULL;
        binaryTree->left = NULL;
        nodeList.push_back(binaryTree);
      } else {
        stringList.clear();
        string::size_type prev_pos = 0, pos = 0;
        // Split the line with '|' delimitor 
        while( (pos = line.find('|', pos)) != string::npos )
        {
          std::string substring( line.substr(prev_pos, pos-prev_pos) );
          stringList.push_back(substring);
          prev_pos = ++pos;
        }
        string substring( line.substr(prev_pos, pos-prev_pos) ); // Last word
        stringList.push_back(substring);

        // Create the binary tree here (level by level)
        vector<string>::iterator itStringList = stringList.begin();
        while (!nodeList.empty()) {
          
          if (itStringList >= stringList.end())
            break;

          if (NULL == *(nodeList.begin())) {
            itStringList = itStringList + 2;
          } else {
            // Left Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->left = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }

            // Right Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->right = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }
          }
          
          // Remove the node which is getting processed
          nodeList.erase(nodeList.begin());
        }
      }
    }
    inFile.close();
  } catch (ifstream::failure e) {
    cerr << e.what() << endl;
  }

  // Print the tree
  traverse(binaryTree, false);
  
  return binaryTree;
}
    

Everything starts from here,

int main(int argc, char** argv)
{
  node *binaryTree = createBinaryTreeFromFile(argv[1]);
  traverse(binaryTree, true);
  return 0;
}

Bash - Few shortcuts to make our life easier

Navigate the cursor inside the current command statement
Ctrl + a	-	Start of the command
Ctrl + e	-	End of the command
Ctrl + f	-	Move to the next character
Ctrl + b	-	Move to the previous character
Alt + right_arrow	-	End of the current word or the next word
Alt + left_arrow	-	Start of the current word or the previous word
Delete
Ctrl + k	-	Delete from current cursor position to the end of the command
Ctrl + u	-	Delete from current cursor position to the start of the command
Ctrl + w	-	Delete one word before the cursor
Ctrl + h	-	Delete one character before the cursor (Backspace)
Ctrl + d	-	Delete the current character under the cursor
Search History
Ctrl + r	-	Find the command with the phrase you type.It searches the history as you type. For each consecutive hit "Ctrl + r", it finds the next match in the history and moves to the start of the history.
!!	-	Repeat the last command
!xyz	-	Find the latest command starting with xyz from the history and run it
!xyz:p	-	Print the latest command starting with xyz from the history
!$	-	Last argument of previous command
!*	-	All arguments of previous command
^abc^def	-	Replace abc with def in the previous command and run it
Process
$$	-	Gets the pid of the current bash/script
$!	-	Pid of the last background process
$?	-	Exit status of the last command

Given a max-heap represented as an array, return the kth largest element without modifying the heap.

  Here are all the header files included to make the compilation successful.
 

    
#include <iostream>
#include <vector>
#include <stack>

#include <math.h>
using namespace std;
 

    
  This is how we heapify the given array of elements.
  

#define SWAP(x,y) \
  x = x ^ y;      \
  y = x ^ y;      \
  x = x ^ y;      \

void siftDown(vector<int> &v, int start, int end)
{
  int root = start;

  while (root*2+1 <= end){
    int child = root*2+1;
    int swap = root;

    if (child <= end && v[swap] < v[child]) {
      swap = child;
    }
    if(child+1 <= end && v[swap] < v[child+1]) {
      swap = child+1;
    }

    if (swap != root) {
      SWAP(v[root], v[swap]);
      root = swap;
    } else {
      return;
    }
  }
}

void heapify(vector<int> &v, int count)
{

  int start = floor((count-2)/2);

  while (start >=0 ) {
    siftDown(v, start, count-1);
    start = start - 1;
  }
}

 

    
  We modify the stack functionality a little to maintain the element order in the stack with the incoming elements.
  

void insertToStack(vector<int> &v, stack<int> &s, int val)
{
  /* Temporary vector to keep the order from the stack */
  vector<int> tmp;

  /* Pop the elements till new value finds its place */
  while(!s.empty() && v[s.top()] > v[val]){
    tmp.insert(tmp.begin(), s.top());
    s.pop();
  }

  /* push the new value into the stack */
  s.push(val);

  /* Push all the elements in the same order 
     which are previously popped out */
  vector<int>::iterator it;
  for (it=tmp.begin(); it<tmp.end(); it++) {
    s.push(*it);
  }
}

 

    
  This function traverses the heap to find the Kth element in log time
  

int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
  /* If current element is smaller than the element in the stack,
     update the current element with the top of the stack and 
     push the current element into the stack*/
  if (!s.empty() && v[s.top()] > v[index]) {
    insertToStack(v, s, index);
    index = s.top();
  }

  if (pos == count) {
    /* If the count reaches pos, return the current element */
    return v[index];
  } else {
    int lchild = index*2+1;
    int rchild = lchild+1;

    /* Check if the current element has right child */
    if (rchild > v.size()-1) {
      
      /* Check if the current element has left child */
      if (lchild > v.size()-1) {
        
        /* The current element is the leaf node. Get the top of 
           the stack to proceed further */
        index = s.top();
        s.pop();
      } else {
        
        /* The current element has only left child. */
        if (s.empty() || v[lchild] > v[s.top()]) {
          index = lchild;
        } else {
          index = s.top();
          s.pop();
          insertToStack(v, s, lchild);
        }
      }
    } else {
      
      /* Find the max and min from the child nodes */
      int max = 0;
      int min = 0;
      if (v[lchild] > v[rchild]) {
        max = lchild;
        min = rchild;
      } else {
        min = lchild;
        max = rchild;
      }

      /* Find the highest element among the child nodes & the top
         of the stack, Update the current element with the highest 
         element and push the other two elements into the stack */
      if (s.empty()) {
        insertToStack(v, s, min);
        index = max;
      } else {
        int top = s.top();
        if (v[max] < v[top]) {
          index = top;
          s.pop();
          insertToStack(v, s, min);
          insertToStack(v, s, max);
        } else {
          index = max;
          if (v[min] > v[top]) {
            insertToStack(v, s, min);
          } else {
            s.pop();
            insertToStack(v, s, min);
            insertToStack(v, s, top);
          }
        }
      }
    }
    
    /* Call "find" recursively till "count" reaches "pos" */
    return find(v, s, index, pos, count+1);
  }
}

int findElement(vector<int> &v, int pos)
{
  /* Start with am empty stack */
  stack<int> s;
  return find(v, s, 0, pos, 1);
}
 

  You are NOT A FAN of recursion? Here you go,
 

@@ -1,5 +1,6 @@
 int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
 {
+  while (count <= v.size()) {
   /* If current element is smaller than the element in the stack,
      update the current element with the top of the stack and 
      push the current element into the stack*/
@@ -74,8 +75,7 @@
         }
       }
     }
-    
-    /* Call "find" recursively till "count" reaches "pos" */
-    return find(v, s, index, pos, count+1);
+    }
+    count++:
   }
 }
 

  Here is the main function
    

int main(int argc, char **argv)
{

  /* Store the inputs into a vector */
  vector<int> input;
  int total= stoi(argv[1]);
  for(int c=0; c<total; c++){
    input.insert(input.end(), stoi(argv[c+2]));
  }

  /* Print them */
  vector<int>::iterator it;
  cout << "     my vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl;

  /* Heapify the input vector */ 
  heapify(input, total);
  cout << "my heap vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl << endl;

  for (int count=1; count<=total; count++) {
    int ret = findElement(input, count);
    cout << "(" << count << "):  " << ret << endl;
  }
  return 0;
}

Output:

$ ./kthInHeap 4 10 6 9 1
     my vector contains: 10 6 9 1
my heap vector contains: 10 6 9 1

(1):  10
(2):  9
(3):  6
(4):  1


$ ./kthInHeap 7 5 6 1 3 8 9 2
     my vector contains: 5 6 1 3 8 9 2
my heap vector contains: 9 8 5 3 6 1 2

(1):  9
(2):  8
(3):  6
(4):  5
(5):  3
(6):  2
(7):  1


$ ./kthInHeap 8 6 5 3 1 8 7 2 4
     my vector contains: 6 5 3 1 8 7 2 4
my heap vector contains: 8 6 7 4 5 3 2 1

(1):  8
(2):  7
(3):  6
(4):  5
(5):  4
(6):  3
(7):  2
(8):  1

Reconstruct the itinerary in order

Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO]
please reconstruct the itinerary in order, 
[ CDG, MUC, LHR, SFO, SJC ]. 
Note: tickets can be represented as nodes

#!/usr/bin/env python

import sys

# Reads the given file which contains airline tickets
# and returns 2 hash,
#  * (1) with all the ticket info
#  * (2) wth the starting and ending points
def getTicketsFromFile(filename):
    lines = []

    # Read the file
    with open(filename, "r") as fp:
        lines = lines = fp.readlines()

    lines = map(lambda s: s.strip(), lines)

    tickets = {}
    points = {}
    for line in lines:
        if line !="":
            point = map(lambda s: s.strip(), line[1:-1].split(","))
            tickets[point[0]] = point[1]

            # create 2 nodes for each ticket (start, end) and
            # do this for all the tickets
            for p in point:
                try:
                    # Delete the key from the points if it exists to find the start and end
                    # points for the entire trip.
                    del points[p]
                except:
                    points[p] = ""

    # Find the starting point
    for k in points.keys():
        if k in tickets.keys():
            startPoint = k
            break
        
    return (tickets, startPoint)


if __name__ == "__main__":
    (tickets, startPoint) = getTicketsFromFile(sys.argv[1])

    # print the order
    point = startPoint
    while True:
        print point,
        
        try:
            point = tickets[point]
        except:
            break

Write a function that subtract two integer streams

You are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit.
For example, integer 2048 is represented in the stream as 8, 4, 0, 2. 

Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.

#include <stdio.h>

/* Subtracts two single digits, prints the reminder and returns 1(carry) if a<b */
int subtract(char c_a, char c_b)
{
  /* Convert the char to interger */
  int i_a = c_a - '0';
  int i_b = c_b - '0';
  int ret = 0;

  /* If a<b, increase 'a' by 10 and return 1(carry) to subtract it from 'a' of the next set */
  if (i_a < i_b) {
    i_a += 10;
    ret = 1;
  }
  
  printf ("%d", i_a - i_b);

  return ret;
}


int main(int agrc, char **argv)
{
  /* Get the two operand streams from input arguments */
  char *s_a = argv[1];
  char *s_b = argv[2];

  int carry_one = 0;
  
  /* Pass one char at a time from each input arguments to function subtract */
  while(*s_b != '\0'){
    /* Subtract carry_one from first operand before sending it to function subtract */
    carry_one = subtract(*s_a - carry_one, *s_b);
    s_a++;
    s_b++;
  }

  /* Print the remining digits from the first operand */
  while(*s_a != '\0'){
    printf("%c", *s_a - carry_one);
    s_a++;
    carry_one = 0;
  }
  printf("\n");
  
  return 0;
}

Output:

  $ ./str_subtract 00051 1005 | rev
  09999
  
  $ ./str_subtract 5 3 | rev
  2
  
  $ ./str_subtract 1234 1233 | rev
  1000

Find the conflicting appointments

#include <stdio.h>
#include <stdlib.h>

/* 
   Time interval format: yyymmddhhmm yyyymmddhhmm 

   Example Input:
   --------------
   4
   5 6
   1 9
   7 8
   2 10

   Process:
   --------

   Data Structure
   time_node to store the intervals
    ------------------------------
   | timestamp | is_start | index |
    ------------------------------

   Step 1:
   -------

   - stores the timestamps into an array
   
    -----------   -----------   -----------   -----------
   | 5 | 1 | 0 | | 6 | 0 | 0 | | 1 | 1 | 1 | | 9 | 0 | 1 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 2 | 1 | 3 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7

   Step 2:
   -------

   - Sort the array wrt the timestamp value

    -----------   -----------   -----------   -----------
   | 1 | 1 | 1 | | 2 | 1 | 3 | | 5 | 1 | 0 | | 6 | 0 | 0 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 9 | 0 | 1 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7
   
   Step 3:
   -------

     3.1 Push the index value to the index_list if it is the start of an interval
     3.2 Delete the index value from the index_list if it is the end of an interval
       3.2.1 add all the index values from the index_list to the conflict_list of the this interval
       3.2.2 add this interval index into the conflict_list of all the index values in the index_list
*/


/* Index to find parent and the childern */
#define LEFT(a) (2*(a+1) -1)
#define RIGHT(a) (2*(a+1))
#define PARENT(a) ((a-1)/2)

typedef enum boolean {
  FALSE = 0,
  TRUE = 1
} bool;

/* To store the calendar appointment intervals */
typedef struct time_node time_node;
struct time_node {
  unsigned long long timestamp;
  bool is_start;
  int index;
};

/* To store the conflicts */
typedef struct index_node index_node;
struct index_node {
  int index;
  index_node *next;
};

/* Swap function */
#define XORSWAP(a, b) ((a.timestamp)^=(b.timestamp),(b.timestamp)^=(a.timestamp),(a.timestamp)^=(b.timestamp), \
                         (a.is_start)^=(b.is_start),(b.is_start)^=(a.is_start),(a.is_start)^=(b.is_start), \
                         (a.index)^=(b.index),(b.index)^=(a.index),(a.index)^=(b.index))

/* Heapify */
void maxheapify (time_node *list, int count, int index)
{
  int left = LEFT (index);
  int right = RIGHT (index);
  
  int largest = index;
  
  if (left <= count-1 && list[left].timestamp > list[largest].timestamp)
    largest = left;
  if (right <= count-1 && list[right].timestamp > list[largest].timestamp)
    largest = right;
  
  if (largest != index)
  {
    XORSWAP (list[index], list[largest]);
    maxheapify (list, count, largest);
  }
}

/* Buids the heap */
void build_max_heap (time_node *list, int count)
{
  for (int i = (count-1)/2; i >= 0; i--)
  {
    maxheapify (list, count, i);
  }  
}

/* Sorts the intervals using heap sort */
void heap_sort (time_node *list, int count)
{
  build_max_heap (list, count);
  
  int tmp_count = count-1;
  for (int i = count-1; i > 0; i--)
  {
    XORSWAP (list[0], list[i]);
    maxheapify (list, i, 0);
  }
}

/* Adds the index node into the list */
bool add_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    *list = (index_node *) calloc (1, sizeof (index_node));
    if (NULL == *list)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      (*list)->index = index;
      (*list)->next = NULL;
    }
  }
  else
  {
    index_node *t = *list;
    
    while (NULL != t->next)
      t = t->next;

    t->next = (index_node *) calloc (1, sizeof (index_node));
    t = t->next;

    if (NULL == t)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      t->index = index;
      t->next = NULL;
    }
  }
  return TRUE;
}

/* Deletes the index node from the list */
void delete_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    return;
  }
  else
  {
    index_node *t = *list;
    index_node *lbo = *list;

    while (t->index != index)
    {
      if (t->next->next == NULL)
      {
        lbo = t;
      }
      t = t->next;
    }
    
    if (t == *list)
    {
      *list = (*list)->next;
      free (t);
    }
    else if (NULL == t->next)
    {
      lbo->next = NULL;
      free(t);
    }
    else
    {
      t->index = t->next->index;
      index_node *d = t->next;
      t->next = t->next->next;
      free (d);
    }
  }
}

int main (int argc, char **argv)
{
  time_node *interval_list = NULL;

  /* Reads the input file for the intervals */
  FILE *fp = NULL;
  fp = fopen ("intervals.txt", "r");
  if (NULL == fp)
  {
    fprintf (stderr, "Error: Could not read the file.");
    return -1;
  }

  int count = 0;
  int readcount = 0;
  int tmp_count = 0;
  
  /* Reads the count */
  readcount = fscanf (fp, "%d", &count);
  if (0 >= readcount)
  {
    fprintf (stderr, "Error: Nothing in the file.");
    return -2;
  }
  
  interval_list = (time_node *) calloc (count*2, sizeof (time_node));
  if (NULL == interval_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* Reads the intervals */
  printf ("Input:\n");
  for(tmp_count = 0; tmp_count < count; tmp_count++)
  {
    if (feof(fp))
    {
      break;
    }
    unsigned long long start = 0;
    unsigned long long end = 0;
    readcount = fscanf (fp, "%llu %llu", &start, &end);
    printf ("%5d) : %llu <-> %llu\n", tmp_count+1, start, end);
    interval_list[tmp_count*2].timestamp = start;
    interval_list[tmp_count*2].is_start = TRUE;
    interval_list[tmp_count*2].index = tmp_count;
    interval_list[tmp_count*2+1].timestamp = end;
    interval_list[tmp_count*2+1].is_start = FALSE;
    interval_list[tmp_count*2+1].index = tmp_count;
  }
  printf ("\n");
  fclose(fp);

  /* Sort the timestamp values */
  heap_sort (interval_list, count*2);
  
  index_node *index_list = NULL;
  index_node **conflict_list = NULL;
  conflict_list = (index_node **) calloc (count, sizeof (index_node*));
  if (NULL == conflict_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* main loop to find the conflicts */
  for (int i = 0; i < count*2; i++)
  {
    if (interval_list[i].is_start == TRUE)
    {
      if (FALSE == add_index_node (&index_list, interval_list[i].index))
      {
        fprintf (stderr, "Error: Memory allocation failed.");
        return -3;
      }
    }
    else
    {
      delete_index_node (&index_list, interval_list[i].index);

      index_node *t = index_list;
      while (t)
      {
        if (FALSE == add_index_node (&(conflict_list[interval_list[i].index]), t->index) || 
            FALSE == add_index_node (&(conflict_list[t->index]), interval_list[i].index))
        {
          fprintf (stderr, "Error: Memory allocation failed.");
          return -3;
        }
        t = t->next;
      }
    }
  }

  /* Print the result */
  printf ("Conflicts:\n");
  for (int i = 0; i < count; i++)
  {
    printf ("%5d : ", i+1);
    index_node *t = conflict_list[i];
    while (t)
    {
      printf ("%d ", t->index+1);
      t = t->next;
    }
    printf ("\n");
  }
  return 0;
}

We can use self-balanced binary search tree to keep the index_list to get a better time complexity.

In a given 2D binary array, find the area of the biggest rectangle which is filled with 1

   Given array

   1 1 0 1 0 1
   1 1 0 1 1 1
   0 1 1 1 1 1
   0 1 1 1 1 1
   0 0 1 1 1 0
   0 0 0 0 0 0

   Consider each block in the array is an unit and he columns in the array as hanging towers.
   Modify the array in a way that, on each row, the number denotes the height of each column.


   1 1 0 1 0 1
   2 2 0 2 1 2
   0 3 1 3 2 3
   0 4 2 4 3 4
   0 0 3 5 4 0
   0 0 0 0 0 0


   Basic Rules to find the biggest rectangle:
   1. For any tower, the boundaries on each side will be decided by its smaller towers. It means
       that all the towers on each side till we find a smaller tower will be included for the calculation.
   2. Area for the subset equals to (the height of the smaller tower) X (no. of towers in the subset)

   Calculate the area of each subset for each level in the array from top to bottom.

   Level[0] [set 0]              Level[0] [set 1]              Level[0] [set 2]

   1 1 0 1 0 1                   1 1 0 1 0 1                   1 1 0 1 0 1
   ---                                 -                                 -
   2 towers with 1 unit each     1 tower with 1 unit           1 tower with 1 unit
   Maximum Area=2x1=2            Maximum Area=1x1=1            Maximum Area=1x1=1

   Level[0] Maximum Area = 2
   -------------------------------------------------------------------------------
   
   Level[1] [set 0]              Level[1] [set 1]

   2 2 0 2 1 2                   2 2 0 2 1 2
   ---                                 -----
   2 towers with 2 units each    1 tower with 1 unit
   Maximum Area=2x2=4            2 towers with 2 units each
                                 Maximum Area=3x1=3

   For [set 1], even though we have 2 towers with 2 units each in this set, we cannot consider them 
   as a single unit because of the smaller unit's presence in between. So, each tower will be consider 
   as a different subset. But, for the tower with 1 unit has bigger towers around it. So, all the units 
   will be taken (but only one unit from each bigger towers) for the area calculation.

   Level[0] Maximum Area = 4
   -------------------------------------------------------------------------------

   and so on...



int findBigBox (int row, int column, int *matrix)
{
  int max_area = 0;
  int *score = (int *) calloc (row+1, sizeof(int));
  if (NULL != score)
  {
    for (int i=0; i<row; i++)
    {
      for (int j=0; j<column; j++)
      {
        /* Process only if we find 1 */
        if (*(matrix+(i*column)+j) != 0)
        {
          int count = 0;
          int start = j;
          /* Iterate through all the consecutive ones. */
          for (;*(matrix+(i*column)+j) != 0 && j<column; j++)
          {
            /* If it is not the first row, add this element 
               with the previous row element at the same column */
            if (i != 0)
            {
              *(matrix+(i*column)+j) += *(matrix+((i-1)*column)+j);
            }
            *(score+*(matrix+(i*column)+j)) = 1;
          }
          
          getScore (row, column, start, j-1, matrix+(i*column), score);

          for (int s=1; s<=row; s++)
          {
            if (*(score+s))
            {
              int area = s * *(score+s);
              if (max_area < area)
                max_area = area;
            }
          }
          /* Reset the score array to use for the next subset */
          memset (score, 0, (row+1)*sizeof(int));
        }
      }
    }
  }
  free (score);
  
  return max_area;
}



   Here the process of finding the number of towers on each subset for each height is call SCORE.
   This SCORE process can be represented as a tree, which has the following rules,
   1. Node structure
      -> Height
      -> Score
      -> Next
      -> Left
      -> Right
   2. Same numbers on the same set which are non-contiguous will be added as the [Next] node.
   3. Same numbers on the same set which are contiguous will increment the [Score] in the first node.
   4. Taller tower on its left in the set will be added to the [Left] node (child).
   5. Taller tower on its right in the set will be added to the [Right] node (child).
   6. [Score] = [Left]->[score] + [Right]->[score] + no of the same [Height] in the set.

   Example:
   For the below given set,
   3 3 2 3 2 3 1 3 1 3 2 3

   1.    ---------          2.    ---------          3.    ---------
        | H=3|S=1 |              | H=3|S=2 |              | H=2|S=3 |
         ---------                ---------                ---------
                                                             /L
                                                       ---------
                                                      | H=3|S=2 |
                                                       ---------
   In the third step, we move the number 2 as the root and 3 as its left as 3 falls on 2's left in the set and
   3 is bigger than 2.

   4.              --------- 
                  | H=2|S=4 |
                   --------- 
                    /L   \R
            ---------   --------- 
           | H=3|S=2 | | H=3|S=1 |
            ---------   ---------
   We move the number 3 as its right as 3 falls on 2's right in the set

   5.              ---------    N    ---------
                  | H=2|S=5 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R
            ---------   --------- 
           | H=3|S=2 | | H=3|S=1 |
            ---------   ---------

   We move the number 2 to the [Next] of the existing 2 as they are on the same set still. (Which means it is the ROOT node)
            
   6.              ---------    N    ---------
                  | H=2|S=6 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R                \R
            ---------   ---------         --------- 
           | H=3|S=2 | | H=3|S=1 |       | H=3|S=1 |
            ---------   ---------         ---------

    This 3 falls on the right side of the second 2, and increase the count on the first 2

    7.             ---------
                  | H=1|S=7 |
                   --------- 
                       /L 
                   ---------    N    ---------
                  | H=2|S=6 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R                \R
            ---------   ---------         --------- 
           | H=3|S=2 | | H=3|S=1 |       | H=3|S=1 |
            ---------   ---------         ---------
            
   and so on...

   Finally, traverse the tree to find the Maximum SCORE for each height.


void getScore (int row, int column, int start, int end, int *matrix_row, int *score)
{
  /* Intervals to be processed to calculate the score for the number */
  int *currentQ = (int *) calloc (column, sizeof(int));
  /* Intervals to be updated for the next number */
  int *nextQ = (int *) calloc (column, sizeof(int));

  /* Interval counts */
  int currentCount = 1;
  int nextCount = 0;

  /* Start with the whole given set */
  currentQ[0] = start;
  currentQ[1] = end;

  for (int i=1; i<=row; i++)
  {
    if (*(score+i))
    {
      int max = 0;
      for (int c=0; c<currentCount; c++)
      {
        int tmp_score = *(currentQ+(c*2)+1) - *(currentQ+(c*2)) + 1;

        /* Update the temporary max */
        if (max < tmp_score)
        {
          max = tmp_score;
        }

        /* Update the intervals for the next bigger number */
        for (int k=*(currentQ+(c*2)); k<=*(currentQ+(c*2)+1); k++)
        {
          /* Find the start of an interval */
          while (*(matrix_row+k) == i && k<=*(currentQ+(c*2)+1))
          {
            k++;
          }
          
          /* End of the current set */
          if (k > *(currentQ+(c*2)+1))
            break;
          
          *(nextQ+(nextCount*2)) = k;

          /* Find the end of that interval */
          while (*(matrix_row+k) != i && k<=*(currentQ+(c*2)+1)) k++;

          if (k > *(currentQ+(c*2)+1)) // End of the current set
          {
            *(nextQ+(nextCount*2)+1) = k-1;
          }
          else
          {
            *(nextQ+(nextCount*2)+1) = k-1;
          }
          nextCount++;
        }
      }

      int *tmp = currentQ;
      currentQ = nextQ;
      nextQ = tmp;
      
      currentCount = nextCount;
      nextCount = 0;
    
      /* Update the score */
      *(score+i) = max;
    }
  }
}