Find the Kth (smallest) Pair from the Elements in Two Sorted Arrays

Problem: Given two sorted array, by choosing one element from each array we have a pair. A pair can be ranked by the sum of the two numbers within it. Find the Kth smallest pair.

Solution: Naive approach takes O(n*m). Here we can borrow the idea that is used to merge multiple arrays. Basically we need a heap or a priority-queue. The main idea is as follows:

• Put the first pair (which is definitely the smallest) {a[0], b[0]} in the heap as bootstrapping.
• Loop over the heap, if heap is not empty, pop the top of the heap {a[i], b[j]}. If i<n-1, push  {a[i+1], b[j]};  If j<m-1, push  {a[i], b[j+1]}.
• pop k times we will get the kth smallest pair. The complexity is  O(k*log(n+m)).

Volume of Water Held by a Histogram

Problem: Pour water on a histogram, calculate the water volume the histogram can hold.

Solution: This is a relatively simple DP problem. Here we only give the main idea.

• For a particular bar bi, if we know the highest bar on its left Li and highest bar on its right Ri.  If the height of bi is smaller than both Li and Ri, the water volume can be held on this bar is min(Li, Ri) - hi; otherwise, it can't hold water.
• To calculate Li and Ri, we just need to record the maximum height we had observed so far from the left (and from the right). Therefore, a O(n) algorithm is straightforward here.

Maximum Rectangle Area within a Histogram

Problem: Given a histogram, find the maximum rectangle area within it.

Solution:  It is easy to find a O(n^2) algorithm by comparing the height of a bar with the rest bars. Here we give a O(n) algorithm.

• For each bar bi, we need to know the number of adjacent bars on the left Li and on the right Ri that are higher than it. Then the maximum rectangle within the histogram with the height hi will be  (Li+Ri+1)*hi. Then we just need to select the largest one.
• When deciding the number of adjacent bars on the left of bi, the key observation is that we don't need to inspect every bar on its left. The key here is to use a stack to track the bars that had been inspected in a smart way. The bars in the stack are in ascending order (from base to top). Besides, before pushing new bar, we need to pop the bars in the stacks that are higher than it. Then we can achieve calculate Li in O(n). Calculating Ri will be the same.

The following only shows how to calculate Li:

//bar[] represents the height of each bar in the histogram
//left[] stores the number of adjacent bars that are taller than bi 
//this stack is used to track inspected bars
stack s; 

for(int i=0; i<N; i++)
{

  int num = 0;
  int idx;
  while(!s.empty())
  {
    idx = s.top();
    if(bar[idx]>bar[i])
    {
       num++;
       s.pop();
       left[i]+= left[idx];  
    }
    else break;
  }

  s.push(i);
  left[i]= num ? num + left[i]:0;

}

Find the Convex Hull

Problem: a series of points are on plain (X>0 and Y>0), find the convex hull of these points, a.k.a, the points which can form a hull that include all the other points.

Solution: Here only main idea is given.Basically we can use Graham scan.

• Find the point p0 with the smallest y coordinate; if multiple exist, choose the one with the smallest x coordinate, this point must be one of the vertices on the convex hull.
• Sort the other points based on the angle of p0->pi. 
• Put p0, p1 and p2 in a stack (we need at least three to form a hull), then we inspect the rest points based on the order. Assume px is the stack top and py is the one next to the top, if py->pi is at the right side of py->px, pop px. We apply the same check to the new px and py until the previous condition doesn't hold. Then we push pi if previous there are any pop operations. If before push pi, there are only two elements in stack, we can push pi directly. 
• After we iterate all the remaining points, the points on the stack are those that form the convex hull. The complexity is O(nlogn), primarily the sorting cost.

More: Alternatively, we can use Jarvis’s march which is asymptotically faster than Graham’s scan. The time complexity is O(nh) where h is the number of the vertices on the hull. The main idea is as follow:

• Find the highest point p_high and lowest point p_low among all the points, which takes O(n).
• Start from p_low, find the next point that has the smallest polar angle (using +x axis) with respect to p_low. Assume this point is p', then find the next point that has the smallest polar angle with respect to p'. Repeat such process until we find p_high. Up to now, we had found the left chain of the hull.
• Then proceed to find the right chain of the hull. It is similar to finding the left chain. We start from p_high and stop when we reach p_low. The only difference is that when we calculate the polar angle, we use -x axis instead of +x axis.

