Press "Enter" to skip to content

Posts published in “Hash”

LeetCode 167. Two Sum II – Input array is sorted (javascript)

By stone on April 12, 2021

Given an array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in increasing order.
  • -1000 <= target <= 1000
  • Only one valid answer exists.

Solution 1: (Two pointer)

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let l = 0;
    let r = numbers.length - 1;
    while (l < r) {
        let sum = numbers[l] + numbers[r];
        if (sum === target) break;
        else if (sum > target) r--;
        else l++;
    }
    // this question use 1-indexed
    return [l + 1, r + 1];
};

Solution 2: (Hash table)

var twoSum = function(numbers, target) {
    let map = new Map;
    for (var i = 0; i < numbers.length; i++) {
        var diff = target - numbers[i];
        if(map.has(diff)) {
            return [map.get(diff), i + 1];
        }
        map.set(numbers[i], i + 1);
    }
};

LeetCode 169. Majority Element (javascript)

By stone on April 9, 2021

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -231 <= nums[i] <= 231 - 1

Solution 1: (Hash Table)

  • Time Complexity : O(n)
  • Space Complexity : O(n)
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map();
    for (let num of nums) {
        map.set(num, (map.has(num) ? map.get(num) : 0)  + 1);
        if (map.get(num) > nums.length / 2) return num;
    }
    return -1;
};

Solution 2: (Sorting)

  • Time Complexity : O(n)
  • Space Complexity : O(1)
var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
};

Solution 3: (Divide and conquer)

  • Time Complexity : O(nlogn)
  • Space Complexity : O(logn)
var majorityElement = function(nums) {
    return majority(nums, 0, nums.length - 1);
};

function majority(nums, l, r) {
    if (l === r) return nums[l];
    const mid = l + Math.floor((r - l) / 2);
    const left = majority(nums, l , mid);
    const right = majority(nums, mid + 1, r);
    if (left === right) return left;
    return nums.slice(l, r + 1).filter(x => x === left).length >
           nums.slice(l, r + 1).filter(x => x === right).length
           ? left : right;
}

LeetCode 316. Remove Duplicate Letters (javascript)

By stone on March 28, 2021

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Idea:

Hash + Stack

Solution:

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    let chars = s.split('');
    // record the index of last occurrence for each character
    let lastIndex = new Map();
    for (let i = 0; i < chars.length; i++) {
        lastIndex.set(chars[i], i);
    }
    let stack = [];
    let used = new Map();
    for (let i = 0; i < chars.length; i++) {
        // if the current character has been used, skip it
        if (used.has(chars[i]) && used.get(chars[i])) continue;
        
        // if the current character is smaller than stack[stack.length - 1]
        // and the last index of stack[stack.length - 1] is larger than i, it means we can use it later,
        // so we pop it out and mark used as false
        while (stack.length !== 0 && chars[i] < stack[stack.length - 1] && lastIndex.get(stack[stack.length - 1]) > i)
            used.set(stack.pop(), false);
        
        stack.push(chars[i]);
        used.set(chars[i], true);
    }
    let ans = [];
    while (stack.length !== 0) ans.push(stack.pop());
    return ans.reverse().join('');
};

LeetCode 387. First Unique Character in a String

By stone on March 18, 2021

Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters.

Idea: Hashtable

Solution:

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    let map = new Map;
    
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            map.set(s[i], map.get(s[i]) + 1);
        } else {
            map.set(s[i], 1);
        }
    }
    
    for (let i = 0; i < s.length; i++) {
        if (map.get(s[i]) === 1) return i;
    }
    return -1;
};

LeetCode 1. Two Sum

By stone on March 18, 2021

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Idea:

Hashtable

Solution:

Hashtable / Javascript

Time complexity: O(n)

Space complexity: O(n)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        let diff = target - nums[i];
        if (map.has(diff)) {
            return [i, map.get(diff)];
        } else {
            map.set(nums[i],i);
        }
    }
};