Definition
- Stream.concat creates a lazily concatenated stream of elements from a followed by b.
- sorted() orders the combined stream by natural order or a supplied comparator.
- Does not exploit pre-sortedness; re-sorts in O((m+n) log(m+n)).
- Two-pointer merge is the optimal O(m+n) alternative for already-sorted inputs.
- distinct() can be added to remove duplicates from the merged result.
Priya at the National Bank of India has two sorted transaction lists from two branches. She drops one list on top of the other and sorts the combined pile. It works, but a merge that walks both lists in order would be faster.
Understanding the Concepts
What does this question ask?
The interviewer wants you to merge two sorted lists into one sorted result. This tests Stream.concat, sorted, and awareness of the efficiency trade-off.
How do you merge with concat and sorted?
package com.bank.service;
import java.util.*;
import java.util.stream.Stream;
public class MergeSortedLists {
public static void main(String[] args) {
List<Integer> branch1 = List.of(100, 300, 500, 700);
List<Integer> branch2 = List.of(200, 400, 600, 800);
List<Integer> merged = Stream.concat(
branch1.stream(), branch2.stream())
.sorted()
.toList();
System.out.println("Merged: " + merged);
}
}
Merged: [100, 200, 300, 400, 500, 600, 700, 800]
What is the efficiency trade-off?
| Approach | Time | Exploits pre-sort |
|---|---|---|
| concat + sorted | O((m+n) log(m+n)) | No |
| Two-pointer merge | O(m+n) | Yes |
// Optimal two-pointer merge
public static List<Integer> merge(
List<Integer> a, List<Integer> b) {
List<Integer> result = new ArrayList<>(a.size() + b.size());
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a.get(i) <= b.get(j)) {
result.add(a.get(i++));
} else {
result.add(b.get(j++));
}
}
while (i < a.size()) result.add(a.get(i++));
while (j < b.size()) result.add(b.get(j++));
return result;
}
The two-pointer merge is linear and leverages the fact that both inputs are already sorted.
How do you remove duplicates from the merged result?
List<Integer> branch1 = List.of(100, 300, 500);
List<Integer> branch2 = List.of(300, 500, 700);
List<Integer> mergedDistinct = Stream.concat(
branch1.stream(), branch2.stream())
.distinct()
.sorted()
.toList();
System.out.println("Merged distinct: " + mergedDistinct);
Merged distinct: [100, 300, 500, 700]
How do you merge with a custom comparator?
List<String> codes1 = List.of("CUR", "FD", "SAV");
List<String> codes2 = List.of("HDFC", "ICICI", "SBI");
List<String> merged = Stream.concat(
codes1.stream(), codes2.stream())
.sorted(Comparator.comparingInt(String::length)
.thenComparing(Comparator.naturalOrder()))
.toList();
System.out.println("Merged by length: " + merged);
How do you merge more than two lists?
List<List<Integer>> allBranches = List.of(
List.of(100, 400), List.of(200, 500), List.of(300, 600));
List<Integer> merged = allBranches.stream()
.flatMap(Collection::stream)
.sorted()
.toList();
System.out.println("All merged: " + merged);
All merged: [100, 200, 300, 400, 500, 600]
What are common mistakes?
Mistake: forgetting sorted() and assuming concat preserves sort order.
// WRONG: concat does not merge-sort; it just appends
List<Integer> wrong = Stream.concat(
List.of(100, 300).stream(),
List.of(200, 400).stream())
.toList();
System.out.println(wrong); // [100, 300, 200, 400] NOT sorted!
// CORRECT: add sorted()
List<Integer> correct = Stream.concat(
List.of(100, 300).stream(),
List.of(200, 400).stream())
.sorted()
.toList();
System.out.println(correct); // [100, 200, 300, 400]
Mistake: modifying the input lists.
// WRONG: addAll modifies the first list
branch1.addAll(branch2); // UnsupportedOperationException on immutable list!
// CORRECT: concat creates a new stream without modifying inputs
What are common interview follow-up questions?
- "What is the time complexity?" O((m+n) log(m+n)) for concat+sorted; O(m+n) for two-pointer.
- "How do you merge K sorted lists efficiently?" Use a priority queue (min-heap) of K entries.
- "Can you do this in parallel?" Yes, sorted() handles parallel internally, but two-pointer is inherently sequential.
Visual Overview
Branch 1: [100, 300, 500, 700]
Branch 2: [200, 400, 600, 800]
│
│ Stream.concat()
▼
[100, 300, 500, 700, 200, 400, 600, 800] (appended, NOT sorted)
│
│ .sorted()
▼
[100, 200, 300, 400, 500, 600, 700, 800] (sorted)
│
│ .toList()
▼
Merged sorted list
Key Takeaway
Merging two sorted lists uses Stream.concat to append one stream after the other and sorted to order the combined result. This is the simplest correct merge, though it re-sorts everything in O((m+n) log(m+n)) without exploiting the pre-sorted order.
For optimal O(m+n) performance, use a classic two-pointer merge that walks both lists in order. Add distinct() if the business wants a merged unique set. At the National Bank of India, Priya used this to combine sorted transaction lists from two branches into one unified report.
The concat approach is readable and correct for moderate data. Reserve the two-pointer merge for performance-critical paths or very large lists.
Remember one sentence: Stream.concat appends two streams and sorted re-orders the result, but it does not exploit pre-sortedness; for that, use a two-pointer merge.
---