Lexicographically Smallest Array with K-Limited Right Moves
Updated
Problem statement
Reorder nums into a permutation of its elements. An element originally at index j may move to any earlier index, but if it moves to a later index i, it must satisfy i - j <= k.
Return the lexicographically smallest reachable array. Equal values are treated as distinct occurrences; when two equal values are both eligible for the same output position, use the smaller original index first.
Function
smallestReachableArray(nums: int[], k: int) → int[]Examples
Example 1
nums = [3,1,2]k = 1return = [1,3,2]Value 1 may move left to the first position. The original 3 must then be placed by index 1, because moving it two places right would exceed k.
Example 2
nums = [4,3,2,1]k = 3return = [1,2,3,4]Every original element may move far enough right for the fully sorted order to be reachable.
Example 3
nums = [2,1,1]k = 0return = [2,1,1]With k = 0, no element may move right. Any leftward move would force an earlier element right, so only the original order is reachable.
Constraints
0 <= nums.length <= 2000000 <= k <= nums.length-1000000000 <= nums[i] <= 1000000000
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- IPOTekion · PHONE SCREENTekion interview questions
- IPOInMobi · PHONE SCREENInMobi interview questions
- Minimum Refueling StopsBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
- Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions
- Schedule Unit-Time Jobs for the Most ProfitScale AI · PHONE SCREENScale AI interview questions
- Minimum Meeting RoomsSentry · PHONE SCREENSentry interview questions
- Minimum Refueling StopsUber · ONSITE INTERVIEWUber interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions