In computational problem-solving, the challenge of finding a sorted subsequence of a specified size within a given array frequently arises. This article explores the methodology for identifying a sorted subsequence of size 4 in an array, achieving this in linear time, $O(n)$. This technique has practical applications in fields such as bioinformatics, data compression, and real-time data processing, where efficiency is paramount.

Problem Definition

Given an array `A` of `n` integers, the task is to find four indices `i, j, k, l` such that `i < j < k < l` and `A[i] < A[j] < A[k] < A[l]`. Unlike typical sorting requirements, the objective here is not to sort the entire array but to identify any one subsequence that fits the criteria.

Linear Time Solution

The solution to this problem capitalizes on maintaining auxiliary data structures to track potential candidates for the required subsequence while traversing the array just once.

Strategy

1. Initialization:
   • Maintain four lists: `first`, `second`, `third`, and `fourth` to store potential candidates for each position in the subsequence.
   • Use four arrays `f`, `s`, `t`, and `fo` to track indices of potential values throughout the array.
2. Forward Pass:
   • Define initial candidates for the `first` element while iterating through the array.
   • For each new element, update candidate lists for `second`, `third`, and `fourth` elements based on previously identified candidates.
3. Backtracking:
   • Once a potential last element of `fourth` is found, backtrack using the index arrays to construct the valid subsequence.

Example

Consider the array `A = [3, 2, 1, 2, 3, 6, 5, 0, 2, 4]`.

• First Pass: Begin by initializing the first element:
  • At index `0`, `first = [3]` and index `f = [0]`.
• Updating Candidates:
  • At index `1`, `A[1] = 2`, update `first` to `[2]` since it replaces `3` as a smaller candidate.
  • At index `3`, identify potential `second` as `2` (from `first`) and `third` as `3` (from `second`).
  • Continue this process, identifying the following indices:
    • `first = [1], second = [2], third = [3], fourth = [6]`.
• Subsequence Found:
  • The indices array now stores positions `[1, 3, 4, 5]` with values `[1, 2, 3, 6]`.

Implementation