Output a set's all sub sets

Problem: Given a set, output all its subsets. For example, for set (a,b,c), we need to output (), (a), (b), (c), (a,b), (a, c), (b,c), (a,b,c).

Solution: iterative approach is not difficult. Here give a recursive approach:

void _print(const vector<int>& set)
{
    i; i<< set[i] << " ";
    cout << endl;
}


void print_set(const vector <int>&set, int i, vector<int>& output)
{
   if(i >= set.size()) _print(output);
   else {
     output.push_back(set[i]);
     print_set(set, i+1, output);
　　　// code to handle duplicates
     int tmp = output.back();
     output.pop_back();
     
     if(output.size()>0 && tmp== output.back()) return;
          
     print_set(set, i+1, output);
   }
}

int main()
{
    vector<int> set,output;
    set.push_back(1);
    set.push_back(2);
    set.push_back(3);
    set.push_back(4);

    print_set(set, 0, output);
}

Why we need virtirtual destructor?

When you release the resource of an class object, usually you leverage the object's destructor. Assume we have two class here: base Class A and derived Class B, for the following code:

class A{
  public:
    ~A(){}
};

class B: public A{
   public:
    ~B(){}
};

B *b = new B();
delete b;

First B's destructor will be called, followed by A's. On the other side, if we have the following code:

class A{
  public:
    ~A(){}
};

class B: public A{
   public:
    ~B(){}
};

A *a = new B();
delete a;

Only A's destructor will be called. In order to also call B's destructor in the second code example, the ~A() should be declared as virtual.

Find the Closet Pair of Points

Problem: Given N points on a cartesian ordinate plane, find the two points with the shortest distance.

Solution: We can use the approach that solving P(n) based on P(n-1). We first sort the points based on their X coordinates. Then assume we have solved the problem with the first n-1 points and the shortest distance is d. Then given the nth point, we don't need naively compute the distance between the nth point and all the previous n-1 points. We can leverage the important information we have obtained: "d". If we can further find a closer pair  given the nth point, the other point in the pair should be in a specific area. The area is a rectangle with dimension (d*2d) that sits on the left of the nth point. Moreover, the number of potential points that could be in this area is limited, at most six points (which can be proved using pigeonhole principle). Therefore our algorithm comes as follows:

• two important data structures are used. The first one is an array X_array that contains all the points sorted by their X coordinates. The second is a BST Y_BST that contains the active points sorted by their Y coordinates. Insert the first two points into X_array and Y_BST. Initialize d_min as the distance between the first points.
• using a sweeping line method. Have a vertical line sweep from left to right and start from the third point in X_array.
• when the line touch a point p, given the current d_min,  first we need to remove the points in X_array that have distance larger than d_min to p. We also need to remove these points in Y_BST. Then we add p to Y_BST and adjust the active region within X_array accordingly.
• search the points in the range [p.y-d_min, p.y+d_min] in Y_BST, for each point in the range, calculate its distance to p. If smaller than d_min, update d_min.
• When all the points have been swept, the algorithm finishes.
• The complexity for the whole algorithm is O(nlogn). Why? The initial sorting cost for X_array is O(nlogn).  For each points being removed from the active region in X_array, it takes O(logn). So the total cost for removing points from the active region in X_array  is O(nlogn). Similarly,  the total cost for removing points from  Y_BST is also O(nlogn). Since there are limited number of points in the rectangle with dimension (d*2d). The cost to calculate the distance between them and p is constant. Therefore, the complexity for the whole algorithm is O(nlogn).

typedef pair<double, double> Coordinate;

bool compX(Coordinate p1, Coordinate p2)
{
   if(p1.first != p2.first)
        return p1.first < p2.first;
   else return p1.second < p2.second;
}

bool compY(Coordinate p1, Coordinate p2)
{
  if(p1.second != p2.second)
    return p1.second < p2.second;
  else return p1.first < p2.first;
}

