Skip to main content
Talentd

Minimum Rotations to Dial a Number II - Solution & Explanation

Medium12 min read
Practice this problem

Problem Statement

You are given an integer n and a string s of length n consisting of digits.

The dial contains the digits 0 through 9 in order and is circular, so 0 and 9 are adjacent. The pointer initially points to 0.

To dial each digit of s in order, rotate the pointer until it points to that digit. Each rotation moves the pointer to an adjacent digit, and you may rotate in either direction. Dialing a digit that the pointer already points to requires no rotations.

Before dialing, you may perform the following operation at most once:

  • Choose an index k such that 0 <= k < n and reverse the suffix s[k..n - 1].

Return the minimum total number of rotations needed to dial the string after optimally choosing whether to perform the operation and which suffix to reverse.

 

Example 1:

Input: n = 4, s = "1502"

Output: 9

Explanation:

Reverse the suffix starting at k = 1 to obtain "1205", then dial it.

Step From To Rotations
1 0 1 1
2 1 2 1
3 2 0 2
4 0 5 5

The total is 1 + 1 + 2 + 5 = 9, which is the minimum total number of rotations.

Example 2:

Input: n = 4, s = "2916"

Output: 12

Explanation:

Choose not to reverse a suffix and dial "2916".

Step From To Rotations
1 0 2 2
2 2 9 3
3 9 1 2
4 1 6 5

The total is 2 + 3 + 2 + 5 = 12, which is the minimum total number of rotations.

Example 3:

Input: n = 4, s = "4219"

Output: 6

Explanation:

Reverse the suffix starting at k = 0, which reverses the entire string, to obtain "9124", then dial it.

Step From To Rotations
1 0 9 1
2 9 1 2
3 1 2 1
4 2 4 2

The total is 1 + 2 + 1 + 2 = 6, which is the minimum total number of rotations.

 

Constraints:

  • 1 <= n == s.length <= 105ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹
  • s consists only of digits '0' to '9'

Approach Overview

Problem Overview: You start at a fixed position on a circular dial and must type a target string one character at a time. Each step rotates the dial in either direction, and you want the minimum total rotations needed to reach every character in order.

Approach 1: Step-by-Step Simulation (O(26n) time, O(1) space)

Track your current position on the dial. For each target character, rotate one notch at a time in the clockwise direction, counting steps until you land on the target. This is correct but wastes work, because a full clockwise sweep can cover distances that the counterclockwise direction covers faster. It is useful as a sanity check when you verify the faster formula on small inputs.

Approach 2: Greedy Shortest Arc (O(n) time, O(1) space)

Compute the circular distance between the current position and the next target character directly. With a dial of size 26, the raw difference is d = |target - current|, and the cost is min(d, 26 - d). Add that cost to the total, then move the current position to the target. Each character is handled with one subtraction and one comparison, so there is no hash map and no sorting. Choosing the shorter arc at every step is optimal because each character's cost depends only on where you are at that moment, so local choices never block a better global result. Use this approach whenever you need the answer in a single pass over the input.

Recommended for interviews: Interviewers expect the greedy shortest-arc solution. Mention the simulation first to show you understand the rotation model, then reduce it to the modular distance formula. The simulation shows understanding, but the O(n) greedy with the min(d, 26 - d) step shows you can spot the circular symmetry. Related practice: greedy, string, and simulation.

Solution

Thinking

Without reversing anything, the total cost is the distance from 0 to the first digit plus the sum of distances between adjacent digits.

Reversing a suffix changes the order inside the suffix, but every adjacent pair inside that suffix is still the same unordered pair, so the total internal suffix cost does not change.

Therefore, for each split point k, only two parts may change: which digit is dialed first, and the single edge connecting the prefix to the suffix. This gives an O(1) transition per split.

Define the total rotation cost between adjacent digits as T:

$ T=sum_{i=1}^{n-1} \operatorname{dist}(s[i-1], s[i]),

where \operatorname{dist}(a,b) is the shortest circular distance between digits a and b.

If we reverse the whole string, namely k=0, the answer becomes

\operatorname{dist}(0, s[n-1]) + T.

If k>0, the prefix s[0..k-1] stays in place, and all internal edges of the suffix keep the same total contribution. The only replaced edge is (s[k-1], s[k]), which becomes (s[k-1], s[n-1]). The starting digit is still s[0], so the total cost is

T - \operatorname{dist}(s[k-1], s[k]) + \operatorname{dist}(0, s[0]) + \operatorname{dist}(s[k-1], s[n-1]).

We enumerate all split points and take the minimum.

The time complexity is O(n), and the space complexity is O(1)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Step-by-Step SimulationO(26n)O(1)Verifying the model on small inputs
Greedy Shortest ArcO(n)O(1)General case and interviews

Video Solutions (6)

Leetcode 4071 | Minimum Rotations to Dial a Number II | Leetcode weekly contest 522

CodeWithMeGuys14:18588 views
Video 1 of 6

Frequently Asked Questions

Is Minimum Rotations to Dial a Number II easy or hard?
It is rated Medium with a 53.1% acceptance rate on FleetCode. The hard part is recognizing that the shorter arc in either direction is always the right local choice. Once you see the circular distance formula, the implementation is only a few lines.
How to solve Minimum Rotations to Dial a Number II in O(n)?
Start with the current position at the starting dial value and iterate through the target string. For each character, compute the absolute difference from the current position, take the smaller of that difference and 26 minus that difference, add it to a running total, and update the current position to the character. Return the total after the loop.
Minimum Rotations to Dial a Number II Python/Java solution?
In Python, loop over the string, convert each character to its index with ord(c) - ord('a'), compute d = abs(target - current), and add min(d, 26 - d) to the total. The Java version uses the same logic with charAt and Math.min. Both run in O(n) time and O(1) space.
What is the best approach for Minimum Rotations to Dial a Number II?
The best approach is a greedy single pass that adds the shorter circular arc between each consecutive pair of characters. For each character, compute the raw difference and take the minimum of that difference and the complement on the dial. This runs in O(n) time with O(1) extra space.
Is Minimum Rotations to Dial a Number II asked at Google/Amazon/Meta?
This problem is tagged General on FleetCode and does not have confirmed company tags in our data. It tests greedy reasoning and modular distance on a circle, which appear in interviews at many large tech companies. Check company-specific question lists on LeetCode for current reports.
What data structure is used in Minimum Rotations to Dial a Number II?
The solution uses only a few integer variables: one for the current position and one for the running total. No hash map, array, or stack is required. The string is read once, so the input itself is the only data structure involved.
What is the time complexity of Minimum Rotations to Dial a Number II?
The optimal solution runs in O(n) time, where n is the length of the target string, because each character is processed once with constant work. A step-by-step simulation that rotates notch by notch runs in O(26n), which is still linear in practice but does more work per character.

Ready to solve this problem?

Practice Minimum Rotations to Dial a Number II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Rotations to Dial a Number I