Find a Specific Pair in Matrix using JavaScript - Coding

In this problem, we are given a 2-D matrix and we have to find the maximum value of ‘MAT[a][b]’ – ‘MAT[d]’ over all possible indices (0 <= ‘a’, ‘b’, ‘c’, ‘d’ < ‘N’) such that . ‘a’ > ‘c’ and ‘b’ > ‘d’. Below is an example to understand the problem statement clearly

Example:

Input 
   [
       [1 ,  2 , 3] ,
       [4 , 5 , 6], 
       [7,  8 , 9]
   ]  

Output:
8

Below are different approaches to Find a specific pair in Matrix using JavaScript:

Table of Content

Brute force Approach
Optimal Approach

Brute force Approach

We will initialize a variable answer with a value of negative infinity to store the maximum difference found in matrix. Now we iterate through each combination in matrix using nested loop making sure that ‘a’ > ‘c’ and ‘b’ > ‘d’. Update answer with the maximum difference found using Math.max(). Return answer as result.

Example: To demonstrate finding a specific pair in Matrix using brute force approach

JavaScript

function maxDifference(matrix) {
    const N = matrix.length;
    let answer = -Infinity;

    for (let a = 0; a < N; a++) {
        for (let b = 0; b < N; b++) {
            for (let c = 0; c < a; c++) {
                for (let d = 0; d < b; d++) {
                    answer = Math
                        .max(answer, matrix[a][b] - matrix[c][d]);
                }
            }
        }
    }

    return answer;
}


const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const result = maxDifference(matrix);
console.log("Maximum difference using Linear approach is  ", result);

Output

Maximum difference using Linear approach is   8

Time Complexity : O(N^4)

Space Complexity: O(1)

Optimal Approach

Define a function that takes a 2D array mat. Initialize answer to store the maximum difference and maxArr to store maximum values from each position to the bottom-right corner. Preprocess the last row and column of maxArr, then traverse the matrix from bottom to top and right to left, updating answer and maxArr. Print the result stored in answer.

Example: To demonstrate finding a specific pair in Matrix using optimal approach

JavaScript

function maxDifference(mat) {
    const N = mat.length;
    let answer = Number.MIN_SAFE_INTEGER;
    const maxArr = new Array(N)
        .fill(null).map(() => new Array(N));

    maxArr[N - 1][N - 1] = mat[N - 1][N - 1];

    let maxv = mat[N - 1][N - 1];
    for (let j = N - 2; j >= 0; j--) {
        if (mat[N - 1][j] > maxv)
            maxv = mat[N - 1][j];
        maxArr[N - 1][j] = maxv;
    }

    maxv = mat[N - 1][N - 1];
    for (let i = N - 2; i >= 0; i--) {
        if (mat[i][N - 1] > maxv)
            maxv = mat[i][N - 1];
        maxArr[i][N - 1] = maxv;
    }

    for (let i = N - 2; i >= 0; i--) {
        for (let j = N - 2; j >= 0; j--) {
            if (maxArr[i + 1][j + 1] - mat[i][j] > answer)
                answer = maxArr[i + 1][j + 1] - mat[i][j];

            maxArr[i][j] = Math
                .max(mat[i][j],
                    Math
                        .max(maxArr[i][j + 1],
                            maxArr[i + 1][j]));
        }
    }

    return answer;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
const result = maxDifference(matrix);
console.log("Maximum difference using optimal approach is  ", result);

Output

Maximum difference using optimal approach is   8

Time Complexity: O(N^2)

Space Complexity: O(N^2)

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
How to show Image in an Alert Box using JavaScript ?
How to select DOM Elements in JavaScript ?
How to Replace a JavaScript Alert Pop Up with a Fancy Alert Box ?
JavaScript Program to find Intersection of Unsorted Arrays
Javascript Program to Convert Integer to Roman Numerals

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14