Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays

0 0 8 minutes read

We are given two arrays, we need to find the longest possible bitonic sequence such that the increasing part must be from the first array and should be a subsequence of the first array. Similarly, the decreasing part of must be from the second array and should be a subsequence of it.

Examples:

Input : arr1[] = {1, 5, 2, 4, 3, 5}, 
        arr2[] = {8, 6, 4, 7, 3, 2}
Output : 1, 2, 4, 5, 8, 6, 4, 3, 2

Input : arr1[] = {2, 0, 1, 3, 4}, 
        arr2[] = {5, 3, 2, 1}
Output : 0, 1, 2, 3, 4, 5, 3, 2, 1

The idea is to use the largest increasing sequence from array1 and the largest decreasing sequence from array2 and then combine both to get our result.

C++

// CPP to find largest bitonic sequence such that
#include <bits/stdc++.h>
using namespace std;
 
vector<int> res;
 
// utility Binary search
int GetCeilIndex(int arr[], vector<int>& T, int l, 
                                   int r, int key)
{
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (arr[T[m]] >= key)
            r = m;
        else
            l = m;
    }
    return r;
}
 
// function to find LIS in reverse form
void LIS(int arr[], int n)
{
    // Add boundary case, when array n is zero
    // Depend on smart pointers
    vector<int> tailIndices(n, 0); // Initialized with 0
    vector<int> prevIndices(n, -1); // initialized with -1
 
    int len = 1; // it will always point to empty location
    for (int i = 1; i < n; i++) {
 
        // new smallest value
        if (arr[i] < arr[tailIndices[0]])             
            tailIndices[0] = i;
 
        // arr[i] wants to extend largest subsequence
        else if (arr[i] > arr[tailIndices[len - 1]]) {            
            prevIndices[i] = tailIndices[len - 1];
            tailIndices[len++] = i;
        } 
          
        // arr[i] wants to be a potential candidate of
        // future subsequence
        // It will replace ceil value in tailIndices
        else {
            int pos = GetCeilIndex(arr, tailIndices, -1, 
                                        len - 1, arr[i]);
            prevIndices[i] = tailIndices[pos - 1];
            tailIndices[pos] = i;
        }
    }
 
    // put LIS into vector
    for (int i = tailIndices[len - 1]; i >= 0; i = prevIndices[i])
        res.push_back(arr[i]);
}
 
// function for finding longest bitonic seq
void longestBitonic(int arr1[], int n1, int arr2[], int n2)
{
    // find LIS of array 1 in reverse form
    LIS(arr1, n1);
 
    // reverse res to get LIS of first array
    reverse(res.begin(), res.end());
 
    // reverse array2 and find its LIS
    reverse(arr2, arr2 + n2);
    LIS(arr2, n2);
 
    // print result
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
}
 
