Connecting Ropes
Ninja visited his village after a long time. His village is having a river in its center with ‘N’ houses on the northern bank with distinct X-coordinates ‘A[1]’ , A[2]’ , … , ‘A[N]’ and ‘N’ houses on the southern bank with distinct X-coordinates ‘B[1]’ , ‘B[2]’ , …, ‘B[N]’.

Ninja aims to connect as many north-south pairs of houses with ropes as possible such that no ropes cross each other. He will only connect house ‘A[i]’ with house ‘B[i]’.

Given an integer ‘N’ and arrays ‘A’ and ‘B’ representing the coordinates of houses. Find the maximum number of pairs of houses Ninja can connect.

Example :

N = 3 A = [ 1, 2, 3 ] B = [ 2, 1, 3 ] Explanation : One of the possible connections can be (1,2) and (3,3).

Another possible connection is (2,1) and (3,3).

Ninja cannot connect all 3 pairs (1,2) , (2,1) and (3,3) as the first 2 pairs cross each other.

So, the maximum connection is 2.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow. The first line of each test case contains an integer ‘N’. The next line contains ‘N’ integers representing the elements of array ‘A’ which denotes the coordinates of the northern houses. The next line contains ‘N’ integers representing the elements of array ‘B’ which denotes the coordinates of the southern houses.

Output format :

For each test case, output an integer denoting the maximum connections of houses possible. Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Connecting Ropes

Ninja visited his village after a long time. His village is having a river in its center with ‘N’ houses on the northern bank with distinct X-coordinates ‘A[1]’ , A[2]’ , … , ‘A[N]’ and ‘N’ houses on the southern bank with distinct X-coordinates ‘B[1]’ , ‘B[2]’ , …, ‘B[N]’.

Ninja aims to connect as many north-south pairs of houses with ropes as possible such that no ropes cross each other. He will only connect house ‘A[i]’ with house ‘B[i]’.

Given an integer ‘N’ and arrays ‘A’ and ‘B’ representing the coordinates of houses. Find the maximum number of pairs of houses Ninja can connect.

Example :

N = 3
A = [ 1, 2, 3 ]
B = [ 2, 1, 3 ]

Explanation : 

One of the possible connections can be (1,2) and (3,3).

Another possible connection is (2,1) and (3,3).

Ninja cannot connect all 3 pairs (1,2) , (2,1) and (3,3) as the first 2 pairs cross each other.

So, the maximum connection is 2.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’.

The next line contains ‘N’ integers representing the elements of array ‘A’ which denotes the coordinates of the northern houses.

The next line contains ‘N’ integers representing the elements of array ‘B’ which denotes the coordinates of the southern  houses.

Output format :

For each test case, output an integer denoting the maximum connections of houses possible.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Sub-Optimal Approach

Approach :

We first notice that the pairs (‘n1’,’s1’) and (‘n2’,’s2’) will cross each other if either :
‘n1’ < ‘n2’ and ‘s1’ > ‘s2’
‘n1’ > ‘n2’ and ‘s1’ < ‘s2’
To reduce the cases, we just sort the pairs by their north coordinates.
So, we only need to take care that there is no pair (‘n1’, ‘n2’) and (‘s1’,’s2’ ) such that ‘s1’ > ‘s2’.
So, we need to select the subsequence from the south coordinates which is in strictly increasing order.
And to maximize the pair of rope connections, we find the longest increasing subsequence among the south coordinates formed after sorting their respective north coordinates.
We find the longest increasing subsequence with the dynamic programming approach.

Algorithm :

Initialise a variable ‘ans’ = 0.
Add the respective coordinates in an array ‘arr’ of pair with their north and south coordinates.
Sort the array ‘arr’ with respect to the north coordinates.
Maintain an array ‘dp’ of size ‘N’ initialized to 1.
Run a for loop from ‘i=0’ to ‘i=N-1’.
- Run a nested for loop from ‘j=0’ to ‘j=i-1’.
- If ‘arr[i].south’ > ‘arr[j].south’ :
- Update ‘dp[i]’ as the maximum of ‘dp[i]’ and ‘dp[j]+1’.
Update ‘ans’ as the maximum of ‘ans’ and ‘dp[i]’.
Return ‘ans’ as the final result.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array ‘A’.

We are maintaining an array to store states of longest increasing subsequence. Hence, the overall Space Complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the length of the array ‘A’.

We are running two nested for loops for finding the longest increasing subsequence, so the overall time complexity is O(N^2).

Python (3.5)

'''

    Time Complexity : O(N^2)

    Space Complexity : O(N)



    where 'N' is the size of array 'A' and 'B'.

'''

from typing import *



def connectingRopes(a: List[int], b: List[int], n: int)-> int:

    

    # Arraylist to store pairs of north and south house coordinates.

    arr = []



    for i in range(n):

        arr.append([a[i], b[i]])



    # Sort arr in terms of north coordinates.

    arr.sort()



    dp = [1 for i in range(n + 1)]

    





    # Variable to store the number of non-crossing ropes connection.

    ans = 0



    for i in range(n):

        for j in range(i):

            # Check if current index 'j' can be placed before index 'i'.

            if arr[j][1] < arr[i][1]:

                dp[i] = max(dp[i], dp[j] + 1)

            

        

        # Update 'ans' as the maximum of the two.

        ans = max(ans, dp[i])

        

    

    # Return the final result.

    return ans

C++ (g++ 5.4)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(N)



    where 'N' is the size of array 'A' and 'B'.

*/



int connectingRopes(vector &a, vector &b, int n) {



    // Arraylist to store pairs of north and south house coordinates.

    vector> arr;



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

      arr.push_back({a[i], b[i]});

    }



    // Sort arr in terms of north coordinates.

    sort(arr.begin(), arr.end());



    // Calculate the Longest Increasing Subsequence in O(NlogN).

    vector dp(n + 1, 1);



    // Variable to store the number of non-crossing ropes connection.

    int ans = 0;



    // Dynamic Programming to calculate the length of longest increasing subsequence.

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

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

        // Check if current index 'j' can be placed before index 'i'.

        if (arr[j].second < arr[i].second) {

          dp[i] = max(dp[i], dp[j] + 1);

        }

      }

      // Update 'ans' as the maximum of the two.

      ans = max(ans, dp[i]);

    }



    // Return the final result.

    return ans;

}

Java (SE 1.8)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(N)



    where 'N' is the size of array 'A' and 'B'.

 */



import java.util.ArrayList;

import java.util.Collections;



class Solution {



  public static int connectingRopes(int a[], int b[], int n) {



    // Arraylist to store pairs of north and south house coordinates.

    ArrayList < Pair > arr = new ArrayList < > ();



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

      arr.add(new Pair(a[i], b[i]));

    }



    // Sort arr in terms of north coordinates.

    Collections.sort(arr);



    // Calculate the Longest Increasing Subsequence in O(NlogN).

    int dp[] = new int[n + 1];

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

      dp[i] = 1;

    }



    // Variable to store the number of non-crossing ropes connection.

    int ans = 0;



    // Dynamic Programming to calculate the length of longest increasing subsequence.

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

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

        // Check if current index 'j' can be placed before index 'i'.

        if (arr.get(j).south < arr.get(i).south) {

          dp[i] = Math.max(dp[i], dp[j] + 1);

        }

      }

      // Update 'ans' as the maximum of the two.

      ans = Math.max(ans, dp[i]);

    }



    // Return the final result.

    return ans;

  }



  public static class Pair implements Comparable < Pair > {

    // Coordinates of the north and south pair of houses.

    private int north,

            south;



    Pair(int a, int b) {

      this.north = a;

      this.south = b;

    }



    @Override

    public int compareTo(Pair p) {

      return (this.north - p.north);

    }

  }

}

Accepted Answer

Optimal Approach

Approach :

In the previous approach, we were finding the longest increasing subsequence among the south coordinates in O(N^2).
Here, we will find the longest increasing subsequence in O(N*logN).
We maintain an array ‘dp’ with size ‘N+1’ initialised to ‘INF’.
Now, for every element ‘x’ , we check in array ‘dp’ the lower bound index of the element ‘x’.
This is because the elements before this index are in increasing order and element ‘x’ can be added at the end of this subsequence.
We update our answer as the maximum of lower bound index of each element ‘x’.

Algorithm :

Initialise a variable ‘ans’ = 0.
Add the respective coordinates in an array ‘arr’ of pair with their north and south coordinates.
Sort the array ‘arr’ with respect to the north coordinates.
Maintain an array ‘dp’ of size ‘N+1’ initialized to ‘INF’.
Run a for loop from ‘i=0’ to ‘i=N-1’.
- Lower bound on the index on array ‘dp’ having ‘dp[idx]’ just greater than or equal to ‘arr[i].south’.
- Update the value at ‘dp[idx]’ with ‘arr[i].south’.
- Update ‘ans’ as the maximum of ‘ans’ and ‘idx+1’.
Return ‘ans’ as the final result.

Space Complexity: O(1)Explanation:

O(N), where ‘N’ is the length of the array ‘A’.

We are maintaining a vector to store the longest increasing subsequence. Hence, the overall Space Complexity is O(N).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)) , where ‘N’ is the size of array ‘A’.

We are performing binary search on an array of size ‘N’ for all the ‘N’ coordinates, so the overall time complexity is O(N*log(N)).