grid47 Exploring patterns and algorithms
Sep 9, 2024
6 min read
Solution to LeetCode 581: Shortest Unsorted Continuous Subarray Problem
Given an integer array, find the shortest continuous subarray such that, if you sort this subarray in non-decreasing order, the whole array will become sorted.
Problem
Approach
Steps
Complexity
Input: A list of integers, nums, representing the array to be considered.
Example: Input: nums = [3, 8, 6, 10, 12, 9, 14]
Constraints:
• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
Output: Return the length of the shortest subarray that needs to be sorted in order to make the whole array sorted.
Example: Output: 4
Constraints:
• The output must be a non-negative integer.
Goal: Find the shortest subarray that needs to be sorted to make the entire array sorted.
Steps:
• Identify the part of the array that is out of order.
• Check for the leftmost and rightmost positions where elements are not in order.
• Find the subarray between these positions and calculate its length.
• Return the length of the shortest subarray that needs to be sorted.
Goal: The input array is non-empty, and its length will not exceed 10^4.
Steps:
• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5
Assumptions:
• The input array is not empty.
• The array contains only integers.
• Input: Input: nums = [3, 8, 6, 10, 12, 9, 14]
• Explanation: The subarray [8, 6, 10, 12] is the only part that is out of order, so sorting it will sort the entire array.
• Input: Input: nums = [1, 2, 3, 4]
• Explanation: The array is already sorted, so the length of the subarray to be sorted is 0.
Approach: The key idea is to find the positions where the array stops being sorted and then calculate the length of the subarray that needs to be sorted.
Observations:
• The problem boils down to finding where the array is unsorted, both from the left and right sides.
• We need to find the smallest subarray that, when sorted, sorts the entire array.
• We can scan the array from both ends to identify where the unsorted subarray starts and ends.
Steps:
• Scan from the left to find the first out-of-order element.
• Scan from the right to find the last out-of-order element.
• Return the difference between the rightmost and leftmost unsorted positions plus one as the length of the subarray to sort.
Empty Inputs:
• The input array is always non-empty according to the constraints.
Large Inputs:
• The input size can be as large as 10^4, so the solution needs to be efficient in time and space.
Special Values:
• If the array is already sorted, return 0.
Constraints:
• The solution must run in O(n) time.
intfindUnsortedSubarray(vector<int>& nums) {
int mn =0, mx =0, n = nums.size();
vector<pair<int, int>> tmp(n);
for(int i =0; i < n; i++)
tmp[i] = make_pair(nums[i], i);
sort(tmp.begin(), tmp.end());
int start =-1, end =-1;
for(int i =0; i < n; i++) {
if(i != tmp[i].second)
if (start ==-1) start = i;
else end = i;
}
if(start ==-1) return0;
return end - (start -1);
}
1 : Function Declaration
intfindUnsortedSubarray(vector<int>& nums) {
Declares the function `findUnsortedSubarray`, which takes a vector of integers as input and returns the length of the shortest unsorted subarray.
2 : Variable Initialization
int mn =0, mx =0, n = nums.size();
Initializes variables `mn`, `mx`, and `n`. `mn` and `mx` will be used to track the minimum and maximum values within the subarray, while `n` holds the size of the input array.
3 : Temporary Array Initialization
vector<pair<int, int>> tmp(n);
Creates a temporary vector `tmp` of pairs, where each pair contains an element from the `nums` array and its corresponding index. This will help track the original order of elements while sorting.
4 : Array Population
for(int i =0; i < n; i++)
Starts a loop to populate the `tmp` vector with pairs. Each pair consists of an element from `nums` and its corresponding index.
5 : Pair Assignment
tmp[i] = make_pair(nums[i], i);
For each element in `nums`, assigns a pair containing the element and its index to `tmp[i]`.
6 : Array Sorting
sort(tmp.begin(), tmp.end());
Sorts the `tmp` vector based on the element values. This is essential to compare the original order with the sorted order and identify the subarray that is out of order.
7 : Variable Initialization for Indices
int start =-1, end =-1;
Initializes two variables `start` and `end` to -1. These will be used to track the first and last indices of the unsorted subarray.
8 : Subarray Identification Loop
for(int i =0; i < n; i++) {
Starts a loop to compare the indices of the original array (`nums`) with those in the sorted `tmp` array. If the indices don't match, it identifies the unsorted subarray.
9 : Index Comparison
if(i != tmp[i].second)
Compares the current index `i` with the index in the sorted `tmp` array. If they don't match, it indicates that this element is part of the unsorted subarray.
10 : Start Index Assignment
if (start ==-1) start = i;
If `start` is still -1 (not yet set), assigns the current index `i` as the `start` of the unsorted subarray.
11 : End Index Assignment
else end = i;
Once `start` is assigned, sets the current index `i` as the `end` of the unsorted subarray.
12 : Check for Already Sorted Array
if(start ==-1) return0;
Checks if the array is already sorted. If `start` is still -1, it means no unsorted subarray was found, so it returns 0.
13 : Return Subarray Length
return end - (start -1);
Calculates and returns the length of the unsorted subarray by subtracting `start` from `end`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We scan the array once to find the leftmost and rightmost out-of-order elements, resulting in O(n) time complexity.
Best Case: O(1)
Worst Case: O(1)
Description: The solution only requires a constant amount of extra space.
