Home » Data Structure » Array Data Structure

Shortest Un-ordered Subarray

C++ implementation to find the shortest un-ordered subarray.
Submitted by Vikneshwar GK, on February 05, 2022

Consider an array of size n. The task at hand is to find the length of a sub-array which has the least number of unordered elements, that is, neither increasing nor decreasing.

Example:

Input:
test1[] = {1, 8, 5, 0, 4, 6}

Output:
Shortest un-ordered subarray: 3

Explanation:
The output will be either 0 or 3 only 
since the problem asks for only the shortest.
If the array is either increasing or decreasing,
then the output is 0, else the output is 3.
For the given array, 
the elements are neither increasing or decreasing, 
therefore the output is 3.

Input:
test1[] = {1, 2, 3, 4, 5, 6}

Output:
Shortest un-ordered subarray: 0

Explanation:
Since the array is in increasing order, 
the output is 0

Solution 1:

On analyzing the problem statement, we can infer that the output will be either 0 or 3 only since the question asks for the least/shortest number of elements. Therefore, we can check whether the array is either increasing or decreasing. If so, then the output is 0, else the output is 3.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to check whether array is increasing
bool checkIncreasing(int array[], int length)
{
    for (int i = 0; i < length - 1; i++)
        if (array[i] >= array[i + 1])
            return false;
    return true;
}

// Function to check whether array is decreasing
bool checkDecreasing(int array[], int length)
{
    for (int i = 0; i < length - 1; i++)
        if (array[i] < array[i + 1])
            return false;
    return true;
}

// Function to check for shortest unordered
int unorderedShortest(int array[], int length)
{
    // if increase or decreasing,
    // return 0 else 3
    if (checkIncreasing(array, length) == true || checkDecreasing(array, length) == true)
        return 0;
    else
        return 3;
}

// Main function
int main()
{
    int array[100], length;
    
    cout << "Enter Number of elements: ";
    cin >> length;

    for (int i = 0; i < length; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    cout << "Shortest un-ordered subarray: " << unorderedShortest(array, length);

    return 0;
}

Output:

Enter Number of elements: 8
Enter element 1:1
Enter element 2:5
Enter element 3:4
Enter element 4:2
Enter element 5:3
Enter element 6:7
Enter element 7:10
Enter element 8:9
Shortest un-ordered subarray: 3

Time Complexity: O(n)