Sorting Problem

2 Sum In A Sorted Array

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

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

4 Sum

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)
Sorting Problem

3 Sum

Problem

Given an integer array arr of size n, find all magic triplets in it.

Magic triplet is a group of three numbers whose sum is zero.

Note that magic triplets may or may not be made of consecutive numbers in arr.

Example

{
"arr": [10, 3, -4, 1, -6, 9]
}

Output:

["10,-4,-6", "3,-4,1"]

Solution

function find_zero_sum(arr) {
    // Write your code here.
    var len = arr.length;
    var ans = [];
    arr.sort((a,b) => (a-b));
    
    for(var i=0; i < len-1; i++) {
        
        var s = new Set();
        
        for(var j = i+1; j < len; j++) {
            
            var x = -(arr[i] + arr[j]);
            
            if(s.has(x)) {
                var k = x + "," + arr[i] + "," + arr[j];
                ans.push(k);
            } else {
                s.add(arr[j]);
            }
        }
    }
    
    return ans;
}

Time and Space Complexity

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