×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

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)


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.