Web Front-endJS TutorialJavaScript 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).
<html>
<body>
<h3 id="Using-the-i-Brute-force-approach-i-to-Count-Inversions-of-size-three-in-a-given-array"> Using the <i> Brute force approach </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let len = array.length;
let cnt = 0;
for (let m = 0; m < len - 2; m++) {
for (let n = m + 1; n < len - 1; n++) {
if (array[m] > array[n]) {
for (let o = n + 1; o < len; o++) {
if (array[n] > array[o])
cnt++;
}
}
}
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
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.
<html>
<body>
<h3 id="Using-the-i-two-nested-loops-i-to-Count-Inversions-of-size-three-in-a-given-array"> Using the <i> two nested loops </i> to Count Inversions of size three in a given array </h3>
<div id = "output"> </div>
<script>
let output = document.getElementById('output');
function InversionCount(array) {
let cnt = 0;
let len = array.length;
// Iterate through every element of the array
for (let m = 0; m < len - 1; m++) {
// count all element that are smaller than arr[m] and at the right to it
let right = 0;
for (let n = m - 1; n >= 0; n--)
if (array[m] < array[n])
right++;
// count all element that are greater than arr[m] and at the left to it
let left = 0;
for (let n = m + 1; n < len; n++)
if (array[m] > array[n])
left++;
// multiply left greater and right smaller elements
cnt += right * left;
}
return cnt;
}
let array = [10, 20, 5, 4, 50, 60, 30, 40];
output.innerHTML += "The count of inversion in the " + array + " is " + InversionCount(array)
</script>
</body>
</html>
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!
Replace String Characters in JavaScriptMar 11, 2025 am 12:07 AMDetailed explanation of JavaScript string replacement method and FAQ This article will explore two ways to replace string characters in JavaScript: internal JavaScript code and internal HTML for web pages. Replace string inside JavaScript code The most direct way is to use the replace() method: str = str.replace("find","replace"); This method replaces only the first match. To replace all matches, use a regular expression and add the global flag g: str = str.replace(/fi
8 Stunning jQuery Page Layout PluginsMar 06, 2025 am 12:48 AMLeverage jQuery for Effortless Web Page Layouts: 8 Essential Plugins jQuery simplifies web page layout significantly. This article highlights eight powerful jQuery plugins that streamline the process, particularly useful for manual website creation
Build Your Own AJAX Web ApplicationsMar 09, 2025 am 12:11 AMSo here you are, ready to learn all about this thing called AJAX. But, what exactly is it? The term AJAX refers to a loose grouping of technologies that are used to create dynamic, interactive web content. The term AJAX, originally coined by Jesse J
10 jQuery Fun and Games PluginsMar 08, 2025 am 12:42 AM10 fun jQuery game plugins to make your website more attractive and enhance user stickiness! While Flash is still the best software for developing casual web games, jQuery can also create surprising effects, and while not comparable to pure action Flash games, in some cases you can also have unexpected fun in your browser. jQuery tic toe game The "Hello world" of game programming now has a jQuery version. Source code jQuery Crazy Word Composition Game This is a fill-in-the-blank game, and it can produce some weird results due to not knowing the context of the word. Source code jQuery mine sweeping game
How do I create and publish my own JavaScript libraries?Mar 18, 2025 pm 03:12 PMArticle discusses creating, publishing, and maintaining JavaScript libraries, focusing on planning, development, testing, documentation, and promotion strategies.
Load Box Content Dynamically using AJAXMar 06, 2025 am 01:07 AMThis tutorial demonstrates creating dynamic page boxes loaded via AJAX, enabling instant refresh without full page reloads. It leverages jQuery and JavaScript. Think of it as a custom Facebook-style content box loader. Key Concepts: AJAX and jQuery
jQuery Parallax Tutorial - Animated Header BackgroundMar 08, 2025 am 12:39 AMThis tutorial demonstrates how to create a captivating parallax background effect using jQuery. We'll build a header banner with layered images that create a stunning visual depth. The updated plugin works with jQuery 1.6.4 and later. Download the
How to Write a Cookie-less Session Library for JavaScriptMar 06, 2025 am 01:18 AMThis JavaScript library leverages the window.name property to manage session data without relying on cookies. It offers a robust solution for storing and retrieving session variables across browsers. The library provides three core methods: Session
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),
ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment
Zend Studio 13.0.1
Powerful PHP integrated development environment
SublimeText3 Chinese version
Chinese version, very easy to use
Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.
