Java Solution: Check If Array Is Sorted and Rotated

Introduction

Welcome to Day 2 of the 30-Day LeetCode Challenge! Today, we're diving into the "Check if Array Is Sorted and Rotated" problem. This problem asks us to determine if an array was originally sorted in non-decreasing order and then rotated some number of positions. We'll provide a Java solution to solve this problem efficiently.

Problem Statement

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

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 with 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.

Solution Approach

Here's a step-by-step explanation of how we can solve this problem efficiently using Java:

We'll iterate through the array, comparing each element with the one next to it. We're looking for situations where an element is greater than the one following it. This indicates a rotation.
Every time we find such a situation, we'll increase a counter called countRotation. This counter helps us keep track of how many times the array was rotated.
If at any point countRotation exceeds 1, we know the array has been rotated more than once, making it impossible to return to the original sorted order. In such a case, we'll return "false."
If the loop completes without countRotation exceeding 1, it means we can rotate the array back to its original sorted order, and we return "true."

Java Code Implementation

Here's the Java code that implements the solution approach:

class Solution {
    public boolean check(int[] nums) {
        int n = nums.length;
        int countRotation = 0;

        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                countRotation++;
            }
            if (countRotation > 1) {
                return false;
            }
        }

        return true;
    }
}

Time and Space Complexity

Time Complexity: The time complexity of this algorithm is O(n), where 'n' is the length of the array 'nums'. We go through the array once to check for rotations.
Space Complexity: The space complexity is O(1) (constant space) because we only use a few variables (n, countRotation, i) that does not depend on the size of the input array.

This solution is efficient and suitable for arrays of various sizes, making it a good choice for solving this problem.

Conclusion

Today, we've tackled the "Check if Array Is Sorted and Rotated" problem as part of the 30-Day LeetCode Challenge. By following the provided algorithm and Java code, you can efficiently determine whether an array was originally sorted in non-decreasing order and then rotated. Stay tuned for more coding challenges and solutions in the upcoming days of the challenge. Happy coding!

Day02 : Solving the "Check if Array Is Sorted and Rotated" Problem in Java

Table of contents