JavaScript program for the shortest unordered subarray JavaScript program for the shortest unordered subarray

The problem statement requires finding the shortest unordered subarray in an array of integers. In other words, we need to determine the smallest subarray whose elements are not sorted in ascending or descending order. This problem can be solved in many ways, but in this article, we will discuss a simple yet effective solution using JavaScript.

So first we will start by defining what is an unordered subarray and then understand the problem statement in detail and then go on to explain the step by step solution using examples and code snippets. After reading this article, you will have a clear understanding of how to solve this problem in JavaScript. So let’s get started!

What is an unordered subarray?

An unordered subarray is a contiguous subarray of an array in which the elements are not arranged in ascending or descending order. In other words, the elements in the subarray are not arranged in increasing or decreasing order.

For example: [1, 2, 3, 5, 4, 6, 7] is an unordered subarray.

Problem Statement

Given an array of integers, we need to find the shortest unordered subarray. In other words, we need to find the smallest subarray whose elements are not sorted in ascending or descending order.

For example, let us consider the following array: const arr = [1, 2, 5, 4, 3, 6, 7]

In this case, the subarray [5, 4, 3] is the shortest unordered subarray.

Now let us understand the algorithm to solve this problem, and then we start implementing this algorithm using JavaScript.

Shortest unordered subarray algorithm

Input - array of n integers

Output - The length of the unordered shortest subarray

Step 1 - Initialization start = 0, end = n-1

STEP 2 - Traverse the array from left to right and find the first element that is larger than its right neighbor. Set its index to start.

STEP 3 - Traverse the array from right to left and find the first element that is smaller than its left neighbor. Set its index to end.

Step 4 - Find the smallest and largest element in the subarray from start to end.

STEP 5 - Iterate through the array from 0 to start-1 and find the index of the first element that is greater than the smallest element found in step 4. Set its index to the left.

STEP 6 - Iterate through the array from end 1 to n-1 and find the index of the first element that is less than the largest element found in step 4. Set its index to the right.

Step 7 - The length of the shortest unordered subarray is (right - left 1).

Example

In the following example, we first find the starting and ending indices of the unordered subarray by iterating the array from the beginning and the end respectively. We then find the smallest and largest elements in the subarray, and then traverse the array from the beginning and the end respectively to find the left and right indexes of the subarray.

Finally, we return the length of the shortest unordered subarray by subtracting the right index from the left index and adding 1.

function shortestUnorderedSubarray(arr) {
   let n = arr.length;
   let start = 0, end = n - 1;
   // find start index
   for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
         start = i;
         break;
      }
   }
   // find end index
   for (let i = n - 1; i > 0; i--) {
      if (arr[i] < arr[i - 1]) {
         end = i;
         break;
      }
   }
   // find min and max element in subarray
   let min = arr[start], max = arr[start];
   for (let i = start + 1; i <= end; i++) {
      if (arr[i] < min) {
         min = arr[i];
      }
      if (arr[i] > max) {
         max = arr[i];
      }
   }
   // find left index
   let left = 0;
   for (let i = 0; i <= start; i++) {
      if (arr[i] > min) {
         left = i;
         break;
      }
   }
   // find right index
   let right = n - 1;
   for (let i = n - 1; i >= end; i--) {
      if (arr[i] < max) {
         right = i;
         break;
      }
   }
   // return length of shortest un-ordered subarray
   return right - left + 1;
}
// Example usage:
const arr = [1, 2, 5, 4, 3, 6, 7]
console.log("Array:", JSON.stringify(arr))
const len = shortestUnorderedSubarray(arr)
console.log("The length shortest un-ordered subarray: ", len);
// Output: 3, as [5, 4, 3] is the shortest un-ordered subarray with length 3.

in conclusion

We discussed every nuance of how to perform the shortest unordered subarray problem using JavaScript. We hope that with this article, people can easily find and fix issues related to unordered subarrays in their code.

The above is the detailed content of JavaScript program for the shortest unordered subarray JavaScript program for the shortest unordered subarray. For more information, please follow other related articles on the PHP Chinese website!