Array

Problem Link on Leetcode: Check if Array Is Sorted and Rotated

Problem 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 B[i] == A[(i+x) % A.length] for every valid index i.

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

Constraints:

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

Implementation:

Apporach 1: O(n) sliding window approach with extra 2n space.

 
 public boolean check(int[] nums) {
        int n = nums.length;
        if(n ==1)
            return true;

        int[] extendedArray = new int[2 * n];

        // Copy the array elements twice
        for (int i = 0; i < n; i++) {
            extendedArray[i] = nums[i];
            extendedArray[i + n] = nums[i];
        }

        // Check for a contiguous sorted subarray of length n
        int count = 1;
        for (int i = 1; i < 2 * n; i++) {
            if (extendedArray[i] >= extendedArray[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            if (count == n) {
                return true;
            }
        }

        return false;
    }

Time and Space Complexity Analysis: Time complexity O(n). Space Complexity: O(2n)

GitHub Link for Approach 1

Apporach 2: Sliding window approach with no extra space.


public boolean check(int[] nums) {
        int n = nums.length;
        if(n ==1)
            return true;

        int count=1;

        for(int i=1; i < 2 * n; i++)
        {
            if(nums[i % n] < nums[(i-1) % n]){
                count =1;
            }
            else
                count++;

            if(count == n)
                return true;
        }
        return false;

    }

Time and Space Complexity Analysis: Time complexity O(n). Space Complexity: constant space or no extra space.

GitHub Link for Approach 2

Apporach 3: Finding rotation, no extra space.


public boolean check(int[] nums) {
        int i=1;
        while(i < nums.length && nums[i] >= nums[i-1]){
            i++;
        }
        //no rotation found and array is sorted
        if(i== nums.length)
            return true;

        //since rotated first element of array must be greater or equal to the last element of the array
        if(nums[0] < nums[nums.length -1]){
            return false;
        }

        //int rotationIndex =i;
        //i is the rotation index
        int j = i;

        while(j+1 < nums.length){
            if(nums[j+1] < nums[j]){
                return false;
            }
            j++;
        }

        return true;
    }

Time and Space Complexity Analysis: Time complexity O(n). Space Complexity: constant space or no extra space.

GitHub Link for Approach 3

Author: Mohammad J Iqbal

Mohammad J Iqbal

Follow Mohammad J Iqbal on LinkedIn

Join the LinkedIn group Algorithm Avengers to share thoughts and learn about Problem Solving, Data Structures, and Algorithms.