array/count-pairs.js

"use strict";
/**
 * <b>LeetCode -  Array Problems</b>
 *
 * @example
 * import { countPairsOptimal } from '../../array';
 *
 * console.log(countPairsOptimal([-1,1,2,3,1]); // 2
 *
 * @author Gaurav Soni
 *
 * @module array
 *
 */
Object.defineProperty(exports, "__esModule", { value: true });
exports.countPairsBruteForce = exports.countPairsOptimal = void 0;
/**
 * @public
 *
 * The algo is based on the two pointer approach. For more details, check notes.
 *
 * <b>Time Complexity:</b> O(n) <br />
 *
 * @see {@link https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/|Count Pairs Whose Sum is Less than Target}
 *
 * @param {number[]} nums array of numbers.
 * @returns {number} Number of pairs whose sum less than target
 */
function countPairsOptimal(nums, target) {
    nums.sort((a, b) => a - b);
    let left = 0;
    let right = nums.length - 1;
    let res = 0;
    while (left < right) {
        if (nums[left] + nums[right] < target) {
            res += right - left;
            left++;
        }
        else {
            right--;
        }
    }
    return res;
}
exports.countPairsOptimal = countPairsOptimal;
function countPairsBruteForce(nums, target) {
    let res = 0;
    for (let left = 0; left < nums.length; left++) {
        for (let right = left + 1; right < nums.length; right++) {
            const sum = nums[left] + nums[right];
            if (sum < target) {
                res++;
            }
        }
    }
    return res;
}
exports.countPairsBruteForce = countPairsBruteForce;