LIS for coordinate values in O(NlogN) or O(Nlog^2N)

Question

This is a standard Dynamic programming Question LIS PROBLEM

I want a longest increasing subsequence for points in 2D coordinates

that is, 2 points A(x1,y1) at index i in array , B(x2,y2) at index j in array can be a part of increasing sequence if (x1<=x2) && (y1 <=y2) && !(x1==x2 && y1==y2) && (j>i)

my code is as below which is O(N^2) using standard DP :-

#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;


struct Pair
{
    int x;
    int y;
};



int main()
{

    int n;
    cin>>n;

    vector<Pair> arr;
    int L[1000000];

    Pair a;

    int i;int Maxchain=0;
    for(i=0;i<n;i++)
    {

        cin>>a.x>>a.y;
        arr.push_back(a);

        L[i]=0;
        for (int j = i-1; j >=0; j--)
        {

            if ((L[j]>(Maxchain-1))&&(L[j]>=L[i])&&(arr[j].x <= arr[i].x) && (arr[j].y <= arr[i].y) && !(arr[j].x == arr[i].x && arr[j].y == arr[i].y))
                L[i] = L[j]+1;


        }

                Maxchain = L[i]>Maxchain ?L[i]:Maxchain ;

    }
    cout<<Maxchain;

    return 0;
}

This is an O(N^2) solution can it be further reduced or any alogrithm for this to solve in O(NlogN) or O(Nlog^2N) ?

for reference found something here:

Longest Increasing Subsequence (LIS) with two numbers

The second answer is more appropriate for my case but how can we implement that?

Need a Better answer or algorithm.

Answer 1

I'll assume that both coordinates are in the [0..N-1] range (if it's not the case, we can "compress" them without changing their ordering relation).

Let's take a closer look at a standard dynamic programming solution. Let f[i] be the length of the longest increasing subsequence that ends in the i-th position. A simple (but slow) way to compute it is too iterate over all previous elements and choose the optimal one. What we want to find is the max f[j] for all such j that p[j].x <= p[i].x and p[j].y <= p[j].y. It looks like some kind of a 2-D query in a rectangle (I know that there is another condition that p[j] != p[i], but we can work around it by querying two rectangles (p[i].x - 1, p[i].y) and (p[i].x, p[i].y - 1).).

So we need a data structure that supports two operations: adding a point with a specific value and getting the maximum value in a rectangle. A segment tree by x-coordinate that stores a balanced binary search tree by y-coordinate for all points in its range can do it in O(log^2 N) per query. Every query range is decomposed into at most O(log N) nodes in the tree. If it's an insertion query, we need to insert the current point (p[i].x, p[i].y) with a value f[i] into the binary search trees for each of these nodes. If it's a get maximum query, we need to get a maximum for some prefix of each of these trees. Either way, we perform an O(log N) operation for O(log N) binary search trees per query. Thus, the total time complexity is (N * log^2 N). The space complexity is O(N log N) as there are O(log N) levels in the tree and each point can occur somewhere at most once per level.

This solution already satisfies your requirements, but it looks pretty hard to code. We can slightly simplify it. We can do two "runs": during the first run, we just store the queries that go into each node of the segment tree (we don't store any extra information so far). Now we can keep a vector of all numbers that ever occur in the node and a binary index tree of the same length to keep track of a minimum for each prefix and get it efficiently (the big picture: we used the fact that we know all the queries beforehand so we can use a combination of a sorted vector and binary index tree instead of a binary search). The time and space complexity analysis is the same as above.

A short recap: we used a data structure that supports a maximum query in a rectangle and insertions of new points efficiently to speed up finding the best j for a fixed i in an O(N^2) dynamic programming solution to solve it in O(N log^2 N).