# Posts tagged as “two pointers”

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 < answer <= 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 a string `S`, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

```Input: "ab-cd"
Output: "dc-ba"
```

Example 2:

```Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
```

Example 3:

```Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
```

Note:

1. `S.length <= 100`
2. `33 <= S[i].ASCIIcode <= 122`
3. `S` doesn’t contain `\` or `"`

Idea:

Two pointers

Solution:

``````/**
* @param {string} S
* @return {string}
*/
var reverseOnlyLetters = function(S) {
let l = 0;
let r = S.length - 1;
let arr = S.split('');

while (l < r) {
if (!isAlpha(arr[l])) l++;
if (!isAlpha(arr[r])) r--;
if (isAlpha(arr[l]) && isAlpha(arr[r])) {
// swap
[arr[l], arr[r]] = [arr[r], arr[l]];
l++
r--;
}
}
return arr.join('');
};

var isAlpha = (c) => /[a-zA-Z]/.test(c);``````

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

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 + nums + nums;
// 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 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 = 
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;
};``````

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