Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1752.html

1752. Check if Array Is Sorted and Rotated

Level

Easy

Description

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2]

Output: true

Explanation: [1,2,3,4,5] is the original sorted array.

You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]

Output: false

Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]

Output: true

Explanation: [1,2,3] is the original sorted array.

You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Example 4:

Input: nums = [1,1,1]

Output: true

Explanation: [1,1,1] is the original sorted array. You can rotate any number of positions to make nums.

Example 5:

Input: nums = [2,1]

Output: true

Explanation: [1,2] is the original sorted array. You can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Solution

Loop over nums and find the minimum value. Then store the indices of the minimum value, and check whether one of the indices can be the start index of a sorted array. Skip the indices that are right after another index with the minimum value.

  • class Solution {
    public boolean check(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int num : nums)
            min = Math.min(min, num);
        List<Integer> minIndices = new ArrayList<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (nums[i] == min)
                minIndices.add(i);
        }
        int size = minIndices.size();
        for (int i = 0; i < size; i++) {
            if (i > 0 && minIndices.get(i) - minIndices.get(i - 1) == 1)
                continue;
            int minIndex = minIndices.get(i);
            int[] newNums = new int[length];
            for (int j = 0; j < length; j++)
                newNums[j] = nums[(minIndex + j) % length];
            boolean flag = true;
            for (int j = 1; j < length; j++) {
                if (newNums[j] < newNums[j - 1]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                return true;
        }
        return false;
    }
}

############

class Solution {
    public boolean check(int[] nums) {
        int cnt = 0;
        for (int i = 0, n = nums.length; i < n; ++i) {
            if (nums[i] > nums[(i + 1) % n]) {
                ++cnt;
            }
        }
        return cnt <= 1;
    }
}

  • class Solution:
    def check(self, nums: List[int]) -> bool:
        return sum(nums[i - 1] > v for i, v in enumerate(nums)) <= 1

############

# 1752. Check if Array Is Sorted and Rotated
# https://leetcode.com/problems/check-if-array-is-sorted-and-rotated

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        k = 0
        
        for i in range(n):
            if nums[i] > nums[(i+1)%n]:
                k += 1
            
            if k > 1: return False
                
        return True
            
            


  • class Solution {
public:
    bool check(vector<int>& nums) {
        int cnt = 0;
        for (int i = 0, n = nums.size(); i < n; ++i) {
            cnt += nums[i] > (nums[(i + 1) % n]);
        }
        return cnt <= 1;
    }
};

  • func check(nums []int) bool {
	cnt := 0
	for i, v := range nums {
		if v > nums[(i+1)%len(nums)] {
			cnt++
		}
	}
	return cnt <= 1
}

  • function check(nums: number[]): boolean {
    const n = nums.length;
    return (
        nums.reduce((r, v, i) => r + (v > nums[(i + 1) % n] ? 1 : 0), 0) <= 1
    );
}


  • impl Solution {
    pub fn check(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut count = 0;
        for i in 0..n {
            if nums[i] > nums[(i + 1) % n] {
                count += 1;
            }
        }
        count <= 1
    }
}

All Problems

All Solutions