Sorted subsequence of size 3

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:

1. The output will be 1 if the subsequence returned by the function is present in the array arr
2. If the subsequence is not present in the array then return an empty array, the driver code will print 0.
3. 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() <= 10⁵
1 <= arr[i] <= 10⁶

Approach 01:

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 and largestSuffix, 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 array arr.

• 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 and largestSuffix, each of size n. 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) \).