Sort an Array of Digits in Linear Time
Updated
Problem statement
You are given an array digits. Every value in it is a single digit from 0 to 9.
Sort the array in non-decreasing order and return it. You may change the array in place and return it.
The goal is O(n) time and O(1) extra space, where n is the length of the array. A general sorting routine takes O(n log n) time, so try to use the fact that there are only ten possible values.
Function
sortDigits(digits: int[]) → int[]Examples
Example 1
digits = [3,0,7,3,1,9,0]return = [0,0,1,3,3,7,9]The digits are two 0s, one 1, two 3s, one 7 and one 9. Written in that order they give [0, 0, 1, 3, 3, 7, 9].
Example 2
digits = [5,5,5]return = [5,5,5]All digits are the same, so the array is already sorted.
Example 3
digits = [9,8,6,2]return = [2,6,8,9]The digits are in decreasing order, so sorting reverses them.
Constraints
1 <= digits.length <= 10^40 <= digits[i] <= 9
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Group Transactions by HourAffirm · ONSITE INTERVIEWAffirm interview questions
- Merge Sorted ArrayDP World · ONSITE INTERVIEW
- Map and Accumulate Learning QueriesPalantir · ONSITE INTERVIEWPalantir interview questions
- Meeting RoomsGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Sort Products by Aisle With Frozen Items LastInstacart · ONSITE INTERVIEWInstacart interview questions
- Merge Two Arrays Into Sorted OrderNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
- Compress Consecutive Integer RangesDocuSign · ONSITE INTERVIEWDocuSign interview questions
- Filter Anagrams of a TargetMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Rank Transform an ArrayAgoda · ONSITE INTERVIEWAgoda interview questions
- Sort Documents Left to RightFigma · ONSITE INTERVIEWFigma interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)