double cal_distance(Coordinate p, Coordinate q)
{
   double a = abs(p.first-q.first);
   double b = abs(p.second-q.second);

   return sqrt(a*a + b*b);
}

double find_closest(vector<Coordinate> &co)
{

   //sort based on X coordinates
   sort(co.begin(), co.end(), compX);

   if(co.size() == 0) return -1;
   if(co.size() == 2) return cal_distance(co[0], co[1]);

   double d_min = cal_distance(co[0], co[1]);
   //inition the y table
   bool(*fn_pt)(Coordinate,Coordinate) = compY;
   set<Coordinate, bool(*)(Coordinate,Coordinate)> y_table(fn_pt);
   y_table.insert(co[0]);
   y_table.insert(co[1]);

   //start from the third point from the left
   int start = 2;

   vector<Coordinate>::iterator tp;
   vector<Coordinate>::iterator it_head = co.begin();
   vector<Coordinate>::iterator it_tail = it_head+1;

   for( ; start<co.size(); start++)
   {
       double l_bound = co[start].first - d_min;
       Coordinate lc(l_bound, 0);
       tp = lower_bound(it_head, it_tail, lc, compX);

      //delete points from y_table
      vector::iterator pp, endp;
      if(tp == it_tail)
      {
         if((*tp).first > (*it_tail).first)
           tp = it_tail+1;
      }

      for( pp = it_head; pp!=tp; pp++)
      {
         y_table.erase(*pp);
      }
      it_head = tp;
      it_tail++;
      y_table.insert(co[start]);

      //select points from y_table
      double y_low = co[start].second - d_min;
      double y_high = co[start].second + d_min;

      //search for these two bounds
      set<Coordinate>::iterator sp, sp_low, sp_high;
      Coordinate y_lc(0, y_low);
      Coordinate y_hc(0, y_high);
      sp_low = lower_bound(y_table.begin(), y_table.end(), y_lc, compY);
      sp_high = lower_bound(y_table.begin(), y_table.end(), y_hc, compY);

      //calculate the distance and compare
      for(sp=sp_low; sp!=sp_high; sp++)
      {
        if(sp->first == co[start].first && sp->second == co[start].second)
             continue;
        double new_d = cal_distance(co[start], *sp);
        if(new_d < d_min) d_min = new_d;
      }

   }

   return d_min;
}

Alternative approach: We can also try to use K-d tree, more precisely, 2-d tree. K-d tree is basically a binary tree. It is constructed by recursively partition the points based on a particular axis (dimension). For example, for a 2-d tree, we first partition by x-coordinate (it is also ok to partition by y-coordinate), given all points, we find the points which x-coordinate is the median of the x-coordinates of all other points. Then we take the points which has this x-coordinate as root. The remaining points are divided into two groups: a) those which x-coordinates are smaller than root.x b) those which x-coordinates are bigger than root.x. Then we recursively partition these two groups, but by y-coordinate. This will help us find the nodes on the second level (assume root is the first level). To find the nodes at the third level, we partition by  x-coordinate. Repeat this until we can't partition any more.

Then we need to apply the Nearest Neighbor Search (NNS) in 2-d tree. Here I just briefly explain the algorithm.

• First, we need to locate the query point  query point q. This process is similar to a binary search based on  q's coordinates. We stop when we encounter a leaf node. Calculate the distance between this leaf node and  q. This is the current best (nearest neighbor).
• However, we need to move forward since the current best may not be optimal. We just rewind the recursion, go to the parent of the leaf node.  Calculate the distance between this (parent) node and  q. If necessary , update the current best. We also need to see if there remains some nearer neighbors in the other plain divided by this (parent) node. This can be done by checking if the circle centered at  q with the radius current best across the splitting line. If yes, we need to check the other branch of this node. Basically, we repeat previous steps, searching q in that subtree.
• If we are done with the (parent) node, we just keep going up, check the parent of this (parent) node, until we encounter the root node.

The empirical performance for a NNS in 2-d tree is O(logn). Then do the NNS for all the nodes is O(nlogn). Considering the cost for building 2-d tree is O(nlogn), the total cost for this problem is also  O(nlogn).

See Also: The closest pair problem