581. Shortest Unsorted Continuous Subarray - Day 3/31 Leetcode May Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!

#leetcode #coding #programming

[georgiyefimov]

I think we can use binary search here. We keep iterating over prefix while it is sorted. When we find the first element which breaks sorting order we look up for a proper position for it in O(log n) in sorted prefix. Same for suffix. And we don't need any extra memory for it. So the complexity would be O(n)+2*O(log n)=O(n)

[vaibhavvatsa]

class Solution {
public:
int nums) {
vector<int>v2(nums);
int i=0, n=nums.size(), j=n-1;
sort(v2.begin(), v2.end());
while(i<n&&v2[i]==nums[i])
i++;
while(j>i&&v2[j]==nums[j])
j--;
return j-i+1;
}
}; // i did it this way without stack as i dont know stack xD

[Sandeep-zddq]

Great O(n) solution, I have done by sort and compare

[omyx]

Do a "How to use leetcode efficiantly" video