You are given an array arr, you need to find any three elements in it such that arr[i] < arr[j] < arr[k] and i < j < k.
Note:
- The output will be 1 if the subsequence returned by the function is present in the array arr
- If the subsequence is not present in the array then return an empty array, the driver code will print 0.
- If the subsequence returned by the function is not in the format as mentioned then the output will be -1.
Examples :
Input: arr = [1, 2, 1, 1, 3] Output: 1 Explanation: A subsequence 1 2 3 exist.
Input: arr = [1, 1, 3] Output: 0 Explanation: No such Subsequence exist, so empty array is returned (the driver code automatically prints 0 in this case).
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= arr.size() <= 105
1 <= arr[i] <= 106
Approach 01:
-
C++
-
Python
class Solution { public: vector<int> find3Numbers(vector<int> &arr) { int numElements = arr.size(); vector<int> smallestPrefix(numElements, 1e9); smallestPrefix[0] = arr[0]; // Fill smallestPrefix array with the smallest element up to that index for (int i = 1; i < numElements; i++) { smallestPrefix[i] = min(arr[i], smallestPrefix[i - 1]); } vector<int> largestSuffix(numElements, INT_MIN); largestSuffix[numElements - 1] = arr[numElements - 1]; // Fill largestSuffix array with the largest element from that index onwards for (int i = numElements - 2; i >= 0; i--) { largestSuffix[i] = max(arr[i], largestSuffix[i + 1]); } // Find a triplet (smallestPrefix[i], arr[i], largestSuffix[i]) that satisfies the condition for (int i = 0; i < numElements; i++) { if (arr[i] > smallestPrefix[i] && arr[i] < largestSuffix[i]) { return {smallestPrefix[i], arr[i], largestSuffix[i]}; } } return {}; } };
from typing import List class Solution: def find3Numbers(self, arr: List[int]) -> List[int]: numElements = len(arr) smallestPrefix = [float('inf')] * numElements smallestPrefix[0] = arr[0] # Fill smallestPrefix array with the smallest element up to that index for i in range(1, numElements): smallestPrefix[i] = min(arr[i], smallestPrefix[i - 1]) largestSuffix = [float('-inf')] * numElements largestSuffix[numElements - 1] = arr[numElements - 1] # Fill largestSuffix array with the largest element from that index onwards for i in range(numElements - 2, -1, -1): largestSuffix[i] = max(arr[i], largestSuffix[i + 1]) # Find a triplet (smallestPrefix[i], arr[i], largestSuffix[i]) that satisfies the condition for i in range(numElements): if arr[i] > smallestPrefix[i] and arr[i] < largestSuffix[i]: return [smallestPrefix[i], arr[i], largestSuffix[i]] return []
Time Complexity
- Prefix and Suffix Array Calculation:
The algorithm constructs two arrays,
smallestPrefix
andlargestSuffix
, to store the smallest and largest elements up to and from each index, respectively.Both arrays are filled in linear time using separate loops. Each loop runs for
numElements
iterations, so the time complexity for this step is \( O(n) \), where \( n \) is the size of the input arrayarr
. - Finding the Triplet:
The algorithm scans the entire array once more to find a triplet that satisfies the condition. This loop also takes \( O(n) \) time.
- Overall Time Complexity:
The overall time complexity is \( O(n) \) due to the three linear passes through the array.
Space Complexity
- Space for Prefix and Suffix Arrays:
The solution uses two additional arrays,
smallestPrefix
andlargestSuffix
, each of sizen
. Therefore, the space complexity for storing these arrays is \( O(n) \). - Overall Space Complexity:
Since the space used is dominated by the two additional arrays, the overall space complexity is \( O(n) \).