Definition
- Longest Increasing Subsequence (LIS) – the longest subsequence of an array where every element is strictly greater than the previous one (elements need not be contiguous).
- Tails array –
tails[k]holds the smallest possible tail value of an increasing subsequence of length k + 1. - Binary search – for each number, find the leftmost tail that is >= the number; replace it (or append if larger than all tails).
- Invariant – the tails array is always sorted, which enables binary search.
- Complexity – O(n log n) time, O(n) space.
- Reconstruction – tails does not store the actual LIS; parent pointers are needed to recover it.
A portfolio analyst at the National Bank of India scans a daily stream of closing prices and tracks the longest run of strictly rising prices, not necessarily on consecutive days. She keeps a shelf of candidate runs ordered by their smallest ending value and slots each new price into the tightest fit, which keeps every run as extendable as possible for future prices.
Understanding the Concepts
What is the Longest Increasing Subsequence problem?
Given an array of integers, find the length of the longest subsequence where every element is strictly greater than the previous one. Elements do not need to be contiguous. For example, in [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 101] with length 4.
This is LeetCode 300 and a classic dynamic programming plus binary search problem.
package com.bank.service;
// Stock prices over 8 days: [10, 9, 2, 5, 3, 7, 101, 18]
// LIS: [2, 3, 7, 101] or [2, 3, 7, 18] -> length 4
// These are the longest stretches of rising prices (non-contiguous)
How does the O(n squared) DP approach work?
The naive DP defines dp[i] as the length of the LIS ending at index i. For each i, check all previous indices j where nums[j] < nums[i] and set dp[i] = max(dp[i], dp[j] + 1). The answer is max(dp[i]) over all i.
This works but is O(n squared), which is too slow for large arrays.
package com.bank.service;
public class LisNaive {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
}
How does the O(n log n) patience sort approach work?
- Maintain a list called
tails. For each number x: - Binary-search for the leftmost position in tails where
tails[pos] >= x. - If no such position exists (x is larger than all tails), append x. This means x extends the longest run.
- Otherwise, replace
tails[pos]with x. A smaller tail keeps future extension easier.
The tails array is always sorted, which is exactly why binary search is valid. After processing all numbers, tails.size() is the LIS length.
package com.bank.service;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class LisFast {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int x : nums) {
int pos = Collections.binarySearch(tails, x);
if (pos < 0) {
pos = -(pos + 1); // insertion point
}
if (pos == tails.size()) {
tails.add(x); // extends the longest run
} else {
tails.set(pos, x); // smaller tail, more extendable
}
}
return tails.size();
}
public static void main(String[] args) {
int[] prices = {10, 9, 2, 5, 3, 7, 101, 18};
LisFast solver = new LisFast();
System.out.println("LIS length: " + solver.lengthOfLIS(prices));
}
}
LIS length: 4
What does the tails array look like during execution?
Walk through [10, 9, 2, 5, 3, 7, 101, 18]:
1. x=10: tails=[], append -> tails=[10] 2. x=9: pos=0 (9 < 10), replace -> tails=[9] 3. x=2: pos=0 (2 < 9), replace -> tails=[2] 4. x=5: pos=1 (5 > 2), append -> tails=[2, 5] 5. x=3: pos=1 (3 < 5), replace -> tails=[2, 3] 6. x=7: pos=2 (7 > 3), append -> tails=[2, 3, 7] 7. x=101: pos=3, append -> tails=[2, 3, 7, 101] 8. x=18: pos=3 (18 < 101), replace -> tails=[2, 3, 7, 18]
Final tails length = 4. Note: tails=[2, 3, 7, 18] but the actual LIS could be [2, 5, 7, 101]. Tails is not the LIS.
package com.bank.service;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TailsTracer {
public static void main(String[] args) {
int[] prices = {10, 9, 2, 5, 3, 7, 101, 18};
List<Integer> tails = new ArrayList<>();
for (int x : prices) {
int pos = Collections.binarySearch(tails, x);
if (pos < 0) pos = -(pos + 1);
if (pos == tails.size()) tails.add(x);
else tails.set(pos, x);
System.out.println("x=" + x + " tails=" + tails);
}
}
}
x=10 tails=[10]
x=9 tails=[9]
x=2 tails=[2]
x=5 tails=[2, 5]
x=3 tails=[2, 3]
x=7 tails=[2, 3, 7]
x=101 tails=[2, 3, 7, 101]
x=18 tails=[2, 3, 7, 18]
Why is tails not the actual LIS?
Tails is a length-tracking device, not a subsequence recorder. The replacements optimize for extendability, not for preserving a real subsequence. In the example above, the final tails are [2, 3, 7, 18], but 18 replaced 101, so the real subsequence that achieved length 4 was [2, 5, 7, 101] or [2, 3, 7, 101].
To reconstruct the actual LIS, maintain parent pointers: for each number, record which previous number it extends.
package com.bank.service;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class LisReconstruct {
public List<Integer> findLIS(int[] nums) {
int n = nums.length;
List<Integer> tails = new ArrayList<>();
int[] tailIndices = new int[n]; // which index in nums is the tail
int[] parent = new int[n];
Arrays.fill(parent, -1);
int[] posToIndex = new int[n]; // tails[pos] came from nums[posToIndex[pos]]
for (int i = 0; i < n; i++) {
int pos = Collections.binarySearch(tails, nums[i]);
if (pos < 0) pos = -(pos + 1);
if (pos == tails.size()) tails.add(nums[i]);
else tails.set(pos, nums[i]);
posToIndex[pos] = i;
parent[i] = pos > 0 ? posToIndex[pos - 1] : -1;
}
// Backtrack from the last element
List<Integer> lis = new ArrayList<>();
int idx = posToIndex[tails.size() - 1];
while (idx != -1) {
lis.add(nums[idx]);
idx = parent[idx];
}
Collections.reverse(lis);
return lis;
}
public static void main(String[] args) {
int[] prices = {10, 9, 2, 5, 3, 7, 101, 18};
LisReconstruct solver = new LisReconstruct();
System.out.println("LIS: " + solver.findLIS(prices));
}
}
LIS: [2, 3, 7, 18]
What about strictly increasing vs non-decreasing?
- The strictness of the subsequence depends on the binary search bound:
- Lower bound (leftmost position where
tails[pos] >= x): strictly increasing. Equal values get replaced, not appended. - Upper bound (leftmost position where
tails[pos] > x): non-decreasing. Equal values can be appended.
package com.bank.service;
public class StrictnessDemo {
// For strictly increasing: use lower_bound (the default binarySearch behavior)
// For non-decreasing: find first position where tails[pos] > x
public static void main(String[] args) {
int[] nums = {3, 5, 5, 7};
// Strictly increasing LIS: [3, 5, 7] length 3
// Non-decreasing LIS: [3, 5, 5, 7] length 4
}
}
What are the edge cases?
- **Empty array**: return 0. - **All decreasing**: `[5, 4, 3, 2, 1]` -> LIS length 1 (each element alone). - **All increasing**: `[1, 2, 3, 4, 5]` -> LIS length 5 (the entire array). - **All equal**: `[7, 7, 7]` -> strictly increasing LIS length 1. - **Single element**: LIS length 1.
package com.bank.service;
public class LisEdgeCases {
public static void main(String[] args) {
LisFast solver = new LisFast();
System.out.println("Decreasing: " + solver.lengthOfLIS(new int[]{5,4,3,2,1}));
System.out.println("Increasing: " + solver.lengthOfLIS(new int[]{1,2,3,4,5}));
System.out.println("All equal: " + solver.lengthOfLIS(new int[]{7,7,7}));
System.out.println("Single: " + solver.lengthOfLIS(new int[]{42}));
}
}
Decreasing: 1
Increasing: 5
All equal: 1
Single: 1
What about the banking use case?
At the National Bank of India, the portfolio analytics desk needs the longest stretch of rising closing prices for a stock to judge momentum. Those rising days do not have to be consecutive. The naive O(n squared) approach is too slow on multi-year daily histories, so the patience-sorting method with binary search gives the answer in O(n log n) time.
package com.bank.service;
public class MomentumAnalyzer {
public static void main(String[] args) {
int[] closingPrices = {150, 140, 145, 155, 148, 160, 170, 165, 180};
LisFast solver = new LisFast();
int momentum = solver.lengthOfLIS(closingPrices);
System.out.println("Longest rising streak (non-contiguous): " + momentum + " days");
}
}
Longest rising streak (non-contiguous): 6 days
What are common interview follow-up questions?
- What is the time complexity? (O(n log n) because n elements each do one binary search.)
- Is tails the actual LIS? (No, it is a length-tracking device. Reconstruction needs parent pointers.)
- How do you handle non-decreasing instead of strictly increasing? (Use upper bound instead of lower bound.)
- Can you do it in O(n)? (No, the LIS problem has an information-theoretic lower bound of O(n log n).)
- What if you need the actual subsequence? (Maintain parent pointers and backtrack.)
Visual Overview
Patience Sort: LIS in O(n log n) Input prices: [10, 9, 2, 5, 3, 7, 101, 18] tails = [] x=10 → append tails = [10] x=9 → replace @0 tails = [9] x=2 → replace @0 tails = [2] x=5 → append tails = [2, 5] x=3 → replace @1 tails = [2, 3] x=7 → append tails = [2, 3, 7] x=101 → append tails = [2, 3, 7, 101] x=18 → replace @3 tails = [2, 3, 7, 18] Answer: tails.size() = 4 (tails is always sorted → binary search valid) (tails ≠ actual LIS, just a length device)
Key Takeaway
The Longest Increasing Subsequence in O(n log n) time uses the patience sorting technique. You maintain a tails array where the entry at index k holds the smallest possible tail value of an increasing subsequence of length k + 1. For each number you binary-search the first tail that is >= the number; if there is none you append because it extends the longest run, otherwise you replace that tail because a smaller tail keeps future extension easier.
The tails array stays sorted at all times, which is what makes the binary search valid. After processing all numbers, the length of tails equals the LIS length. It is important to understand that tails is not the actual subsequence, only a length device; rebuilding the real subsequence needs parent pointers.
Using the lower bound gives a strictly increasing result, while the upper bound allows equal values for a non-decreasing variant. The naive O(n squared) DP is conceptually simpler but too slow for large inputs, so the binary search approach is the standard interview answer.
At the National Bank of India, the portfolio desk needed the longest stretch of rising closing prices to judge momentum, and those rising days did not have to be consecutive. The patience-sorting method delivered the answer on multi-year daily histories in O(n log n) time.
Remember one sentence: keep the smallest tails, binary-search each new element into them, and the tails array length is the LIS length.
---