Sorting Problem

2 Sum In A Sorted Array

Tech CornerLeave a comment

Problem

Given an array sorted in non-decreasing order and a target number, find the indices of the two values from the array that sum up to the given target number.

Example

{
"numbers": [1, 2, 3, 5, 10],
"target": 7
}

Output:

[1, 3]

Solution

function pair_sum_sorted_array(numbers, target) {
    let [start, end] = [0, numbers.length-1];
    let result = [];
    while(start < end){
        const sum = numbers[start] + numbers[end];
        if(sum < target){
            start++;
        }else if(sum > target){
            end--;
        }else{
            result = [start++, end--];
            break;
        }
    }
    return result.length ? result : [-1,-1];
}
Sorting Problem

K Most Frequent Words

Tech CornerLeave a comment

Problem

Given a number and a list of words, return the given number of most frequent words.

Example

{
"k": 4,
"words": ["car", "bus", "taxi", "car", "driver", "candy", "race", "car", "driver", "fare", "taxi"]
}

Output:

["car", "driver", "taxi", "bus"]

Solution

function mostFrequentWord(words, k) {

  const freq = new Map();
  let result = [];
  let n = words.length;

  for (let i = 0; i < n; i++) {

    let x = 0;
    if (freq.has(words[i]) == true) {
      x = freq.get(words[i]);
    }
    freq.set(words[i], x + 1);
  }

  let freqWordsSorted = new Map([...freq.entries()].sort((a, b) => b[1] - a[1]));

  for (let [key, value] of freqWordsSorted) {
    result.push(key);
    k--;
    if(!k) {
      break;
    }
  }

  console.log(result);
}

// given set of keys
let arr = ["car", "bus", "taxi", "car", "driver", "candy", "race", "car", "driver", "fare", "taxi"];
let n = 4;

mostFrequentWord(arr, n);

Time and Space Complexity

Time Complexity : O(n * log(n))
Space Complexity:  O(n)
Sorting Problem

3 Sum Smaller

Tech CornerLeave a comment

Problem

Given a list of numbers, count the number of triplets having a sum less than a given target.

Example One

{
"target": 4,
"numbers": [5, 0, -1, 3, 2]
}

Output:

2

{numbers[1], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[4]} are the triplets having sum less than 4.

Example Two

{
"target": 7,
"numbers": [2, 2, 2, 1]
}

Output:

4

{numbers[0], numbers[1], numbers[2]}, {numbers[0], numbers[1], numbers[3]}, {numbers[0], numbers[2], numbers[3]} and {numbers[1], numbers[2], numbers[3]} are the triplets having sum less than 7.

Solution

function count_triplets(target, numbers) {
    // Write your code here.
    // Initialize result
    let n = numbers.length;
    let result = 0;
        
        // Fix the first element as A[i]
        for (let i = 0; i < n-2; i++)
        {
           // Fix the second element as A[j]
           for (let j = i + 1; j < n-1; j++)
           {
               // Now look for the third number
               for (let k = j + 1; k < n; k++)
                   if (numbers[i] + numbers[j] + numbers[k] < target)
                       result++;
           }
        }
    return result;
}

Time and Space Complexity


Time: O(n * n).
Auxiliary space: O(1).
Total space: O(n)
Sorting Problem

4 Sum

Tech CornerLeave a comment

Problem

Given a list of numbers, find all the unique quadruples that sum up to a given target value.

Example

{
"arr": [0, 0, 1, 3, 2, -1],
"target": 3
}

Output:

[
[-1, 0, 1, 3],
[0, 0, 1, 2]
]

Solution

const removeDuplicates = (arr = []) => {
  const map = new Map();
  arr.forEach((x) => map.set(JSON.stringify(x), x));
  arr = [...map.values()];
  return arr;
};

function findFourElements(arr, target) {
    // Store sums of all pairs in a hash table
    arr.sort();
    let n = arr.length;
    let result = [];
    let mp = new Map();
    for (let i = 0; i < n - 1; i++)
        for (let j = i + 1; j < n; j++)
            mp.set(arr[i] + arr[j], [i, j]);

    // Traverse through all pairs and search
    // for target - (current pair sum).
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            let sum = arr[i] + arr[j];

            // If target - sum is present in hash table,
            if (mp.has(target - sum)) {

                // Making sure that all elements are
                // distinct array elements and an
                // element is not considered more than
                // once.
                let p = mp.get(target - sum);
                if (p[0] != i && p[0] != j
                    && p[1] != i && p[1] != j) {
                    let matchedResult = [
                        arr[i], 
                        arr[j],
                        arr[p[0]],
                        arr[p[1]]];
                    matchedResult.sort();
                    result.push(matchedResult);
                    break;
                }
            }
        }
    }
    let finalRes = removeDuplicates(result);
    console.log(finalRes);
}

// Problem
let arr = [0, 0, 1, 3, 2, -1];
let target = 3;

// Function call
findFourElements(arr, target);

Time and Space Complexity

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