Press "Enter" to skip to content

Posts published in “Algorithms”

LeetCode 141. Linked List Cycle (javascript)

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

Can you solve it using O(1) (i.e. constant) memory?

Idea:

Use fast and slow pointers traversal, you they can meet each other then there is a circle

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head;
    let slow = head;
    
    while (fast) {
        if (!fast.next) return false;
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

LeetCode 209. Minimum Size Subarray Sum (javascript)

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Idea:

Two pointers + tracking min size

Solution:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let l = 0;
    let r = 0;
    let ans = Infinity;
    const n = nums.length;
    let total = 0;
    while (l < n) {
        while(r < n && total < target) {
            total += nums[r];
            r++;
        }
        if (total < target) break;
        ans = Math.min(ans, r - l);
        total -= nums[l];
        l++;
    }
    return ans === Infinity ? 0 : ans;
};

LeetCode 121. Best Time to Buy and Sell Stock (javascript)

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Idea:

Tracking two variables – minStock(min price of the stock) and maxGain(max profit)

Solution:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxGain = 0;
    let minStock = prices[0];
    
    for (let i = 0; i < prices.length; i++) {
        minStock = Math.min(minStock, prices[i]);
        maxGain = Math.max(maxGain, prices[i] - minStock);
    }
    return maxGain;
};

LeetCode 42. Trapping Rain Water (javascript)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

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

Idea:

Two pointers traversal

Solution:

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res = 0;
    const n = height.length;
    let l = 0;
    let r = n - 1;
    
    while (l < r) {
        let min = Math.min(height[l], height[r]);
        
        // if left side is smaller
        if (min === height[l]) {
            l++;
            while (l < r && height[l] < min) {
                res += min - height[l++];
            }
        } else { // right side is smaller
            r--;
            while (l < r && height[r] < min) {
                res += min - height[r--];
            }
        }
    }
    return res;
};

LeetCode 26. Remove Duplicates from Sorted Array (javascript)

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Constraints:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums is sorted in ascending order.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums === null || nums.length === 0) return 0;
    if(nums.length == 1) return 1;
    var count = 0;
    for(var i = 0; i < nums.length; i++) {
        if(nums[i] !== nums[i+1]){
            count++;
            nums[count] = nums[i+1];
        }
    }
    return count;
};

LeetCode 16. 3Sum Closest (javascript)

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;
} 

LeetCode 15. 3Sum (javascript)

Given an array nums of n integers, are there elements abc 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;
};

LeetCode 11. Container With Most Water (javascript)

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;
};

LeetCode 3. Longest Substring Without Repeating Characters (javascript)

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Solutions:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let n = s.length;
    let ans = 0;
    let visited = new Map();
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n ; j++) {
            if (visited.has(s[j])) {
                visited.clear();
                break;
            } else {
                ans = Math.max(ans, j - i + 1);
                visited.set(s[j], true);
            }
            
        }
        
    }
    return ans;
};

LeetCode 19. Remove Nth Node From End of List (Javascript)

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    if (head.next === null) 
        return null;
    
    let first = new ListNode();
    first.next = head;
    let second = first;
    // first point to n + 1
    first = first.next;
    while (n > 0) {
        first = first.next;
        n--;
    }
    // first already reach to the end null, means need to remove the first node
    if (first === null) {
        head = head.next;
    } else {
        // maintaining N nodes apart between first and second pointer
        while (first !== null) {
            first = first.next;
            second = second.next;
        }
        // Now second pointer to the node that need to be removed
        // remove that node now
        second.next = second.next.next;
    }

    return head;
    
};