🔥 LeetCode 1752 - Check if Array Is Sorted and Rotated | May 23 POTD
📌 Problem:
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.
Duplicates are allowed.
Example 1: nums = [3,4,5,1,2] → true (rotated [1,2,3,4,5] by 2)
Example 2: nums = [2,1,3,4] → false (no rotation produces this)
Example 3: nums = [1,2,3] → true (rotated by 0 positions)
💡 Approach: Inversion Count
Key Insight: A sorted rotated array can have AT MOST one inversion point!
What is an inversion?
→ A position where nums[i] is less than nums[i-1]
(i.e. the sequence drops down)
In a valid sorted rotated array:
→ There can be at most 1 drop in the middle (the rotation point)
→ BUT we also check if nums[0] is less than nums[len-1]
because wrapping around also creates an inversion
→ If total inversions is more than 1, return false
Step by step:
→ Count inversions across the array
→ Also check if nums[0] is less than nums[len-1] as wrap inversion
→ If countInversion is greater than or equal to 2, return false
→ Else return true
⏱ Complexity:
- Time: O(n) — single pass through the array
- Space: O(1) — no extra space
✅ Difficulty: Easy
📅 May 23, 2025 — Problem of the Day
🔗 Perfect follow-up to LC 33 and LC 153 — Rotated Array series!
━━━━━━━━━━━━━━━━━━━━━━━
🔗 Problem Link:
https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/
#leetcode #java #inversioncount #dsa #leetcodedaily #potd
#leetcodeEasy #competitiveprogramming #may23potd #leetcode1752
#rotatedarray #sortedarray #oneliner #mustwatch
