# Grokking the Coding Interview's Two Pointers

Pair with target sum, Remove duplicates, Squaring a sorted array, Dutch national flag problem

### 1. Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Example:

```
- Input: []int{1, 2, 6, 8, 16, 26}, target=14
Output: []int{2, 3}
Explanation: 6 (index 2) + 8 (index 3) = 14
```

Approach:

```
- Have one pointer start at the beginning and one at the end of the array.
- At each step, see if the two pointers add up to the target sum and move
them toward each other accordingly.
```

Cost:

```
- O(n) time, O(n) space.
```

### 2. Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Example:

```
- Input: []int{1, 2, 6, 8, 16, 26}, target=14
Output: []int{2, 3}
Explanation: 6 (index 2) + 8 (index 3) = 14
```

Approach:

```
- Have one pointer iterate the array and one placing non-duplicate number.
```

Cost:

```
- O(n) time, O(1) space.
```

### 3. Given a sorted array, create a new array containing squares of all the number of the input array in the sorted order.

Assumption:

```
- The input can have negative numbers.
```

Example:

```
- Input: []int{-2, -1, 0, 1, 2}
Output: []int{0, 1, 1, 4, 4}
```

Approach:

```
- The difficult part is to generate the output array with squares in sorted order because we have negative numbers and their squares are positive.
- Have one pointer start at the beginning and one at the end and let them
move toward each other.
- At each step, whichever bigger will be added to the output array, from
right to left.
```

Cost:

```
- O(n) time, O(n) space.
```

### 4. Given an array containing 0s, 1s and 2s, sort the array in-place.

Example:

```
- Input: []int{1, 0, 2, 1, 0}
Output: []int{0, 0, 1, 1, 2}
```

Approach:

```
- Have one pointer start at the beginning and the other at the end
while iterating through the array.
- We will move all 0s before that start pointer and 2s after the end
pointer so that all 1s would be between in the end.
```

Cost:

```
- O(n) time, O(1) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #grokking-the-coding-interview, #algorithm