Sorting

Question 1

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Answer 1

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {    
     if (s.length !== t.length) {
         return false;
     }
    let sArr = s.split('').sort();
    let tArr = t.split('').sort();

    for (let i = 0; i < s.length; i++) {
        if (sArr[i] !== tArr[i]) {
            return false;
        }
    }

return true; };

Question 2

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
Example 2:

Input: [1,2,3,4]
Output: false

Answer 2

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    let sortedArr = nums.sort();

    for (let i = 1; i < sortedArr.length; i++) {
        if (sortedArr[i] === sortedArr[i - 1]) {
            return true;
        }
    }

return false; };

Question 3

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Answer 3

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumProduct = function(nums) {
    let sortedArr = nums.sort((a, b) => a - b);
    let len = nums.length;

return Math.max(
sortedArr[len - 1] * sortedArr[len - 2] * sortedArr[len -3],
sortedArr[0] * sortedArr[1] * sortedArr[len -1]
); };

Question 4

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Answer 4

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    const sortedArr = nums.sort((a, b) => b - a);
    return sortedArr[k - 1];
};

Question 5

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Answer 5

/**

• @param {number[][]} intervals
• @return {number[][]}
• /

var isOverlaps = function(a, b) {
    const start = Math.max(a[0], b[0]);
    const end = Math.min(a[1], b[1]);
    return end - start >= 0;
}
var merge = function(intervals) {
    intervals = intervals.sort((a, b) => a[0] - b [0]);
    const res = [];
    if (intervals.length <= 1) {
        return intervals;
    }
    let currentInterval = intervals[0];
    res.push(currentInterval);
    for (let i = 0; i < intervals.length; i++) {
        if (isOverlaps(currentInterval, intervals[i])) {
            currentInterval[1] = Math.max(intervals[i][1], currentInterval[1]);
        } else {
            currentInterval = intervals[i];
            res.push(currentInterval);
        }
    }

return res; };

Question 6

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: “210”
Example 2:

Input: [3,30,34,5,9]
Output: “9534330”

Answer 6

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    let initialStr = '';
    for (let i = 0; i < nums.length; i++) {
        initialStr += String(nums[i]);
    }
    initialStr = initialStr
        .split('')
        .map(str => Number(str))
        .sort((a, b) => b - a);
    return initialStr.join('');
};

Question 7

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Answer 7

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function(pairs) {
    pairs = pairs.sort(([a, b], [c, d]) => a - c);
    const N = pairs.length;
    const dp = new Array(N).fill(1);
     for (let j = 1; j < N; j++) {
            for (let i = 0; i < j; i++) {
                if (pairs[i][1] < pairs[j][0]) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
        }
        let ans = 0;
        for (const x of dp) {
            if (x > ans) {
                ans = x;
            }
        }
        return ans;
};