DSA-133 · Minimum tail dominance with lower-bound binary search

Longest Increasing Subsequence

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9857 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the length of a longest strictly increasing subsequence of nums. A subsequence may delete elements but must preserve the original order; equal consecutive chosen values are not increasing.

nums is a non-null int[] of at most 100000 entries. Every signed int value is valid, including MIN_VALUE and MAX_VALUE. Null throws NullPointerException and an oversized array throws IllegalArgumentException.
Return an int length in 0..nums.length. Empty input returns zero. Duplicates cannot extend a strict subsequence, and no sorting or mutation of nums is permitted.
Return only a length. The optimized tails array stores best endpoints for different lengths; it is not promised to be a realizable subsequence or an output witness. The quadratic baseline is correct for the same input contract but only practical on bounded small tests.

Examples

Input: nums=[10,9,2,5,3,7,101,18]
Output: 4
One witness is [2,3,7,18]. The answer does not require returning a witness.
Input: nums=[2,2,2]
Output: 1
Equal values replace the same endpoint rather than extending a strict sequence.
Input: nums=[3,5,6,2,4]
Output: 3
The final minimum tails are [2,4,6], but those values do not occur in that order. [3,5,6] is a valid length-three witness.
Input: nums=[]
Output: 0
There is no selected value.

Before you start

Strict subsequences preserve original index order
Lower bound and dominance of future extension options

Recognize the structure

A quadratic DP can keep the best strict subsequence ending at each index. To improve it, compare partial subsequences of equal length: the one with the smaller last value can be extended by every future value that extends a larger tail. Therefore the minimum tail for each length dominates larger tails, even though the representative subsequences for different lengths need not coexist.

Try before revealing

Hint 1

For two subsequences of equal length, which endpoint is easier for future values to extend?

Hint 2

Store the minimum endpoint for every attainable length and examine whether these endpoints are sorted.

Hint 3

Replace the first tail ≥x; append only when x is larger than all active tails.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Best subsequence ending at each original index

Set ending[i]=1. For every earlier j with nums[j]<nums[i], consider ending[j]+1 and maximize ending[i]. The answer is the maximum ending value, with zero for an empty array. Earlier indices guarantee the chosen subsequence order. This O(n²) method is already a valid DP and is useful for witness reconstruction. It is the baseline because minimum-tail dominance removes the need to inspect all earlier endpoints. Tests compare both methods with a separate oracle that enumerates index subsets and validates strict order.

Improve the baseline

Retain a state per attainable length

tails[k] is the smallest possible final value of a strict subsequence of length k+1 in the processed prefix. size is the number of attainable positive lengths. Only tails[0..size) is meaningful; the remaining allocated cells are not states or sentinels.

Show why the active tails are strictly increasing

A subsequence of length k+2 ending at value v has a length k+1 prefix whose final value is strictly smaller than v. The minimal tail for that shorter length is no larger than this prefix endpoint. Thus adjacent minimum tails are ordered strictly, enabling binary search.

Find the first tail at least the new value

For value x, lower_bound finds the first active tails[k]≥x. Every earlier tail is <x and can precede x, so a length k+1 subsequence ending at x is feasible. Any longer extension would require a tail <x at index k or beyond, which the boundary excludes. Use the first ≥, not first >, to prevent equal values from extending strict sequences.

Replace or append without losing optimal options

Write tails[k]=x. If k<size, x improves or preserves the minimum tail for that length. If k==size, x extends the longest existing subsequence and size increases. Process input in its original order; sorting would change the question. Binary search compares ints directly and computes mid without subtracting input values.

Do not confuse endpoint representatives with one witness

For [3,5,6,2,4], tails becomes [3], [3,5], [3,5,6], [2,5,6], then [2,4,6]. The last 6 still represents an earlier feasible length-three sequence. The endpoint values in one final tails array can refer to different histories, so copying that array is not valid reconstruction.

Why it is correct

Empty processed prefix

No positive-length subsequence is attainable before reading input, so size=0 and no allocated tails cell is meaningful.

Dominance-preserving update

Assume each active cell is a feasible minimum endpoint. The lower-bound predecessor, if present, is strictly smaller than x, so x realizes the new candidate length. A smaller endpoint for a fixed length never removes a future extension option. The boundary also proves x cannot create a longer subsequence than k+1, preserving every minimum-tail meaning after replacement or append.

Length optimality and termination

