JavaScript program to calculate the inversion of size 3 in a given array

In this tutorial, we will learn to calculate the inversion of size 3 in a given array.

Problem Statement - We are given an array of length n containing distinct numeric entries. We need to find the total number of pairs of numbers of size 3 such that arr[i] > arr[j] > arr[k], where I

Here, we will first learn the brute force method, and then, we will optimize its time and space complexity.

Use brute force methods

In the brute force approach, we will use three nested for loops to find count reversals of size 3. The first loop iterates from 1 to n-2 elements, and the second loop iterates from the i-th element to the n-1-th element. If the previous element is greater than the next element, iterate over the array and find the element smaller than the middle element.

grammar

Users can use the brute force method following the syntax below to compute the inversion of size 3 in a given array.

for ( ) {
   for ( ) {
      if (array[m] > array[n]) {
         for (let o = n + 1; o < len; o++) {
            if (array[n] > array[o])
            cnt++;
         }
      }
   }
}

algorithm

• Step 1 - Iterate over the first n-2 elements using a for loop.

• Step 2 - Iterate over m 1 to len-1 elements using a nested for loop.

• Step 3 - In the nested for loop, check if array[m] is greater than array[n]. If so, iterate from the n 1th element to the last element.

• Step 4 - If the element at the othth index is smaller than the element at the nth index, we can say that we found a valid inversion pair of size 3 and increase that The value 'cnt' variable is decremented by 1.

• Step 5 - After all iterations of the for loop are completed, return the value of "cnt".

Example 1

In the example below, we implement a brute force method to find the total number of reversal pairs of size 3.

In the given array, the user can only observe 2 inversion pairs in the output. The first reversal pair is (10,5,4) and the second reversal pair is (20,5,4).

   
 Using the  Brute force approach  to Count Inversions of size three in a given array 
   
 
   

Time and space complexity

• Time complexity - Since we use three nested for loops, the time complexity is O(n^3).

• Space complexity - When we use constant space, the space complexity is O(1).

Use two nested for loops

In this method, we will use two nested loops. We will find the total number of smaller elements to the right of the current element, and the total number of larger elements to the left. After that, we multiply the two to get the total number of reversals for a specific number.

grammar

Users can use two nested loops to calculate reversals of size 3 in JavaScript by following the syntax below.

for ( ) {  
   // find a smaller element on the right  
   for ()
   if (array[m] < array[n])
   right++;
   
   // find bigger elements on the left
   for ()
   if (array[m] > array[n])
   left++;        
   cnt += right * left;
}

algorithm

• Step 1 - Iterate over n elements of the array using a for loop.

• Step 2 - Use a for loop to find all elements to the right of the current element that are smaller than the current element.

• Step 3 - Use the for loop again to find all elements to the left of the current element that are larger than the current element.

• Step 4 - Multiply the values ​​of the left and right variables and add them to the "cnt" variable.

Example 2

In the following example, we use two nested loops to find the total number of reversals of size 3, as shown in the above method. The user can observe that the output is the same as in the first method.

   
 Using the  two nested loops  to Count Inversions of size three in a given array 
   
 
   

Time and space complexity

• Time complexity - Since we use two nested loops, the time complexity of the above method is O(n^2).

• Space complexity - When we use constant space, the space complexity is O(1).

The user learned two methods to find count inversions of size 3 in a given array. In the first approach, we solved the problem using a brute force approach, and in the second approach, we further optimized the solution to reduce the time complexity.

The above is the detailed content of JavaScript program to calculate the inversion of size 3 in a given array. For more information, please follow other related articles on the PHP Chinese website!