2855. Minimum Right Shifts to Sort the Array
Problem Description
In this problem, we are given an array nums
which contains distinct positive integers in a 0-indexed fashion, meaning the index of the array starts at 0. The goal is to determine the minimum number of right shifts needed to sort the array in ascending order. A right shift means taking an element at index i
and moving it to index (i + 1) % n
, where n
is the length of the array. If the array can be sorted with right shifts, we return the minimum number of shifts required; otherwise, we return -1
to indicate that sorting is not possible with only right shifts.
A right shift effectively moves the last element of the array to the front while shifting all other elements to the right by one position. This operation can be repeated many times to rotate the array. However, if the array is not a rotated version of a sorted array to begin with, it cannot be sorted by just right shifting.
Intuition
To solve this problem, we're going to leverage the fact that the array contains distinct positive integers. Given that the array can only be sorted by right shifts (or rotations), the original array must be a rotation of a sorted array. If it is not, then sorting it will be impossible.
The solution starts by stepping through the array while the integers remain in ascending order. The moment this order is violated, we know we've potentially found the point of rotation. From this 'breakpoint', the next step is to check if the array continues to increase up to the first element of the array (i.e., the element before the rotation point). If the order is again violated before reaching the end of the array, it means the array is not a rotation of a sorted array, so we cannot sort it with right shifts alone, and the solution should return -1
. If we successfully reach the end of the array without any order violations, it means we've confirmed that the array is a rotation of a sorted array.
Finally, to find the minimum number of right shifts, we need to return the distance from the beginning of the array to the 'breakpoint' or rotation point. However, since we're doing right shifts which effectively move the end element to the front, what we actually want is the number of elements from the rotation point to the end of the array. Therefore, we subtract the index of the rotation point from the total number of elements n
to get the minimum number of right shifts required.
Solution Approach
The implementation of the solution follows a straightforward algorithm to identify if the array is a single rotation of a sorted sequence and then calculates the minimum right shifts needed to sort the array.
The complete approach is as follows:
-
Initialize two pointers,
i
andk
.i
starts from 1 because we want to compare with the previous element, and it marks the index we're checking for the ascending order.k
is used to determine if the remaining part of the array is increasing and is smaller thannums[0]
. It starts fromi + 1
.
-
The first
while
loop finds the first occurrence wherenums[i-1] >= nums[i]
. This is the standard pattern to identify the break in ascending order. Ifi
reaches the end of the arrayn
without triggering the break condition, it means the array is already sorted, and no right shifts are needed; hence, return0
. -
The second
while
loop starts from the indexk
and checks whether every number from that index onwards is less thannums[0]
and the sequence is still increasing. Ifk
reachesn
without breaking the loop, the array is one rotation away from being sorted. -
The return value:
- If
k
has not reachedn
, it means that there's another break in the order, hence the sequence isn't just a single rotation of a sorted array, and sorting it by rotations is impossible. In this case, return-1
. - Otherwise, return
n - i
, which indicates the minimum number of right shifts required to bringnums[i]
to the 0th index, effectively sorting the array.
- If
Here is how the code encapsulates this logic:
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
n = len(nums)
i = 1
while i < n and nums[i - 1] < nums[i]:
i += 1
if i == n: # The array is already sorted.
return 0
k = i + 1
while k < n and nums[k - 1] < nums[k] < nums[0]:
k += 1
return -1 if k < n else n - i
This solution leverages simple array traversal and comparison without any complex data structures or advanced algorithms.
- No additional space complexity is introduced since we are only using a few integer variables (
i
,k
,n
). - The time complexity is at most O(2n) since both loops could potentially iterate over the whole array, but never more than once per element, simplifying to O(n).
One key point in understanding this algorithm is how the sorted array property is used to verify the possibility of sorting by rotations and then calculating the minimal rotation if possible.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use an example to illustrate the solution approach. Consider the following array:
nums = [3, 4, 5, 1, 2]
Now, let's walk through the approach step by step:
-
We initialize
i
to1
as we want to start comparing from the first element with the previous one (index 0). Variablek
is not used until later. -
The initial state is
i = 1
, and we comparenums[i - 1]
andnums[i]
. The pair we are comparing is therefore(3, 4)
which satisfiesnums[i - 1] < nums[i]
, so we incrementi
to2
. -
Continuing the loop,
i
now is2
, and we compare(4, 5)
. This also satisfies the ascending order soi
is incremented to3
. -
At
i = 3
, we compare(5, 1)
and find thatnums[i - 1] >= nums[i]
, which breaks the ascending order. According to our logic, this indicates where the array was potentially rotated. -
We set
k = i + 1
which is4
in this case and enter the secondwhile
loop to verify that the remaining part of the array is still in ascending order and each element is less thannums[0]
. -
Now,
k = 4
and we compare(1, 2)
. The conditionnums[k - 1] < nums[k] < nums[0]
is satisfied as(1 < 2 < 3)
. Sincek < n
, we continue and incrementk
to5
. -
As
k
equals ton
(end of array), which means the loop was never broken and confirms that the array is a rotation of a sorted array. -
Finally, we calculate the minimum number of right shifts required to sort the array which is
n - i
. In this case,n
is5
andi
is3
, so we need5 - 3 = 2
right shifts.
Therefore, the array [3, 4, 5, 1, 2]
requires a minimum of 2
right shifts to be sorted in ascending order.
Solution Implementation
1from typing import List
2
3class Solution:
4
5 def minimum_right_shifts(self, nums: List[int]) -> int:
6 # Determine the length of the input list `nums`
7 length = len(nums)
8
9 # Initialize the index `i` to start checking the ascending order from the beginning of the list
10 i = 1
11
12 # Find the first breaking point where ascending order is violated
13 while i < length and nums[i - 1] < nums[i]:
14 i += 1
15
16 # If there was no breaking point, the list is already in ascending order
17 if i == length:
18 return 0
19
20 # Initialize `k` for the second part of the task to identify if the right-shift requirement is met.
21 k = i + 1
22
23 # Check if the rest of the list after the breaking point is in ascending order and
24 # that it is less than the first element (to ensure a proper shifting sequence)
25 while k < length and nums[k - 1] < nums[k] < nums[0]:
26 k += 1
27
28 # If `k` did not reach end of the list, it means the right-shift to fix is impossible
29 return -1 if k < length else length - i # Return the number of shifts or -1 if not possible
30
31# Example of creating an instance of the solution and using the method
32solution_instance = Solution()
33print(solution_instance.minimum_right_shifts([3, 4, 5, 1, 2])) # Example output: 3 because it takes three right shifts for the list to become sorted
34
1class Solution {
2 public int minimumRightShifts(List<Integer> nums) {
3 // Get the size of the list
4 int listSize = nums.size();
5
6 // Initialize an index to track how many elements are
7 // in non-decreasing order starting from the beginning of the list
8 int nonDecreasingIndex = 1;
9
10 // Iterate through the list until elements are no longer in
11 // non-decreasing order, starting from the second element
12 while (nonDecreasingIndex < listSize && nums.get(nonDecreasingIndex - 1) < nums.get(nonDecreasingIndex)) {
13 ++nonDecreasingIndex;
14 }
15
16 // Once the non-decreasing sequence is broken, start another
17 // index to track the rest of the list if the elements are in non-decreasing order
18 // and also less than the first element of the list (to ensure proper rotation)
19 int checkIndex = nonDecreasingIndex + 1;
20 while (checkIndex < listSize && nums.get(checkIndex - 1) < nums.get(checkIndex) && nums.get(checkIndex) < nums.get(0)) {
21 ++checkIndex;
22 }
23
24 // If the checkIndex hasn't reached the end of the list, it means that the list can't be
25 // sorted by right rotations alone, so we return -1
26 // Otherwise, return the number of right shifts required, which is the size of the list minus
27 // the index of the initial non-decreasing sequence
28 return checkIndex < listSize ? -1 : listSize - nonDecreasingIndex;
29 }
30}
31
1class Solution {
2public:
3 int minimumRightShifts(vector<int>& nums) {
4 // Get the size of the vector nums.
5 int numsSize = nums.size();
6
7 // Initialize an index to keep track of the sequence.
8 int index = 1;
9
10 // Loop through the vector to find when the ascending sequence breaks.
11 while (index < numsSize && nums[index - 1] < nums[index]) {
12 ++index;
13 }
14
15 // If the entire vector is in ascending order, no right shift is needed.
16 if (index == numsSize) {
17 return 0;
18 }
19
20 // Initialize an index for the second part of the sequence.
21 int secondIndex = index + 1;
22
23 // Loop through the second part to validate ascending order
24 // till an element is less than the first element of the vector.
25 while (secondIndex < numsSize &&
26 nums[secondIndex - 1] < nums[secondIndex] &&
27 nums[secondIndex] < nums[0]) {
28 ++secondIndex;
29 }
30
31 // If secondIndex did not reach the end, sequence is not strictly ascending,
32 // return -1 indicating it's impossible to achieve the condition.
33 if (secondIndex < numsSize) {
34 return -1;
35 }
36
37 // Return the number of right shifts needed which is the length of the vector
38 // minus the length of the initial ascending sequence.
39 return numsSize - index;
40 }
41};
42
1/**
2 * Computes the minimum number of right shifts required to sort the array in non-decreasing order.
3 * If it's impossible to sort the array with only right shifts, the function returns -1.
4 * @param {number[]} nums - The input array of numbers.
5 * @return {number} The minimum number of shifts required, or -1 if impossible.
6 */
7function minimumRightShifts(nums: number[]): number {
8 // Get the length of the array.
9 const length = nums.length;
10
11 // Initialize the first index to 1.
12 let currentIndex = 1;
13
14 // Find the first element that is smaller than its previous element (breaks the increasing order).
15 while (currentIndex < length && nums[currentIndex - 1] < nums[currentIndex]) {
16 currentIndex++;
17 }
18
19 // If we have reached the end of the array, no right shifts are needed.
20 if (currentIndex === length) {
21 return 0;
22 }
23
24 // Define a variable to start checking for the correct position of first element after shifting.
25 let indexToCheck = currentIndex;
26
27 // Check that the remaining elements are still in increasing order and smaller than the first element.
28 while (indexToCheck < length && nums[indexToCheck - 1] < nums[indexToCheck] && nums[indexToCheck] < nums[0]) {
29 indexToCheck++;
30 }
31
32 // If indexToCheck has not reached the end, sorting is impossible.
33 return indexToCheck < length ? -1 : length - currentIndex;
34}
35
Time and Space Complexity
Time Complexity
The given Python function involves checking each element of the array exactly once in the two while
loops. The first loop continues until it encounters a non-ascending pair (nums[i - 1] >= nums[i]
), and the second loop continues until it reaches an element that does not satisfy the condition (nums[k - 1] < nums[k] < nums[0]
) or until it reaches the end of the array.
Both loops have a worst-case scenario where they traverse the entire list (n
being the length of the list).
- The first loop runs in
O(n)
time in the worst case. - The second loop also runs in
O(n)
time in the worst case.
As both loops run sequentially, the overall time complexity of the function is O(n) + O(n) = O(n)
.
Space Complexity
The function only uses a few integer variables (i
, k
, n
) and does not allocate any additional space that grows with the size of the input. Therefore, the space complexity of the function is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!