The invariant makes every active length feasible and rules out a longer unrepresented length. Each finite input value performs a binary search whose half-open interval shrinks and one update. After the final value, size equals the maximum feasible length. The caller array remains unchanged, and direct comparisons are safe at signed-int extremes.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(int[] nums) {
        Objects.requireNonNull(nums, "nums");
        if (nums.length > 100_000) throw new IllegalArgumentException("too many values");
    }
    public static int lengthOfLIS(int[] nums) {
        validate(nums);
        int[] tails = new int[nums.length];
        int size = 0;
        for (int value : nums) {
            int low = 0, high = size;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (tails[mid] < value) low = mid + 1;
                else high = mid;
            }
            tails[low] = value;
            if (low == size) size++;
        }
        return size;
    }
    // Baseline: best strict subsequence ending at each original index.
    public static int baseline(int[] nums) {
        validate(nums);
        int[] ending = new int[nums.length]; int best = 0;
        for (int i = 0; i < nums.length; i++) {
            ending[i] = 1;
            for (int j = 0; j < i; j++) if (nums[j] < nums[i]) ending[i] = Math.max(ending[i], ending[j] + 1);
            best = Math.max(best, ending[i]);
        }
        return best;
    }
}

Read the meaningful blocks

Allocate private tails and an empty active prefix

The array has capacity n but size starts at zero. Its default zero values must never enter a search before becoming meaningful endpoints; otherwise all-negative inputs can be misclassified.

Search a half-open boundary range

low=0 and high=size describe a possible insertion boundary, including size. tails[mid]<value discards the lower part; otherwise high=mid retains the first tail that is at least value. The loop ends with exactly one boundary.

Update the endpoint, then the active length

Writing tails[low] is safe even when low==size because another input value is still being processed and size<n. Increase size only on append. Return size, rather than the last endpoint value or the allocated array length.

Complexity

For n values, the reference uses O(n log(n+1)+1) time and O(n) auxiliary int storage, with an int output. Searches actually depend on the current LIS length; an O(n log(L+1)+1) bound applies for final length L. Contract checking is constant time because all int values are valid.

The baseline takes O(n²+1) time and O(n) auxiliary storage. Both methods preserve input order. Returning one actual subsequence requires predecessor indices and endpoint indices, generally O(n) extra history; the value-only tails representatives are insufficient as a witness.

Exact-state walkthroughs

Reveal normal and boundary traces

Minimum tails need not coexist as a witness

Input: [3,5,6,2,4] · Strict LIS length: 3

Step 1 of 19: Start with no attainable positive subsequence length.

Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.

Strict LIS — minimum endpoints and lower-bound search

Phase: initial.

Input order stays fixed. Only occurrences before or at the current decision can influence the active summary.

0: 3
1: 5
2: 6
3: 2
4: 4

Active minimum tails — not one reconstructed subsequence

No positive length is attainable yet.

Every tail has its own feasible index history. Minimum tails are strictly ordered and preserve all future extension options, but the final displayed values may not occur together in that order.

