Problem

Count the number of inversions in a given array of numbers. A pair (nums[i], nums[j]) is said to form an inversion if nums[i] > nums[j] and i < j.

Example 1

{
"nums": [3, 6, 1, 7, 2]
}

Output:

5

Example 2

{
"nums": [5, 10, 15, 18]
}

Output:

0

Solution

function merge(left, right) {

    //Array for storing sorted elements.
    let newArray = [];

    //No. of inversions
    let ni = 0;
    let p = 0;
    let k = 0;

    //For counting inversions
    while (p < left.length && k < right.length) {
        if (left[p] > right[k]) {
            newArray.push(right[k]);
            ni = ni + left.length - p;
            k = k + 1;
        }
        else {
            newArray.push(left[p]);
            p = p + 1;
        }
    }

    //Copies remaining left array elements
    while (p < left.length) {
        newArray.push(left[p]);
        p = p + 1;
    }

    //Copies remaining right array elements
    while (k < right.length) {
        newArray.push(right[k]);
        k = k + 1;
    }
    return [ni, newArray];
}

function countingInversions(a) {
    if (a.length < 2) return [0, a];
    else {
        let mid, left, right, left_inv, right_inv, merged;
        let inversions = 0;

        //Finding middle index.
        mid = Math.floor(a.length / 2);

        //Divides array into left and right.
        left = a.slice(0, mid);
        right = a.slice(mid, a.length);

        //returns inversions and sorted array.
        left_inv = countingInversions(left);
        right_inv = countingInversions(right);

        inversions = inversions + left_inv[0] + right_inv[0];

        //returns inversions and merged array.
        merged = merge(left_inv[1], right_inv[1]);

        //Total number of inversions
        inversions = inversions + merged[0];

        return [inversions, merged[1]];
    }
}

function count_inversions(arr) {
    let result = countingInversions(arr);
    return result[0];
}

Time and Space Complexity

Time Complexity : O(nlogn)
Space Complexity:  O(n)

Problem

Given a target number and a list of numbers, find a triplet of numbers from the list such that sum of that triplet is the closest to the target. Return that sum.

Example 1

{
"target": 9,
"numbers": [2, 8, 3, 2]
}

Output:

7

Example 2

{
"target": 16,
"numbers": [11, -2, 17, -6, 9]
}

Output:

14

Solution

function find_closest_triplet_sum(target, numbers) {
    // Sort the array
    numbers.sort((a, b) => a - b);

    // To store the closest sum
    let closestSum = Number.MAX_VALUE;

    // Run three nested loops each loop for each element of triplet
    for (let i = 0; i < numbers.length; i++) {
        for (let j = i + 1; j < numbers.length; j++) {
            for (let k = j + 1; k < numbers.length; k++) {

                // Update the closestSum
                if (Math.abs(target - closestSum) >
                    Math.abs(target - (numbers[i] + numbers[j] + numbers[k])))
                    closestSum = (numbers[i] + numbers[j] + numbers[k]);
            }
        }
    }

    // Return the closest sum found
    return closestSum;
}

Time and Space Complexity

Time Complexity : O(N2)
Space Complexity: O(1)

Problem

Given a list of characters, sort it in the non-decreasing order based on ASCII values of characters.

Example

{
"arr": ["a", "s", "d", "f", "g", "*", "&", "!", "z", "y"]
}

Output:

["!", "&", "*", "a", "d", "f", "g", "s", "y", "z"]

Solution

function sort_array(arr) {
    let length = arr.length;
    let result = [];

    // Stores the frequency of each character of the string
    let freq = new Array(256).fill(0)

    // Count and store the frequency
    for (let i = 0; i < length; i++) {
        freq[arr[i].charCodeAt(0)]++;
    }

    // Store the result
    for (let i = 0; i < 256; i++) {
        for (let j = 0; j < freq[i]; j++) {
            result.push(String.fromCharCode(i));
        }
    }

    return result;
}

Time and Space Complexity

Time Complexity : O(256*N)
Space Complexity: O(256)

Problem

Given an array of numbers sorted in increasing order, generate another array containing the square of all the elements in the given array, sorted in increasing order.

Example 1

{
"numbers": [1, 2, 3, 4]
}

Output:

[1, 4, 9, 16]

Example 2

{
"numbers": [-9, -5, -2, 0, 3, 7]
}

Output:

[0, 4, 9, 25, 49, 81]

Solution

function generate_sorted_array_of_squares(numbers) {
    let result = [];
    // Left and right pointer
    let l = 0;
    let r = numbers.length - 1;
    // Position to add squared number to A
    let p = r;

    // Add the higher number to the array and then decrease the pointer
    while (l <= r) {
        if (numbers[l] ** 2 > numbers[r] ** 2) {
            result[p--] = numbers[l++] ** 2;
        } else {
            result[p--] = numbers[r--] ** 2;
        }
    }

    return result;
}

Time and Space Complexity

Time Complexity : O(n)
Space Complexity: O(n)