Sort a K-Displaced Array
Updated
Problem statement
You are given an integer array nums and an integer k. The array is k-almost-sorted: every value is at most k positions away from where it ends up after sorting.
To handle repeated values, sort the occurrences by value and break ties by original index. If an occurrence starts at index i and has final index r in that order, the input promises |i-r| <= k. All supplied inputs satisfy this promise.
Return all input values in nondecreasing order. Keep every duplicate. Return a new array and leave nums unchanged. An empty input has k=0 and returns an empty array.
Explain how knowing this bound can save work compared with a plain sort.
Function
sortAlmostSorted(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,1,2,5,4]k = 2return = [1,2,3,4,5]Sorting gives [1,2,3,4,5]. The value 3 moves from index 0 to index 2, and every other value moves by one position. So the input fits k=2.
Example 2
nums = [2,1,1,3]k = 2return = [1,1,2,3]Keep both occurrences of 1, giving [1,1,2,3]. With equal values tied by original index, the two ones move left by one position each, while 2 moves right by two positions.
Example 3
nums = []k = 0return = []There are no input occurrences, so the sorted result is an empty array.
Constraints
0 <= nums.length <= 100.- Every element is an integer between
-1000000and1000000, inclusive. kis an integer with0 <= k <= nums.length.- Every occurrence stays within
kpositions of its sorted place, as the statement describes.
More Akuna Capital Phone Screen questions
- Match Orders by Price and Arrival TimeOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Biased Coin: Probability of Exactly h HeadsPHONE SCREEN · Seen Nov 2026
- Positive Nth Root with Gradient DescentPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Sep 2026
- Maximum Value in a Binary TreePHONE SCREEN · Seen Sep 2026
- Tiered Expiring Item StorePHONE SCREEN · Seen Aug 2026
- Statistics for the Latest K ValuesPHONE SCREEN · Seen Nov 2025
- Remove Duplicates While Preserving OrderPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2025
- Sliding Window MaximumPHONE SCREEN · Seen Oct 2025
- Evaluate a PolynomialPHONE SCREEN · Seen Oct 2025
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Meeting Rooms IIeBay · PHONE SCREENeBay interview questions
- Top K Frequent ElementsAmazon · OA · PHONE SCREEN
- Select the Top User MatchesDuolingo · PHONE SCREENDuolingo interview questions
- Meeting Rooms IIQuince · PHONE SCREENQuince interview questions
- Kth Largest Element in an ArrayLinkedIn · PHONE SCREENLinkedIn interview questions
- Meeting Rooms IISecuronix · PHONE SCREEN
- Merge Multiple Sorted StreamsNVIDIA · PHONE SCREENNVIDIA interview questions
- Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions
Interview reports that mention this question
Akuna Capital interview experiences
- Akuna Capital Quant Trader and QR Interviews: 5 Experiences
- Akuna Capital JQR CodePair Rounds: 8 Experiences (Part 6 of 6)
- Akuna Capital QR Probability Phones: 14 Experiences (Part 5 of 6)
- Akuna Capital QR Regression Rounds: 11 Experiences (Part 3 of 6)
- Akuna Capital QR Coding Interviews: 17 Experiences (Part 2 of 6)