Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 581 with 22 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 581 # by problem number
lcpy gen -s shortest_unsorted_continuous_subarray # by problem name
nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.
Return the shortest such subarray and output its length.
Input: nums = [2,6,4,8,10,9,15]
Output: 5
Input: nums = [1,2,3,4]
Output: 0
Input: nums = [1]
Output: 0
O(n) time complexity?
class Solution:
# Time: O(n)
# Space: O(1)
def find_unsorted_subarray(self, nums: list[int]) -> int:
n = len(nums)
end = -2
max_seen = nums[0]
for i in range(1, n):
if nums[i] < max_seen:
end = i
else:
max_seen = nums[i]
if end == -2:
return 0
start = 0
min_seen = nums[n - 1]
for i in range(n - 2, -1, -1):
if nums[i] > min_seen:
start = i
else:
min_seen = nums[i]
return end - start + 1
| Time | Space |
|---|---|
| O(n) | O(1) |