Mastering the "Sorted Subsequence of Size 3" Problem: Two Efficient Java Approaches

Finding a sorted subsequence of a specific size is a classic algorithmic challenge that tests your ability to optimize array traversals. The problem asks us to find three elements in an array such that arr[i] < arr[j] < arr[k] and their indices satisfy i < j < k.

If you are preparing for coding interviews or just sharpening your problem-solving skills, this problem is a fantastic way to transition from brute-force thinking to highly optimized logic.

In this post, we will explore two distinct approaches to solving this problem in Java: an intuitive Precomputation Approach and a highly optimized Single-Pass Greedy Approach.

---

Approach 1: The Prefix and Suffix Arrays (Precomputation)

The Intuition

To find our three numbers, let's focus on the middle element, arr[j]. For any element to act as a valid middle number in our sequence, two conditions must be met:

1. There must be a strictly smaller number somewhere to its left.
2. There must be a strictly larger number somewhere to its right.

Instead of scanning the left and right sides over and over for every single element, we can precalculate the smallest numbers on the left and the largest numbers on the right using auxiliary arrays.

How It Works

• prefixMin Array: We iterate from left to right, storing the minimum value seen so far at each index.
• suffixMax Array: We iterate from right to left, storing the maximum value seen so far at each index.
• Once these are built, we simply loop through the original array one last time. For any element arr[i], we check if its corresponding prefixMin[i] is smaller than arr[i] and its suffixMax[i] is larger than arr[i].

The Code

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public ArrayList<Integer> find3Numbers(int[] arr) {
        // code here
        if (arr == null || arr.length < 3) {
            return new ArrayList<>();
        }
        int length = arr.length;
        ArrayList<Integer> result = new ArrayList<>();
        int [] prefixMin = new int [length];
        int [] suffixMax = new int [length];
        Arrays.fill(prefixMin, Integer.MAX_VALUE);

        prefixMin[0] = arr[0];
        for (int index = 1; index < length; index++) {
            prefixMin[index] = Math.min(arr[index], prefixMin[index - 1]);
        }

        suffixMax[length - 1] = arr[length - 1];
        for (int index = length - 2; index >= 0; index--) {
            suffixMax[index] = Math.max(arr[index], suffixMax[index + 1]);
        }

        for (int index = 0; index < length; index++) {
            int middleNum = arr[index];
            int leftMin = prefixMin[index];
            int rightMax = suffixMax[index];

            if (leftMin < middleNum && middleNum < rightMax) {
                result.add(leftMin);
                result.add(middleNum);
                result.add(rightMax);
                break;
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(N). We traverse the array exactly three times: once to build prefixMin, once for suffixMax, and one final time to find the sequence. Dropping the constant gives us a linear time complexity.
• Space Complexity: O(N). We allocate two additional arrays, each of size N, to store our precomputed boundaries.

---

Approach 2: The Space-Optimized Single Pass (Greedy)

While the first approach is highly intuitive, creating two additional arrays consumes extra memory. What if the array is massive? We can solve this in a single pass with constant extra space by keeping a running track of the "smallest" and "second smallest" values.

The Intuition

As we iterate through the array, we want to build our sequence dynamically. We can do this by maintaining variables for the smallest element seen so far (verySmall) and the second smallest element (secondSmall).

The tricky part? If we find a new verySmall number, we can't just carelessly overwrite the old one if we already have a secondSmall paired with it. To solve this, this approach brilliantly introduces smallBeforeSecondSmall. This guarantees that when we finally find our third, largest number, we pair it with the exact minimum that historically came before our second-smallest number.

How It Works

1. Initialize verySmall, secondSmall, and smallBeforeSecondSmall to infinity.
2. Traverse the array:
   • If the current number is smaller than verySmall, update verySmall.
   • If it falls strictly between verySmall and secondSmall, update secondSmall and "lock in" the current verySmall into smallBeforeSecondSmall.
   • If we find a number strictly greater than secondSmall, we have found our trio!

The Code

class Solution {
    public ArrayList<Integer> find3Numbers(int[] arr) {
        // code here
        if (arr == null || arr.length < 3) {
            return new ArrayList<>();
        }
        int length = arr.length;
        ArrayList<Integer> result = new ArrayList<>();

        int verySmall = Integer.MAX_VALUE;
        int secondSmall = Integer.MAX_VALUE;
        int smallBeforeSecondSmall = Integer.MAX_VALUE;

        for (int num : arr) {
            if (num < verySmall) {
                verySmall = num;
            }
            else if (num > verySmall && num < secondSmall) {
                secondSmall = num;
                smallBeforeSecondSmall = verySmall;
            }
            else if (smallBeforeSecondSmall < secondSmall && secondSmall < num) {
                result.add(smallBeforeSecondSmall);
                result.add(secondSmall);
                result.add(num);
                break;
            }
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(N). We iterate through the array exactly once, performing basic comparison operations at each step.
• Space Complexity: O(1). Aside from the output ArrayList, we only use three integer variables, meaning our memory footprint remains constant regardless of the array's size.

---