Posts published in “Algorithms”

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

Idea:

Sorting the array + two pointers traversal

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    if (nums === null || nums.length <= 2) return null;
    if (nums.length === 3) return nums[0] + nums[1] + nums[2];
    // sort array first
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let res = null;
    let closest = Infinity;
    // two pointers traverse
    for (let i = 0; i < n; i++) {
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k];
            let diff = sum - target;
            if (diff === 0) {
                return sum;
            } else if (diff > 0) {
                // too large, make it smaller by moving k to the left
                k--;
            } else {
                // get the postive diff
                diff = target - sum;
                // too small, make it larger by moving j to the right;
                j++;
            }
            // keep tracking the current closest and update the current sum
            if (diff < closest) {
                closest = diff;
                res = sum;
            }
        }
    }
    return res;
} 

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Idea:

• Sort nums + two pointers
• Enumerate nums[i]
• Use two pointers to find all possible sets of (i,  l,  r) such that
  • i < l < r
  • nums[i] + nums[l] + nums[r] === 0
• How to move pointers?
  • nums[i] + nums[l] + nums[r] > 0, too large, decrease r
  • nums[i] + nums[l] + nums[r] > 0, too small, increase l

Optimize:

• skip: if nums[i] > 0, then nums[i] + nums[l] + nums[r] never = 0 
• skip same number: nums[i] === nums[i – 1]

Solution:

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const n = nums.length;
    let res = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 2; i++) {
        // skip: if nums[i] > 0,
        // then nums[i] + nums[l] + nums[r] never = 0
        if (nums[i] > 0) break; 
        // skip same number
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let l = i + 1;
        let r = n - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] === 0) {
                res.push([nums[i], nums[l++], nums[r--]]);
                // skip same number
                while (l < r && nums[l] === nums[l - 1]) l++;
                while (l < r && nums[r] === nums[r + 1]) r--;
            } else if (nums[i] + nums[l] + nums[r] > 0) {
                r--;
            } else {          
                l++;
            }  
        }
    }
    return res;
};

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Solution:

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let len = height.length;
    let l = 0
    let r = len - 1;
    let maxA = 0;
    while (l < r) {
        let minH = Math.min(height[l], height[r]);
        maxA = Math.max(maxA, minH * (r - l));
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return maxA;
};