# Posts published in “Hash”

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

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

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('');
};``````

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

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