Find a sorted sub-sequence of size 4 in linear time
Given an array (arr[]) of N integers, find a subsequence of 4 elements such that a[i] < a[j] < a[k] < a[l] and i < j < k < l in O(N) time. If there are multiple such Quadruplet, then just print any one of them.
Examples:
Input: arr[] = {7, 4, 6, 10, 11, 13, 1, 2}
Output: 4 6 10 13
Explanation: As 4 < 6 < 10 <13, where i < j < k < l, arr[i] < arr[j] < arr[k] < arr[l]Input: arr[] = {1, 7, 4, 5, 3, 6}
Output: 1 4 5 6
Explanation: As 1 < 4 < 5 < 6, where i < j < k < l, arr[i] < arr[j] < arr[k] < arr[l]Input: arr[] = {4, 3, 1, 7}
Output: No such Quadruplet exists.
Naive Approach:
Hint: Use Auxiliary Space.
The approach is to find an element which has two element smaller than itself on the left side of the array and an element greater than itself on the right side of the array, if there is any such element then there exists a Quadruplet that satisfies the criteria, otherwise no such Quadruplet is present.
Algorithm:
- Create an auxiliary array smaller[n], which stores the index of a number which is smallest value than arr[i] and is on the left side. The array contains -1 if there is no such element.
- Create another auxiliary array second_smaller[n], which stores the index of a number which is second smaller value than arr[i] and is on the left side. The array contains -1 if there is no such element.
- Create another auxiliary array greater[n], which stores the index of a number which is greater value than arr[i] and is on the right side. The array contains -1 if there is no such element.
- Finally traverse three arrays and find the index in which greater[i] != -1, second_smaller[i] != -1 and smaller[second_smaller[i]] != -1 and if condition matches the Quadruplet will be arr[smaller[second_smaller[i]]], arr[second_smaller[i]], arr[i] and arr[greater[i]] .
Below is the implementation of the above approach:-
C++
// C++ program to find a sorted // sub-sequence of size 4 #include <bits/stdc++.h> using namespace std; void findQuadruplet( int arr[], int n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4) { cout << "No such Quadruple found" ; return ; } bool flag = false ; // to check true or false // Index of greatest element // from right side int max = n - 1; // Index of smallest element // from left side int min = 0; // Index of second smallest element // from left side int second_min = -1; // Create another array that will // store index of a minimum element // on left side. If there is no minimum // element on left side, // then smaller[i] = -1 int * smaller = new int [n]; // Create another array that will // store index of a second minimum // element on left side. If there is no // second minimum element on left side, // then second_smaller[i] = -1 int * second_smaller = new int [n]; // First entry of both smaller and // second_smaller is -1. smaller[0] = -1; second_smaller[0] = -1; for ( int i = 1; i < n; i++) { if (arr[i] <= arr[min]) { min = i; smaller[0] = -1; second_smaller[0] = -1; } else { smaller[i] = min; if (second_min != -1) { if (arr[second_min] < arr[i]) { second_smaller[i] = second_min; } } else { second_smaller[i] = -1; } if (arr[i] < arr[second_min] || second_min == -1) { second_min = i; } } } // Create another array that will store // index of a greater element on right side. // If there is no greater element on // right side, then greater[i] = -1 int * greater = new int [n]; // Last entry of greater is -1. greater[n - 1] = -1; for ( int i = n - 2; i >= 0; i--) { if (arr[max] <= arr[i]) { max = i; greater[i] = -1; } else { greater[i] = max; } } // Now we need to find a number which // has a greater on its right side and // two small on it's left side. for ( int i = 0; i < n; i++) { if (smaller[second_smaller[i]] != -1 && second_smaller[i] != -1 && greater[i] != -1) { cout << "Quadruplets: " << arr[smaller[second_smaller[i]]] << " " << arr[second_smaller[i]] << " " << arr[i] << " " << arr[greater[i]] << "\n" ; flag = true ; break ; } } if (flag == false ) cout << "No such Quadruplet found" ; // Free the dynamically allocated memory // to avoid memory leak delete [] smaller; delete [] greater; delete [] second_smaller; return ; } // Driver Code int main() { int arr[] = { 1, 7, 4, 5, 3, 6 }; int N = sizeof (arr) / sizeof ( int ); findQuadruplet(arr, N); return 0; } |
Java
// Java program to find a sorted // sub-sequence of size 4 class GFG { static void findQuadruplet( int arr[], int n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4 ) { System.out.println( "No such Quadruple found" ); return ; } boolean flag = false ; // to check true or false // Index of greatest element // from right side int max = n - 1 ; // Index of smallest element // from left side int min = 0 ; // Index of second smallest element // from left side int second_min = - 1 ; // Create another array that will // store index of a minimum element // on left side. If there is no minimum // element on left side, // then smaller[i] = -1 int [] smaller = new int [n]; // Create another array that will // store index of a second minimum // element on left side. If there is no // second minimum element on left side, // then second_smaller[i] = -1 int [] second_smaller = new int [n]; // First entry of both smaller and // second_smaller is -1. smaller[ 0 ] = - 1 ; second_smaller[ 0 ] = - 1 ; for ( int i = 1 ; i < n; i++) { if (arr[i] <= arr[min]) { min = i; smaller[ 0 ] = - 1 ; second_smaller[ 0 ] = - 1 ; } else { smaller[i] = min; if (second_min != - 1 ) { if (arr[second_min] < arr[i]) { second_smaller[i] = second_min; } } else { second_smaller[i] = - 1 ; } if (second_min == - 1 || arr[i] < arr[second_min]) { second_min = i; } } } // Create another array that will store // index of a greater element on right side. // If there is no greater element on // right side, then greater[i] = -1 int [] greater = new int [n]; // Last entry of greater is -1. greater[n - 1 ] = - 1 ; for ( int i = n - 2 ; i >= 0 ; i--) { if (arr[max] <= arr[i]) { max = i; greater[i] = - 1 ; } else { greater[i] = max; } } // Now we need to find a number which // has a greater on its right side and // two small on it's left side. for ( int i = 0 ; i < n; i++) { if (second_smaller[i] != - 1 && smaller[second_smaller[i]] != - 1 && greater[i] != - 1 ) { System.out.println( "Quadruplets: " + arr[smaller[second_smaller[i]]] + " " + arr[second_smaller[i]] + " " + arr[i] + " " + arr[greater[i]]); flag = true ; break ; } } if (flag == false ) System.out.println( "No such Quadruplet found" ); return ; } // Driver Code public static void main(String args[]) { int arr[] = { 1 , 7 , 4 , 5 , 3 , 6 }; int N = arr.length; findQuadruplet(arr, N); } } // This code is contributed by Lovely Jain |
Python3
# Python3 program for the above approach # program to find a sorted # sub-sequence of size 4 def findQuadruplet(arr, n) : # If number of elements < 4 # then no Quadruple are possible if (n < 4 ) : print ( "No such Quadruple found" ) return flag = False # to check true or false # Index of greatest element # from right side max = n - 1 # Index of smallest element # from left side min = 0 # Index of second smallest element # from left side second_min = - 1 # Create another array that will # store index of a minimum element # on left side. If there is no minimum # element on left side, # then smaller[i] = -1 smaller = [ 0 ] * n # Create another array that will # store index of a second minimum # element on left side. If there is no # second minimum element on left side, # then second_smaller[i] = -1 second_smaller = [ 0 ] * n # First entry of both smaller and # second_smaller is -1. smaller[ 0 ] = - 1 second_smaller[ 0 ] = - 1 for i in range ( 1 , n) : if (arr[i] < = arr[ min ]) : min = i smaller[ 0 ] = - 1 second_smaller[ 0 ] = - 1 else : smaller[i] = min if (second_min ! = - 1 ) : if (arr[second_min] < arr[i]) : second_smaller[i] = second_min else : second_smaller[i] = - 1 if (arr[i] < arr[second_min] or second_min = = - 1 ) : second_min = i # Create another array that will store # index of a greater element on right side. # If there is no greater element on # right side, then greater[i] = -1 greater = [ 0 ] * n # Last entry of greater is -1. greater[n - 1 ] = - 1 for i in range (n - 2 , - 1 , - 1 ) : if (arr[ max ] < = arr[i]) : max = i greater[i] = - 1 else : greater[i] = max # Now we need to find a number which # has a greater on its right side and # two small on it's left side. for i in range (n) : if (smaller[second_smaller[i]] ! = - 1 and second_smaller[i] ! = - 1 and greater[i] ! = - 1 ) : print ( "Quadruplets:" , arr[smaller[second_smaller[i]]], end = " " ) print (arr[second_smaller[i]], end = " " ) print (arr[i], end = " " ) print (arr[greater[i]]) flag = True break if (flag = = False ) : print ( "No such Quadruplet found" ) return # Driver Code arr = [ 1 , 7 , 4 , 5 , 3 , 6 ] N = len (arr) findQuadruplet(arr, N) # This code is contributed by sanjoy_62. |
C#
// C# program to find a sorted // sub-sequence of size 4 using System; public class GFG { static void findQuadruplet( int []arr, int n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4) { Console.WriteLine( "No such Quadruple found" ); return ; } bool flag = false ; // to check true or false // Index of greatest element // from right side int max = n - 1; // Index of smallest element // from left side int min = 0; // Index of second smallest element // from left side int second_min = -1; // Create another array that will // store index of a minimum element // on left side. If there is no minimum // element on left side, // then smaller[i] = -1 int [] smaller = new int [n]; // Create another array that will // store index of a second minimum // element on left side. If there is no // second minimum element on left side, // then second_smaller[i] = -1 int [] second_smaller = new int [n]; // First entry of both smaller and // second_smaller is -1. smaller[0] = -1; second_smaller[0] = -1; for ( int i = 1; i < n; i++) { if (arr[i] <= arr[min]) { min = i; smaller[0] = -1; second_smaller[0] = -1; } else { smaller[i] = min; if (second_min != -1) { if (arr[second_min] < arr[i]) { second_smaller[i] = second_min; } } else { second_smaller[i] = -1; } if (second_min == -1 || arr[i] < arr[second_min]) { second_min = i; } } } // Create another array that will store // index of a greater element on right side. // If there is no greater element on // right side, then greater[i] = -1 int [] greater = new int [n]; // Last entry of greater is -1. greater[n - 1] = -1; for ( int i = n - 2; i >= 0; i--) { if (arr[max] <= arr[i]) { max = i; greater[i] = -1; } else { greater[i] = max; } } // Now we need to find a number which // has a greater on its right side and // two small on it's left side. for ( int i = 0; i < n; i++) { if (second_smaller[i] != -1 && smaller[second_smaller[i]] != -1 && greater[i] != -1) { Console.WriteLine( "Quadruplets: " + arr[smaller[second_smaller[i]]] + " " + arr[second_smaller[i]] + " " + arr[i] + " " + arr[greater[i]]); flag = true ; break ; } } if (flag == false ) Console.WriteLine( "No such Quadruplet found" ); return ; } // Driver Code public static void Main( string []args) { int []arr = { 1, 7, 4, 5, 3, 6 }; int N = arr.Length; findQuadruplet(arr, N); } } // This code is contributed by AnkThon |
Javascript
// JavaScript program to find a sorted // sub-sequence of size 4 function findQuadruplet(arr, n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4) { console.log( "No such Quadruple found" ); return ; } let flag = false ; // to check true or false // Index of greatest element // from right side let max = n - 1; // Index of smallest element // from left side let min = 0; // Index of second smallest element // from left side let second_min = -1; // Create another array that will // store index of a minimum element // on left side. If there is no minimum // element on left side, // then smaller[i] = -1 let smaller = new Array(n).fill(0); // Create another array that will // store index of a second minimum // element on left side. If there is no // second minimum element on left side, // then second_smaller[i] = -1 let second_smaller = new Array(n).fill(0); // First entry of both smaller and // second_smaller is -1. smaller[0] = -1; second_smaller[0] = -1; for (let i = 1; i < n; i++) { if (arr[i] <= arr[min]) { min = i; smaller[0] = -1; second_smaller[0] = -1; } else { smaller[i] = min; if (second_min != -1) { if (arr[second_min] < arr[i]) { second_smaller[i] = second_min; } } else { second_smaller[i] = -1; } if (arr[i] < arr[second_min] || second_min == -1) { second_min = i; } } } // Create another array that will store // index of a greater element on right side. // If there is no greater element on // right side, then greater[i] = -1 let greater = new Array(n).fill(0); // Last entry of greater is -1. greater[n - 1] = -1; for (let i = n - 2; i >= 0; i--) { if (arr[max] <= arr[i]) { max = i; greater[i] = -1; } else { greater[i] = max; } } // Now we need to find a number which // has a greater on its right side and // two small on it's left side. for (let i = 0; i < n; i++) { if ((smaller[second_smaller[i]] != -1) && (second_smaller[i] != -1) && (greater[i] != -1)) { console.log( "Quadruplets: " , arr[smaller[second_smaller[i]]] , arr[second_smaller[i]], arr[i], arr[greater[i]]); flag = true ; break ; } } if (flag == false ) console.log( "No such Quadruplet found" ); return ; } // Driver Code let arr = [ 1, 7, 4, 5, 3, 6 ]; let N = arr.length; findQuadruplet(arr, N); // This code is contributed by phasing17 |
Quadruplets: 1 4 5 6
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: Follow the below idea to solve the problem:
The idea is to find first find three elements arr[i], arr[j] , arr[k] such that arr[i] < arr[j] < arr[k]. Then find a fourth element arr[l] greater than arr[k] by traversing the array with O(n) time and O(1) space. Then we can print the Quadruplet as arr[i], arr[j], arr[k], arr[l] .
Follow the steps to solve the problem:
- Iterate over the length of the array.
- Keep track of the min element.
- As soon as the next iteration has an element greater than min, we have found our second min and the min will be saved as arr[i].
- Continue iterating until a greater element than arr[j] is found and get our arr[k] and second min will be saved as arr[j] and min as arr[i]
- Then, while continuing iteration try to find a number greater than arr[k] which is arr[l] .
- Then the sequence of Quadruplet will be min, second min, arr[k] and arr[l] (where min < second min < arr[k] < arr[l].
Below is the implementation of the above approach:-
C++
// C++ program to find a sorted // sub-sequence of size 4 #include <bits/stdc++.h> using namespace std; void findQuadruplet( int arr[], int n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4) { cout << "No such Quadruple found" ; return ; } // Initializing the variables with // INT_MAX macros. // To store the min element. int small = INT_MAX; // To store the second minimum element. int second_small = INT_MAX; // To store the middle element. int mid = INT_MAX; // To remember the mid and the // minimum element. int min = 0; int main_mid = 0; int main_min = 0; // Traversing the array to find // the Quadruple for ( int i = 0; i < n; i++) { if (arr[i] <= small) { small = arr[i]; } else if (arr[i] <= second_small) { second_small = arr[i]; min = small; } else if (arr[i] <= mid) { mid = arr[i]; main_mid = second_small; main_min = min; } else { // If the number is greater than mid. cout << "Quadruplets: " << main_min << " " << main_mid << " " << mid << " " << arr[i]; // Return if Quadruple is found. return ; } } // If no Quadruple is found cout << "No such Quadruple" ; return ; } // Driver program int main() { int arr[] = { 1, 7, 4, 5, 3, 6 }; int N = sizeof (arr) / sizeof ( int ); findQuadruplet(arr, N); return 0; } |
Java
// Java program to find a sorted // sub-sequence of size 4 public class GFG { static void findQuadruplet( int arr[], int n) { int INT_MAX = Integer.MAX_VALUE; // If number of elements < 4 // then no Quadruple are possible if (n < 4 ) { System.out.print( "No such Quadruple found" ); return ; } // Initializing the variables with // INT_MAX macros. // To store the min element. int small = INT_MAX; // To store the second minimum element. int second_small = INT_MAX; // To store the middle element. int mid = INT_MAX; // To remember the mid and the // minimum element. int min = 0 ; int main_mid = 0 ; int main_min = 0 ; // Traversing the array to find // the Quadruple for ( int i = 0 ; i < n; i++) { if (arr[i] <= small) { small = arr[i]; } else if (arr[i] <= second_small) { second_small = arr[i]; min = small; } else if (arr[i] <= mid) { mid = arr[i]; main_mid = second_small; main_min = min; } else { // If the number is greater than mid. System.out.print( "Quadruplets: " + main_min + " " + main_mid + " " + mid + " " + arr[i]); // Return if Quadruple is found. return ; } } // If no Quadruple is found System.out.print( "No such Quadruple" ); return ; } // Driver program public static void main (String[] args) { int arr[] = { 1 , 7 , 4 , 5 , 3 , 6 }; int N = arr.length; findQuadruplet(arr, N); } } // This code is contributed by AnkThon |
Python3
# Python program to find a sorted # sub-sequence of size 4 import sys def findQuadruplet(arr, n): # If number of elements < 4 # then no Quadruple are possible if (n < 4 ): print ( "No such Quadruple found" ) return # Initializing the variables with # INT_MAX macros. # To store the min element. small = sys.maxsize # To store the second minimum element. second_small = sys.maxsize # To store the middle element. mid = sys.maxsize # To remember the mid and the # minimum element. min = 0 main_mid = 0 main_min = 0 # Traversing the array to find # the Quadruple for i in range (n): if (arr[i] < = small): small = arr[i] elif (arr[i] < = second_small): second_small = arr[i] min = small elif (arr[i] < = mid): mid = arr[i] main_mid = second_small main_min = min else : # If the number is greater than mid. print (f "Quadruplets: {main_min} {main_mid} {mid} {arr[i]}" ) # Return if Quadruple is found. return # If no Quadruple is found print ( "No such Quadruple" ) return # Driver program arr = [ 1 , 7 , 4 , 5 , 3 , 6 ] N = len (arr) findQuadruplet(arr, N); # This code is contributed by shinjanpatra |
C#
// C# program to find a sorted // sub-sequence of size 4 using System; public class GFG { static void findQuadruplet( int [] arr, int n) { int INT_MAX = int .MaxValue; // If number of elements < 4 // then no Quadruple are possible if (n < 4) { Console.Write( "No such Quadruple found" ); return ; } // Initializing the variables with // INT_MAX macros. // To store the min element. int small = INT_MAX; // To store the second minimum element. int second_small = INT_MAX; // To store the middle element. int mid = INT_MAX; // To remember the mid and the // minimum element. int min = 0; int main_mid = 0; int main_min = 0; // Traversing the array to find // the Quadruple for ( int i = 0; i < n; i++) { if (arr[i] <= small) { small = arr[i]; } else if (arr[i] <= second_small) { second_small = arr[i]; min = small; } else if (arr[i] <= mid) { mid = arr[i]; main_mid = second_small; main_min = min; } else { // If the number is greater than mid. Console.Write( "Quadruplets: " + main_min + " " + main_mid + " " + mid + " " + arr[i]); // Return if Quadruple is found. return ; } } // If no Quadruple is found Console.Write( "No such Quadruple" ); return ; } // Driver program public static void Main() { int [] arr = { 1, 7, 4, 5, 3, 6 }; int N = arr.Length; findQuadruplet(arr, N); } } // This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach function findQuadruplet(arr, n) { // If number of elements < 4 // then no Quadruple are possible if (n < 4) { document.write( "No such Quadruple found" ); return ; } // Initializing the variables with // Number.MAX_VALUE macros. // To store the min element. let small = Number.MAX_VALUE; // To store the second minimum element. let second_small = Number.MAX_VALUE; // To store the middle element. let mid = Number.MAX_VALUE; // To remember the mid and the // minimum element. let min = 0; let main_mid = 0; let main_min = 0; // Traversing the array to find // the Quadruple for (let i = 0; i < n; i++) { if (arr[i] <= small) { small = arr[i]; } else if (arr[i] <= second_small) { second_small = arr[i]; min = small; } else if (arr[i] <= mid) { mid = arr[i]; main_mid = second_small; main_min = min; } else { // If the number is greater than mid. document.write( "Quadruplets: " + main_min + " " + main_mid + " " + mid + " " + arr[i]); // Return if Quadruple is found. return ; } } // If no Quadruple is found document.write( "No such Quadruple" ); return ; } // Driver program let arr = [1, 7, 4, 5, 3, 6]; let N = arr.length; findQuadruplet(arr, N); // This code is contributed by Potta Lokesh </script> |
Quadruplets: 1 4 5 6
Time Complexity: O(N)
Auxiliary Space: O(1)