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

DEV Community

arr[j]. For any element to act as a valid middle number in our sequence, two conditions must be met:

There must be a strictly smaller number somewhere to its left.
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

Initialize verySmall, secondSmall, and smallBeforeSecondSmall to infinity.
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.