Skip to main content
Talentd

Orderly Queue - Solution & Explanation

HardMathStringSorting16 min readAsked at: Amazon, Bloomberg
Practice this problem

Problem Statement

You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string.

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

 

Example 1:

Input: s = "cba", k = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character 'c' to the end, obtaining the string "bac".
In the second move, we move the 1st character 'b' to the end, obtaining the final result "acb".

Example 2:

Input: s = "baaca", k = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character 'b' to the end, obtaining the string "aacab".
In the second move, we move the 3rd character 'c' to the end, obtaining the final result "aaabc".

 

Constraints:

  • 1 <= k <= s.length <= 1000
  • s consist of lowercase English letters.

Approach Overview

Problem Overview: You are given a string s and an integer k. In one move, you can choose one of the first k characters and move it to the end of the string. The goal is to produce the lexicographically smallest string possible after any number of moves.

Approach 1: Rotational Minimization (O(n^2) time, O(1) space)

When k == 1, you are restricted to moving only the first character to the end. That operation is equivalent to performing a rotation of the string. Because every move shifts the first character to the back, the only strings you can generate are the n cyclic rotations of the original string. The strategy is simple: generate each rotation s[i:] + s[:i] and track the lexicographically smallest one using standard string comparison. Each comparison takes up to O(n), and there are n rotations, giving O(n^2) total time. This approach relies purely on string manipulation and lexicographic ordering.

Approach 2: Direct Sorting (Applicable for k > 1) (O(n log n) time, O(n) space)

When k > 1, the problem changes completely. You can choose any of the first two characters and move it to the end, which effectively allows adjacent swaps after a sequence of operations. With enough moves, this gives you the freedom to reorder characters arbitrarily. Once arbitrary permutations are reachable, the smallest possible string is simply the sorted version of the characters. Convert the string to a character array, sort it using a standard sorting algorithm, and join the result. Sorting takes O(n log n) time and O(n) space depending on the implementation. This approach relies on concepts from sorting and reasoning about reachable permutations using simple math observations.

Recommended for interviews: Interviewers expect you to recognize the key observation that the value of k changes the reachable state space. Demonstrating the rotation-based reasoning for k == 1 shows you understand the constraint. Identifying that k > 1 enables arbitrary reordering and immediately switching to sorting shows strong problem reduction skills. The optimal interview solution combines both insights in a simple conditional.

Approach 1: Approach 1: Rotational Minimization

This approach is best when k = 1. Since you can only move the first character to the end, you are only able to produce rotations of the string. Therefore, to find the lexicographically smallest string, you can generate all rotations of the string and find the smallest one.

In this C implementation, rotateString is a helper function to get a rotated version of the string. The main function checks if k > 1 to sort the string. If k == 1, it rotates the string in all possible ways and keeps track of the lexicographically smallest string. The qsort function from the standard library sorts the string when k > 1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the string for k = 1 due to generating all rotations.
When k > 1, Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding copies of the string during rotations or sorting.

Try this approach in the editor →

Approach 2: Approach 2: Direct Sorting (Applicable for k > 1)

When k > 1, the problem allows moving any of the top k characters to the end, meaning we can potentially rearrange the entire string. Thus, this is equivalent to sorting the characters in the string to achieve the lexicographically smallest string. This can be directly achieved by sorting the string.

This C solution employs qsort to sort the characters of the string when k > 1. For this approach, when k==1, it is assumed to be handled by another approach since the logic for k=1 isn't applicable here.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding the sorted version of the string.

Try this approach in the editor →

Approach 3: Case-by-case Judgment

If k = 1, we can only move the first character of the string to the end of the string each time, resulting in |s| different states. We return the string with the smallest lexicographic order.

If k > 1, for a string like abc[xy]def, we can move a, b, and c to the end in order, resulting in [xy]defabc. Then we move y and x to the end, resulting in defabc[yx]. Finally, we move d, e, and f to the end, resulting in abc[yx]def. This way, we have swapped y and x.

Therefore, as long as k > 1, we can swap any two adjacent characters in the string, eventually obtaining a string sorted in ascending order.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Rotational Minimization

Time Complexity: O(n^2), where n is the length of the string for k = 1 due to generating all rotations.
When k > 1, Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding copies of the string during rotations or sorting.

Approach 2: Direct Sorting (Applicable for k > 1)

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for holding the sorted version of the string.

Case-by-case Judgment—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Rotational Minimization (k = 1)O(n^2)O(1)When only cyclic rotations are possible and k equals 1
Direct Sorting (k > 1)O(n log n)O(n)General case when k is greater than 1 and arbitrary permutations become reachable

Video Solution

Orderly Queue - (Amazon): Explanation ➕ Live Coding • codestorywithMIK • 16,668 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Orderly Queue easy or hard?
Orderly Queue is labeled Hard on LeetCode, but the implementation becomes simple once you identify the key observation about k. The difficulty comes from recognizing that k = 1 restricts operations to rotations, while k > 1 allows full reordering of characters.
Orderly Queue Python/Java solution
In Python or Java, the implementation is short. If k == 1, iterate through all rotations using substring operations and track the smallest string. If k > 1, convert the string to a character array, sort it using built-in sorting utilities, and return the joined result.
How to solve Orderly Queue in O(n)?
An O(n) theoretical solution exists for the k = 1 case using Booth's algorithm to find the lexicographically minimal rotation. However, most interview and competitive programming solutions simply check all rotations in O(n^2) because the constraints are small. For k > 1, sorting with O(n log n) is the standard approach.
What is the best approach for Orderly Queue?
The optimal approach depends on the value of k. If k = 1, only cyclic rotations of the string are possible, so you check all rotations and pick the lexicographically smallest in O(n^2) time. If k > 1, any permutation of the string becomes reachable, so sorting the characters directly in O(n log n) time produces the smallest possible string.
Is Orderly Queue asked at Google/Amazon/Meta?
Orderly Queue is a typical string manipulation and greedy reasoning problem similar to questions asked at companies like Amazon and Google. It tests understanding of lexicographic ordering, string rotations, and recognizing when constraints allow arbitrary permutations.
What data structure is used in Orderly Queue?
The solution primarily uses basic string operations and arrays of characters. For k = 1, you iterate through rotations and compare strings. For k > 1, the characters are placed in an array or list and sorted using a standard sorting algorithm.
What is the time complexity of Orderly Queue?
The complexity depends on the case. For k = 1, generating and comparing all rotations requires O(n^2) time and O(1) extra space. For k > 1, sorting the characters dominates the cost with O(n log n) time and O(n) space.

Ready to solve this problem?

Practice Orderly Queue with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer