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