Sorted subsequence of size 3

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find any three indices i<j<k where arr[i]<arr[j]<arr[k]. Track prefix minimum and suffix maximum.

Algorithm

1leftMin[i] = min of arr[0..i]. rightMax[i] = max of arr[i..n-1].
2For each j: if leftMin[j] < arr[j] < rightMax[j]: found.

Common Pitfalls

•Similar to LC 334 (increasing triplet subsequence). O(n) with two auxiliary arrays.

Sorted subsequence of size 3.java

Java

// Approach: Track min from left and max from right. Find middle element where left_min < mid < right_max.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {

    public ArrayList<Integer> find3Numbers(int[] arr) {
        int n = arr.length;

        if (n < 3) {
            return new ArrayList<>(); // No such triplet exists
        }

        // Create arrays to store the leftMin and rightMax values
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];

        // Initialize leftMin array
        leftMin[0] = arr[0];
        for (int i = 1; i < n; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], arr[i]);
        }

        // Initialize rightMax array
        rightMax[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], arr[i]);
        }

        // Find the triplet
        for (int i = 1; i < n - 1; i++) {
            if (arr[i] > leftMin[i - 1] && arr[i] < rightMax[i + 1]) {
                ArrayList<Integer> result = new ArrayList<>();
                result.add(leftMin[i - 1]);
                result.add(arr[i]);
                result.add(rightMax[i + 1]);
                return result;
            }
        }

        // If no triplet is found
        return new ArrayList<>();
    }
}

Was this solution helpful?