LeetCode 2855. Minimum Right Shifts to Sort the Array Solution in Java, C++, Python & More | Explanation + Code

Description

You are given a 0-indexed array nums of length n containing distinct positive integers. Return the minimum number of right shifts required to sort nums and -1 if this is not possible.

A right shift is defined as shifting the element at index i to index (i + 1) % n, for all indices.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
After the first right shift, nums = [2,3,4,5,1].
After the second right shift, nums = [1,2,3,4,5].
Now nums is sorted; therefore the answer is 2.

Example 2:

Input: nums = [1,3,5]
Output: 0
Explanation: nums is already sorted therefore, the answer is 0.

Example 3:

Input: nums = [2,1,4]
Output: -1
Explanation: It's impossible to sort the array using right shifts.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums contains distinct integers.

Solutions

Solution 1: Direct Traversal

First, we use a pointer i to traverse the array nums from left to right, finding a continuous increasing sequence until i reaches the end of the array or nums[i - 1] > nums[i]. Next, we use another pointer k to traverse the array nums from i + 1, finding a continuous increasing sequence until k reaches the end of the array or nums[k - 1] > nums[k] and nums[k] > nums[0]. If k reaches the end of the array, it means the array is already increasing, so we return n - i; otherwise, we return -1.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.

PythonJavaC++GoTypeScript

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 k = i + 1 while k < n and nums[k - 1] < nums[k] < nums[0]: k += 1 return -1 if k < n else n - i(code-box)

class Solution { public int minimumRightShifts(List<Integer> nums) { int n = nums.size(); int i = 1; while (i < n && nums.get(i - 1) < nums.get(i)) { ++i; } int k = i + 1; while (k < n && nums.get(k - 1) < nums.get(k) && nums.get(k) < nums.get(0)) { ++k; } return k < n ? -1 : n - i; } }(code-box)

class Solution { public: int minimumRightShifts(vector<int>& nums) { int n = nums.size(); int i = 1; while (i < n && nums[i - 1] < nums[i]) { ++i; } int k = i + 1; while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) { ++k; } return k < n ? -1 : n - i; } };(code-box)

func minimumRightShifts(nums []int) int { n := len(nums) i := 1 for i < n && nums[i-1] < nums[i] { i++ } k := i + 1 for k < n && nums[k-1] < nums[k] && nums[k] < nums[0] { k++ } if k < n { return -1 } return n - i }(code-box)

function minimumRightShifts(nums: number[]): number { const n = nums.length; let i = 1; while (i < n && nums[i - 1] < nums[i]) { ++i; } let k = i + 1; while (k < n && nums[k - 1] < nums[k] && nums[k] < nums[0]) { ++k; } return k < n ? -1 : n - i; }(code-box)