Sorted subsequence of size 3
Easy Accuracy: 45.69% Submissions: 17170 Points: 2
Given an array A of N integers, find any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k.
Example 1:
Input:
N = 5
A[] = {1,2,1,1,3}
Output: 1
Explanation: a sub-sequence 1 2 3 exist.
Example 2:
Input:
N = 3
A[] = {1,1,3}
Output: 0
Explanation: no such sub-sequence exist.
Your Task:
Your task is to complete the function find3Numbers which finds any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. You need to return them as a vector/ArrayList/array (depending on the language cpp/Java/Python), if no such element is present then return the empty vector of size 0.
Note: The output will be 1 if the sub-sequence returned by the function is present in array A else 0. If the sub-sequence returned by the function is not in the format as mentioned then the output will be -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 105
1 <= A[i] <= 106, for each valid i
ksoni-1258
commented
3 years ago
Example 1:
Input: N = 5 A[] = {1,2,1,1,3} Output: 1 Explanation: a sub-sequence 1 2 3 exist. Example 2:
Input: N = 3 A[] = {1,1,3} Output: 0 Explanation: no such sub-sequence exist. Your Task: Your task is to complete the function find3Numbers which finds any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. You need to return them as a vector/ArrayList/array (depending on the language cpp/Java/Python), if no such element is present then return the empty vector of size 0.
Note: The output will be 1 if the sub-sequence returned by the function is present in array A else 0. If the sub-sequence returned by the function is not in the format as mentioned then the output will be -1.
Expected Time Complexity: O(N) Expected Auxiliary Space: O(N)
Constraints: 1 <= N <= 105 1 <= A[i] <= 106, for each valid i