Combine Two Sorted Lists Into One
Updated
Problem statement
You are given two lists of integers, left and right. Each list is already sorted from smallest to largest, and either one may be empty.
Return one list that holds every number from both lists, sorted from smallest to largest. Keep repeated numbers: if a value appears twice in left and once in right, it appears three times in the answer.
Try to use the fact that both lists are already sorted, instead of sorting everything again.
Function
combineSorted(left: int[], right: int[]) → int[]Examples
Example 1
left = [2,5,9]right = [1,5,6,12]return = [1,2,5,5,6,9,12]Take the smaller front number each time: 1 (right), 2 (left), 5 (left), 5 (right), 6 (right), 9 (left). Then the left list is used up, so 12 is copied. Both 5s are kept. The answer is [1,2,5,5,6,9,12].
Example 2
left = [10,20]right = [1,2,3]return = [1,2,3,10,20]Every number in right is smaller than 10, so all of right comes first and then all of left: [1,2,3,10,20].
Example 3
left = []right = [-3,0,0]return = [-3,0,0]left is empty, so the answer is just right: [-3,0,0].
Constraints
0 <= left.length, right.length <= 1000-104 <= left[i], right[j] <= 104leftandrightare each sorted in non-decreasing order (a number is never smaller than the one before it)
More DocuSign Onsite Interview questions
- Count Binary SubstringsONSITE INTERVIEW · Seen Sep 2026
- Two Positions That Add Up to a TargetPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Compress Consecutive Integer RangesONSITE INTERVIEW · Seen Aug 2026
- JSON Schema Object ValidatorONSITE INTERVIEW · Seen Aug 2026
- Most Transactions Kept Without Going NegativeONSITE INTERVIEW · Seen May 2025
- Three-Part Splits With a Light MiddleONSITE INTERVIEW · Seen May 2025
- Exact Palindrome CheckPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Paired Words That Share a SubstringONSITE INTERVIEW · Seen Apr 2022
- Reverse the Characters of a TextPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Reverse the Order of a Linked ListONSITE INTERVIEW · Seen Feb 2020
Similar questions at other companies
- Merge Sorted ArrayDP World · ONSITE INTERVIEW
- Merge Two Arrays Into Sorted OrderNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- Two SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Merge Sorted ArrayAmazon · ONSITE INTERVIEW
- Squares of a Sorted ArrayBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Assign CookiesExpedia · PHONE SCREEN · ONSITE INTERVIEWExpedia interview questions
- 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Sort Ones, Twos, and Threes In PlaceAgoda · PHONE SCREEN · ONSITE INTERVIEWAgoda interview questions
- Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
- Count Triplets With Sum at Most TargetGoogle · ONSITE INTERVIEWGoogle interview questions