State after this step
Variable	Value
input	`[3,5,6,2,4]`
phase	`"initial"`
tails	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many values");
 8     }
 9     public static int lengthOfLIS(int[] nums) {
10         validate(nums);
11         int[] tails = new int[nums.length];
12         int size = 0;
13         for (int value : nums) {
14             int low = 0, high = size;
15             while (low < high) {
16                 int mid = low + (high - low) / 2;
17                 if (tails[mid] < value) low = mid + 1;
18                 else high = mid;
19             }
20             tails[low] = value;
21             if (low == size) size++;
22         }
23         return size;
24     }
25     // Baseline: best strict subsequence ending at each original index.
26     public static int baseline(int[] nums) {
27         validate(nums);
28         int[] ending = new int[nums.length]; int best = 0;
29         for (int i = 0; i < nums.length; i++) {
30             ending[i] = 1;
31             for (int j = 0; j < i; j++) if (nums[j] < nums[i]) ending[i] = Math.max(ending[i], ending[j] + 1);
32             best = Math.max(best, ending[i]);
33         }
34         return best;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no attainable positive subsequence length.
Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.
input
[3,5,6,2,4]
phase
"initial"
tails
[]
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[3,5,6,2,4]
phase
"search"
tails
[]
index
0
value
3
low
0
high
0
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[3,5,6,2,4]
phase
"replace"
tails
[3]
index
0
value
3
low
0
high
0
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[3,5,6,2,4]
phase
"search"
tails
[3]
index
1
value
5
low
0
high
1
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[3]
index
1
value
5
low
1
high
1
wasLow
0
wasHigh
1
mid
0
probeValue
3
smaller
true
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[3,5,6,2,4]
phase
"replace"
tails
[3,5]
index
1
value
5
low
1
high
1
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[3,5,6,2,4]
phase
"search"
tails
[3,5]
index
2
value
6
low
0
high
2
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[3,5]
index
2
value
6
low
2
high
2
wasLow
0
wasHigh
2
mid
1
probeValue
5
smaller
true
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[3,5,6,2,4]
phase
"replace"
tails
[3,5,6]
index
2
value
6
low
2
high
2
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[3,5,6,2,4]
phase
"search"
tails
[3,5,6]
index
3
value
2
low
0
high
3
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[3,5,6]
index
3
value
2
low
0
high
1
wasLow
0
wasHigh
3
mid
1
probeValue
5
smaller
false
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[3,5,6]
index
3
value
2
low
0
high
0
wasLow
0
wasHigh
1
mid
0
probeValue
3
smaller
false
Improve or preserve a minimum endpoint for this length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[3,5,6,2,4]
phase
"replace"
tails
[2,5,6]
index
3
value
2
low
0
high
0
replaced
3
extended
false
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[3,5,6,2,4]
phase
"search"
tails
[2,5,6]
index
4
value
4
low
0
high
3
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[2,5,6]
index
4
value
4
low
0
high
1
wasLow
0
wasHigh
3
mid
1
probeValue
5
smaller
false
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[3,5,6,2,4]
phase
"probe"
tails
[2,5,6]
index
4
value
4
low
1
high
1
wasLow
0
wasHigh
1
mid
0
probeValue
2
smaller
true
Improve or preserve a minimum endpoint for this length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[3,5,6,2,4]
phase
"replace"
tails
[2,4,6]
index
4
value
4
low
1
high
1
replaced
5
extended
false
Return the number of attainable positive lengths.
Minimum-tail dominance retains every future extension option. The original input has not been sorted or changed.
input
[3,5,6,2,4]
phase
"complete"
tails
[2,4,6]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
3

Equal values do not extend

Input: [2,2,2] · Strict LIS length: 1

Step 1 of 11: Start with no attainable positive subsequence length.

Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.

Strict LIS — minimum endpoints and lower-bound search

Phase: initial.

Input order stays fixed. Only occurrences before or at the current decision can influence the active summary.

0: 2
1: 2
2: 2

Active minimum tails — not one reconstructed subsequence

No positive length is attainable yet.

Every tail has its own feasible index history. Minimum tails are strictly ordered and preserve all future extension options, but the final displayed values may not occur together in that order.

State after this step
Variable	Value
input	`[2,2,2]`
phase	`"initial"`
tails	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many values");
 8     }
 9     public static int lengthOfLIS(int[] nums) {
10         validate(nums);
11         int[] tails = new int[nums.length];
12         int size = 0;
13         for (int value : nums) {
14             int low = 0, high = size;
15             while (low < high) {
16                 int mid = low + (high - low) / 2;
17                 if (tails[mid] < value) low = mid + 1;
18                 else high = mid;
19             }
20             tails[low] = value;
21             if (low == size) size++;
22         }
23         return size;
24     }
25     // Baseline: best strict subsequence ending at each original index.
26     public static int baseline(int[] nums) {
27         validate(nums);
28         int[] ending = new int[nums.length]; int best = 0;
29         for (int i = 0; i < nums.length; i++) {
30             ending[i] = 1;
31             for (int j = 0; j < i; j++) if (nums[j] < nums[i]) ending[i] = Math.max(ending[i], ending[j] + 1);
32             best = Math.max(best, ending[i]);
33         }
34         return best;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no attainable positive subsequence length.
Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.
input
[2,2,2]
phase
"initial"
tails
[]
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[2,2,2]
phase
"search"
tails
[]
index
0
value
2
low
0
high
0
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[2,2,2]
phase
"replace"
tails
[2]
index
0
value
2
low
0
high
0
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[2,2,2]
phase
"search"
tails
[2]
index
1
value
2
low
0
high
1
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[2,2,2]
phase
"probe"
tails
[2]
index
1
value
2
low
0
high
0
wasLow
0
wasHigh
1
mid
0
probeValue
2
smaller
false
Improve or preserve a minimum endpoint for this length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[2,2,2]
phase
"replace"
tails
[2]
index
1
value
2
low
0
high
0
replaced
2
extended
false
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[2,2,2]
phase
"search"
tails
[2]
index
2
value
2
low
0
high
1
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[2,2,2]
phase
"probe"
tails
[2]
index
2
value
2
low
0
high
0
wasLow
0
wasHigh
1
mid
0
probeValue
2
smaller
false
Improve or preserve a minimum endpoint for this length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[2,2,2]
phase
"replace"
tails
[2]
index
2
value
2
low
0
high
0
replaced
2
extended
false
Return the number of attainable positive lengths.
Minimum-tail dominance retains every future extension option. The original input has not been sorted or changed.
input
[2,2,2]
phase
"complete"
tails
[2]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
1

Empty active prefix

Input: [] · Strict LIS length: 0

Step 1 of 3: Start with no attainable positive subsequence length.

Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.

Strict LIS — minimum endpoints and lower-bound search

Phase: initial.

Input order stays fixed. Only occurrences before or at the current decision can influence the active summary.

Active minimum tails — not one reconstructed subsequence

No positive length is attainable yet.

Every tail has its own feasible index history. Minimum tails are strictly ordered and preserve all future extension options, but the final displayed values may not occur together in that order.

State after this step
Variable	Value
input	`[]`
phase	`"initial"`
tails	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many values");
 8     }
 9     public static int lengthOfLIS(int[] nums) {
10         validate(nums);
11         int[] tails = new int[nums.length];
12         int size = 0;
13         for (int value : nums) {
14             int low = 0, high = size;
15             while (low < high) {
16                 int mid = low + (high - low) / 2;
17                 if (tails[mid] < value) low = mid + 1;
18                 else high = mid;
19             }
20             tails[low] = value;
21             if (low == size) size++;
22         }
23         return size;
24     }
25     // Baseline: best strict subsequence ending at each original index.
26     public static int baseline(int[] nums) {
27         validate(nums);
28         int[] ending = new int[nums.length]; int best = 0;
29         for (int i = 0; i < nums.length; i++) {
30             ending[i] = 1;
31             for (int j = 0; j < i; j++) if (nums[j] < nums[i]) ending[i] = Math.max(ending[i], ending[j] + 1);
32             best = Math.max(best, ending[i]);
33         }
34         return best;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no attainable positive subsequence length.
Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.
input
[]
phase
"initial"
tails
[]
Return the number of attainable positive lengths.
Minimum-tail dominance retains every future extension option. The original input has not been sorted or changed.
input
[]
phase
"complete"
tails
[]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
0

Signed-int extremes

Input: [-2147483648,0,2147483647] · Strict LIS length: 3

Step 1 of 11: Start with no attainable positive subsequence length.

Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.

Strict LIS — minimum endpoints and lower-bound search

Phase: initial.

Input order stays fixed. Only occurrences before or at the current decision can influence the active summary.

0: -2147483648
1: 0
2: 2147483647

Active minimum tails — not one reconstructed subsequence

No positive length is attainable yet.

Every tail has its own feasible index history. Minimum tails are strictly ordered and preserve all future extension options, but the final displayed values may not occur together in that order.

State after this step
Variable	Value
input	`[-2147483648,0,2147483647]`
phase	`"initial"`
tails	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(int[] nums) {
 6         Objects.requireNonNull(nums, "nums");
 7         if (nums.length > 100_000) throw new IllegalArgumentException("too many values");
 8     }
 9     public static int lengthOfLIS(int[] nums) {
10         validate(nums);
11         int[] tails = new int[nums.length];
12         int size = 0;
13         for (int value : nums) {
14             int low = 0, high = size;
15             while (low < high) {
16                 int mid = low + (high - low) / 2;
17                 if (tails[mid] < value) low = mid + 1;
18                 else high = mid;
19             }
20             tails[low] = value;
21             if (low == size) size++;
22         }
23         return size;
24     }
25     // Baseline: best strict subsequence ending at each original index.
26     public static int baseline(int[] nums) {
27         validate(nums);
28         int[] ending = new int[nums.length]; int best = 0;
29         for (int i = 0; i < nums.length; i++) {
30             ending[i] = 1;
31             for (int j = 0; j < i; j++) if (nums[j] < nums[i]) ending[i] = Math.max(ending[i], ending[j] + 1);
32             best = Math.max(best, ending[i]);
33         }
34         return best;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Start with no attainable positive subsequence length.
Only active minimum tails are displayed. Unused cells of the allocated Java array have no state meaning.
input
[-2147483648,0,2147483647]
phase
"initial"
tails
[]
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[-2147483648,0,2147483647]
phase
"search"
tails
[]
index
0
value
-2147483648
low
0
high
0
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[-2147483648,0,2147483647]
phase
"replace"
tails
[-2147483648]
index
0
value
-2147483648
low
0
high
0
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[-2147483648,0,2147483647]
phase
"search"
tails
[-2147483648]
index
1
value
0
low
0
high
1
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[-2147483648,0,2147483647]
phase
"probe"
tails
[-2147483648]
index
1
value
0
low
1
high
1
wasLow
0
wasHigh
1
mid
0
probeValue
-2147483648
smaller
true
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[-2147483648,0,2147483647]
phase
"replace"
tails
[-2147483648,0]
index
1
value
0
low
1
high
1
replaced
null
extended
true
Search the active tails for the first value at least x.
The lower-bound interval is half-open and includes an insertion boundary at size. Equal values must replace rather than extend a strict subsequence.
input
[-2147483648,0,2147483647]
phase
"search"
tails
[-2147483648,0]
index
2
value
2147483647
low
0
high
2
Narrow the lower-bound interval using a direct int comparison.
Every excluded lower tail is strictly smaller than x. The first tail at least x remains in the candidate boundary range; no subtraction of input values can overflow.
input
[-2147483648,0,2147483647]
phase
"probe"
tails
[-2147483648,0]
index
2
value
2147483647
low
2
high
2
wasLow
0
wasHigh
2
mid
1
probeValue
0
smaller
true
Append a newly attainable length.
Each minimum endpoint has its own feasible history. The displayed tails need not coexist in original index order and are not a reconstructed LIS.
input
[-2147483648,0,2147483647]
phase
"replace"
tails
[-2147483648,0,2147483647]
index
2
value
2147483647
low
2
high
2
replaced
null
extended
true
Return the number of attainable positive lengths.
Minimum-tail dominance retains every future extension option. The original input has not been sorted or changed.
input
[-2147483648,0,2147483647]
phase
"complete"
tails
[-2147483648,0,2147483647]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
3

Test the contract

Input: nums=[3,2,1]
Output: 1
Strictly decreasing input.
Input: nums=[-3,-2,-1]
Output: 3
Negative values need no sentinel.
Input: nums=[-2147483648,0,2147483647]
Output: 3
Full signed-int comparisons.
Input: nums=[0,1,0,3,2,3]
Output: 4
Replacements preserve future options.
Input: nums=[7]
Output: 1
One occurrence.
Input: nums=null
Output: NullPointerException
Null is not empty.

Common mistakes and counterexamples

Sort the input before scanning

Counterexample: [3,2,1] would become increasing after sorting, but its original LIS length is one.

Preserve index order and keep only a private endpoint summary.

Use an upper bound for strict LIS

Counterexample: [2,2,2] would extend to length three if the boundary is first tail >2.

Find the first tail ≥value. Upper bound belongs to a nondecreasing variant.

Treat the tails array as a chosen subsequence

Counterexample: Final tails [2,4,6] for [3,5,6,2,4] has impossible index order.

Store predecessor identities if a witness is needed.

Use zero as a sentinel or subtract values to compare

Counterexample: All-negative values are valid and MAX−MIN can overflow.

Search only the meaningful prefix and use direct relational comparisons.

Follow-ups

Return one actual LIS.

Track the original index realizing each tail length and a predecessor index for every input occurrence. On an update, link the new occurrence to the current endpoint of the previous length. Backtrack from the final longest endpoint, then reverse indices. Tie rules affect which witness is returned, not its validity.

Find a longest nondecreasing subsequence.

Change the extension relation to ≤. Search for the first tail strictly greater than x so equal values extend. Revisit the ordered-tail invariant and retain original index order. This is a different contract rather than a harmless tie-breaking adjustment.

Count the number of longest subsequences.

The minimum-tail summary discards multiplicity and cannot simply carry one count per tail. Start with an O(n²) length/count DP, adding counts from compatible predecessors with optimal length. For faster solutions, coordinate-compress values and query a Fenwick/segment tree of best-length/count pairs, keeping strict comparisons and an explicit count-overflow policy.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 108/20,000 characters

Self-review

I can define a minimum tail for a length and prove dominance, not just memorize binary search.I can distinguish lower versus upper bound and preserve the active-prefix meaning.I can explain why final tails need not be a witness and how predecessor indices recover one.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.