# Python O(N) with O(1) space complexity. No sorting

• Before, I explain anything this is my submitted solution is 96% and even though my code is not clean, I think it explains my thinking about this problem.

First, we have two pointer that finds first non-ascending, `l`, and first non-descending, `r` in array.
First `if` statement checks if `l` is greater than `r` which means the array is already sorted.
Now, second set of `while` loop is for any numbers outside of violating zone that should be included.
Such as following example that would not get caught by first pass:

`[1, 3, 7, 2, 5, 4, 6, 10]` : `left` would catch at value 7, `index: 2` and `right` would catch at value 4, `index: 5`

But, looking at the array the function should also include `3` and `6`. And this is why we do another round of while loop.
Instead incrementing and decrementing respective, `l` and `r`, we decrement and increment respective `l` and `r`.
Thinking about it as adjusting lower bound and upper bound is better.
This adjustment depends on two things: Minimum and maximum values of array `nums[l:r+1]`.
Now, we decrement `l` value until we find something that is lower than minimum.
Also, we increment `r` value until we find something that is greater than maximum.

After all that you just need to do `l + r - 1`.

I hope this helped everyone.

Analysis:
At worst case, `nums` is already sorted: `O(2n) = O(n)`
At worst case, `nums` is not sorted bound begins in the middle and two values are min and max of entire array: `O(2n) = O(n)`
Space complexity: Using only 5 variables and it is constant: `O(5) = O(1)`

``````class Solution(object):
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2: return 0

l, r = 0, len(nums) - 1

while l < len(nums) - 1 and nums[l] <= nums[l + 1]:
l += 1

while r > 0 and nums[r] >= nums[r -1]:
r -= 1

if l > r:
return 0

temp = nums[l:r+1]
tempMin = min(temp)
tempMax = max(temp)

while l > 0 and tempMin < nums[l-1]:
l -= 1

while r < len(nums) - 1 and tempMax > nums[r+1]:
r += 1

return r - l + 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.