You are given a stream of numbers and an integer bufferSize. Every number is at most bufferSize positions away from where it should appear in the correctly ordered stream.
Return the numbers in sorted order, meaning the final list should be in non-decreasing order.
If two numbers are equal, keep their relative order from the input stream to make the output deterministic.
Method Signature
List<Integer> serializeNumbers(List<Integer> stream, int bufferSize)
stream is the input stream of numbers.bufferSize is the maximum distance any number can be away from its correct position.- The method returns the serialized stream in non-decreasing order.
Constraints
1 ≤ stream.size() ≤ 100,0000 ≤ bufferSize < stream.size()-1,000,000,000 ≤ stream.get(i) ≤ 1,000,000,000- Each number is at most
bufferSize indices away from its position in the sorted order.
Examples
Example 1
serializeNumbers(stream = List.of(3, 1, 2, 5, 4, 6), bufferSize = 2)
Output: List.of(1, 2, 3, 4, 5, 6)
Explanation: Every number is close to its sorted position, so the stream can be serialized into sorted order.
Example 2
serializeNumbers(stream = List.of(10, 20, 15, 30, 25), bufferSize = 1)
Output: List.of(10, 15, 20, 25, 30)
Explanation: Each number is at most one position away from its correct place.
Example 3
serializeNumbers(stream = List.of(4, 4, 3, 5, 6), bufferSize = 2)
Output: List.of(3, 4, 4, 5, 6)
Explanation: The numbers are returned in non-decreasing order, and equal values keep their input order.