3291. Find if Array Can Be Sorted
My accepted Python solution to LeetCode problem 3291, Find if Array Can Be Sorted, running in 15ms.
- Difficulty: Medium
- Python
- Runtime 15ms
- Memory 17.3MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 15ms, memory 17.3MB, accepted 2025-12-29.
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
# Group by popcount, within groups can sort freely
# Check if max of prev group <= min of current group
# Time: O(n), Space: O(1)
n = len(nums)
prev_max = 0
i = 0
while i < n:
curr_popcount = bin(nums[i]).count('1')
curr_max = nums[i]
curr_min = nums[i]
# Find all elements with same popcount
while i < n and bin(nums[i]).count('1') == curr_popcount:
curr_max = max(curr_max, nums[i])
curr_min = min(curr_min, nums[i])
i += 1
# Check if previous max <= current min
if prev_max > curr_min:
return False
prev_max = curr_max
return True