FastPrepLexicographically Smallest Array with K-Limited Right Moves
Problems/Lexicographically Smallest Array with K-Limited Right Moves

Lexicographically Smallest Array with K-Limited Right Moves

Google logoGoogle● HardINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was a PhD intern interview. The firsthand Google internship report asks to make an integer array as sorted as possible, when each element can move right by at most k places and left without limit. We read "as sorted as possible" as the lexicographically smallest array you can reach. We added a fixed rule for duplicates.

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 <= 200000
  • 0 <= 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

Interview reports that mention this question

  • Google SWE Intern Onsite Questions: 16 Experiences (Part 2 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int[] smallestReachableArray(int[] nums, int k) {
        // Write your code here.
    }
}
Checking account…