// driver preogram
int main()
{
    int arr1[] = { 1, 2, 4, 3, 2 };
    int arr2[] = { 8, 6, 4, 7, 8, 9 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    longestBitonic(arr1, n1, arr2, n2);
    return 0;
}

Java

// Java to find largest bitonic sequence such that
import java.util.*;
 
class GFG 
{
    static Vector<Integer> res = new Vector<>();
 
    // utility Binary search
    static Integer GetCeilIndex(Integer[] arr, Integer[] T, 
                                Integer l, Integer r, Integer key) 
    {
        while (r - l > 1) 
        {
            Integer m = l + (r - l) / 2;
            if (arr[T[m]] >= key)
                r = m;
            else
                l = m;
        }
        return r;
    }
 
    // function to find LIS in reverse form
    static void LIS(Integer[] arr, Integer n)
    {
 
        // Add boundary case, when array n is zero
        // Depend on smart pointers
        Integer[] tailIndices = new Integer[n];
        Integer[] prevIndices = new Integer[n];
        Arrays.fill(tailIndices, 0); // Initialized with 0
        Arrays.fill(prevIndices, -1); // initialized with -1
 
        Integer len = 1; // it will always point to empty location
        for (Integer i = 1; i < n; i++) 
        {
            // new smallest value
            if (arr[i] < arr[tailIndices[0]])
                tailIndices[0] = i;
 
            // arr[i] wants to extend largest subsequence
            else if (arr[i] > arr[tailIndices[len - 1]]) 
            {
                prevIndices[i] = tailIndices[len - 1];
                tailIndices[len++] = i;
            }
 
            // arr[i] wants to be a potential candidate of
            // future subsequence
            // It will replace ceil value in tailIndices
            else
            {
                Integer pos = GetCeilIndex(arr, 
                            tailIndices, -1, len - 1, arr[i]);
                prevIndices[i] = tailIndices[pos - 1];
                tailIndices[pos] = i;
            }
        }
 
        // put LIS into vector
        for (Integer i = tailIndices[len - 1]; i >= 0; i = prevIndices[i])
            res.add(arr[i]);
    }
 
    // function for finding longest bitonic seq
    static void longestBitonic(Integer[] arr1, Integer n1,
                                Integer[] arr2, Integer n2)
    {
        // find LIS of array 1 in reverse form
        LIS(arr1, n1);
 
        // reverse res to get LIS of first array
        Collections.reverse(res);
 
        // reverse array2 and find its LIS
        Collections.reverse(Arrays.asList(arr2));
        LIS(arr2, n2);
 
        // print result
        for (Integer i = 0; i < res.size(); i++)
            System.out.print(res.elementAt(i) + " ");
    }
 
    // Driver Code
    public static void main(String[] args) 
    {
        Integer[] arr1 = { 1, 2, 4, 3, 2 };
        Integer[] arr2 = { 8, 6, 4, 7, 8, 9 };
        Integer n1 = arr1.length;
        Integer n2 = arr2.length;
        longestBitonic(arr1, n1, arr2, n2);
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 to find largest bitonic sequence such that
res = []
 
# utility Binary search
def GetCeilIndex(arr,T, l,r, key):
    while (r - l > 1):
        m = l + (r - l) // 2;
        if (arr[T[m]] >= key):
            r = m
        else:
            l = m
    return r
 
# function to find LIS in reverse form
def LIS(arr, n):
     
    # Add boundary case, when array n is zero
    # Depend on smart pointers
    tailIndices = [0]*(n) #Initialized with 0
    prevIndices = [-1]*(n) #initialized with -1
 
    leN = 1 # it will always point to empty location
    for i in range(1, n):
 
        # new smallest value
        if (arr[i] < arr[tailIndices[0]]):
            tailIndices[0] = i
 
        # arr[i] wants to extend largest subsequence
        else if (arr[i] > arr[tailIndices[leN - 1]]):
            prevIndices[i] = tailIndices[leN - 1]
            tailIndices[leN] = i
            leN += 1
 
        # arr[i] wants to be a potential candidate of
        # future subsequence
        # It will replace ceil value in tailIndices
        else:
            pos = GetCeilIndex(arr, tailIndices, -1,
                               leN - 1, arr[i])
            prevIndices[i] = tailIndices[pos - 1]
            tailIndices[pos] = i
 
    # put LIS into vector
    i = tailIndices[leN - 1]
    while(i >= 0):
         
        # print(i)
        res.append(arr[i])
        i = prevIndices[i]
 
# function for finding longest bitonic seq
def longestBitonic(arr1, n1, arr2, n2):
    global res
     
    # find LIS of array 1 in reverse form
    LIS(arr1, n1)
 
    # reverse res to get LIS of first array
    res = res[::-1]
 
    # reverse array2 and find its LIS
    arr2 = arr2[::-1]
    LIS(arr2, n2)
 
    # print result
    for i in res:
        print(i,end=" ")
 
# Driver program
 
arr1 = [1, 2, 4, 3, 2]
arr2 = [8, 6, 4, 7, 8, 9]
n1 = len(arr1)
n2 = len(arr2)
longestBitonic(arr1, n1, arr2, n2);
 
# This code is contributed by mohit kumar 29    

C#

// C# to find largest bitonic 
// sequence 
using System;
using System.Collections.Generic;
class GFG{ 
 
static List<int> res = new List<int>(); 
 
// Reverse array
static int[] reverse(int []a) 
{
  int i, n = a.Length, t;
  for (i = 0; i < n / 2; i++) 
  {
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
  }
  return a;
}
   
// Utility Binary search 
static int GetCeilIndex(int[] arr, int[] T, 
                        int l, int r, int key) 
{ 
  while (r - l > 1) 
  { 
    int m = l + (r - l) / 2; 
    if (arr[T[m]] >= key) 
      r = m; 
    else
      l = m; 
  } 
  return r; 
} 
 
// Function to find LIS in reverse form 
static void LIS(int[] arr, int n) 
{
  // Add boundary case, 
  // when array n is zero 
  // Depend on smart pointers 
  int[] tailIndices = new int[n]; 
  int[] prevIndices = new int[n]; 
  for(int i = 0; i < n; i++)
  {
    tailIndices[i] = 0;
    prevIndices[i] = -1;
  }
  int len = 1; 
   
  // It will always point 
  // to empty location 
  for (int i = 1; i < n; i++) 
  { 
    // New smallest value 
    if (arr[i] < arr[tailIndices[0]]) 
      tailIndices[0] = i; 
 
    // arr[i] wants to extend 
    // largest subsequence 
    else if (arr[i] > arr[tailIndices[len - 1]]) 
    { 
      prevIndices[i] = tailIndices[len - 1]; 
      tailIndices[len++] = i; 
    } 
 
    // arr[i] wants to be 
    // a potential candidate of 
    // future subsequence 
    // It will replace ceil 
    // value in tailIndices 
    else
    { 
      int pos = GetCeilIndex(arr, tailIndices, 
                             -1, len - 1, arr[i]); 
      prevIndices[i] = tailIndices[pos - 1]; 
      tailIndices[pos] = i; 
    } 
  } 
 
  // Put LIS into vector 
  for (int i = tailIndices[len - 1]; 
           i >= 0; i = prevIndices[i]) 
    res.Add(arr[i]); 
} 
 
// Function for finding longest bitonic seq 
static void longestBitonic(int[] arr1, int n1,  
                           int[] arr2, int n2) 
{ 
  // Find LIS of array 1 
  // in reverse form 
  LIS(arr1, n1); 
 
  // Reverse res to get 
  // LIS of first array 
  res.Reverse();
 
  // Reverse array2 and 
  // find its LIS 
  arr2 = reverse(arr2); 
  LIS(arr2, n2); 
 
  // Print result 
  for (int i = 0; i < res.Count; i++) 
    Console.Write(res[i] + " "); 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
  int[] arr1 = {1, 2, 4, 3, 2}; 
  int[] arr2 = {8, 6, 4, 7, 8, 9}; 
  int n1 = arr1.Length; 
  int n2 = arr2.Length; 
  longestBitonic(arr1, n1, arr2, n2); 
} 
} 
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript to find largest 
// bitonic sequence such that
     
    let res = [];
     
    // utility Binary search
    function GetCeilIndex(arr,T,l,r,key)
    {
        while (r - l > 1)
        {
            let m = l + Math.floor((r - l) / 2);
            if (arr[T[m]] >= key)
                r = m;
            else
                l = m;
        }
        return r;
    }
     
    // function to find LIS in reverse form
    function LIS(arr,n)
    {
        // Add boundary case, when array n is zero
        // Depend on smart pointers
        let tailIndices = new Array(n);
        let prevIndices = new Array(n);
        for(let i=0;i<n;i++)
        {
            tailIndices[i]=0;
            prevIndices[i]=-1;
        }
        // it will always point to empty location
        let len = 1; 
        for (let i = 1; i < n; i++)
        {
            // new smallest value
            if (arr[i] < arr[tailIndices[0]])
                tailIndices[0] = i;
  
            // arr[i] wants to extend largest subsequence
            else if (arr[i] > arr[tailIndices[len - 1]])
            {
                prevIndices[i] = tailIndices[len - 1];
                tailIndices[len++] = i;
            }
  
            // arr[i] wants to be a potential candidate of
            // future subsequence
            // It will replace ceil value in tailIndices
            else
            {
                let pos = GetCeilIndex(arr,
                    tailIndices, -1, len - 1, arr[i]);
                prevIndices[i] = tailIndices[pos - 1];
                tailIndices[pos] = i;
            }
        }
  
        // put LIS into vector
        for (let i = tailIndices[len - 1]; i >= 0;
        i = prevIndices[i])
            res.push(arr[i]);
    }
     
    // function for finding longest bitonic seq
    function longestBitonic(arr1,n1,arr2,n2)
    {
        // find LIS of array 1 in reverse form
        LIS(arr1, n1);
  
        // reverse res to get LIS of first array
        res.reverse();
  
        // reverse array2 and find its LIS
        arr2.reverse();
        LIS(arr2, n2);
  
        // print result
        for (let i = 0; i < res.length; i++)
            document.write(res[i] + " ");
    }
     
    // Driver Code
    let arr1=[1, 2, 4, 3, 2];
    let arr2=[8, 6, 4, 7, 8, 9];
    let n1 = arr1.length;
    let n2 = arr2.length;
    longestBitonic(arr1, n1, arr2, n2);
     
 
// This code is contributed by patel2127
 
</script>

Output

1 2 3 8 6 4

Time Complexity : O(n Log n)
Auxiliary Space: O(n)

Please note that O(n Log n) implementation of LIS is used
If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!