NlogN solution using Manacher's algorithm


#1

// LIS using Manacher’s algorithm
// TC = O(NlogN)

int binarySearch(vector<vector > &A, vector &dp, int l, int h, int i) {
int target = A[i][1];
while(l <= h) {
int mid_idx = l + (h-l)/2;
int mid = dp[mid_idx];
if(A[mid][1] == target) return mid_idx;
else if(A[mid][1] < target) l = mid_idx+1;
else h = mid_idx-1;
}
return (-l - 1);
}

int Solution::solve(vector<vector > &A) {
int n = A.size();
if(n <= 1) return n;

vector<int> dp(n, 0);
int len = 1;
for(int i=1; i<n; i++) {
    int idx = binarySearch(A, dp, 0, len-1, i);
    if(idx < 0) {
        idx = -(idx + 1);
        int A_idx = dp[idx];
        if(idx == 0)    dp[idx] = i;
        else if(A[dp[idx-1]][1] < A[i][0]) {
            dp[idx] = i;
            if(idx == len)    len++;
        }
    }
    else {
        if(A[dp[idx]][0] < A[i][0]) {
            dp[idx] = i;
            if(idx == len)    len++;
        }
    }
}

return len;

}


#2

How do you binary search without a sorted sequence?