Coder's Cat

## LeetCode: Two Sum II - Input array is sorted

2020-03-16

Challenge Description: Two Sum II - Input array is sorted

Note the input array is already sorted. So we can iterate all the elements, for each element(suppose with a value of v1), we try to find another element with the value of target-v1. Binary search will suitable for this task.

The overall time complexity is $O(NlogN)$.

## Approach #2: two-slice

The idea of two slices is similar to binary search. In this approach, we use two index, index l is from left to right, index r is from right to left.

In each iteration, we compare the current sum of two elements with the target. There are tree cases:

• sum == target, then we need return current two indexes.
• sum > target, then we need to decrease index r .
• sum < target, then we need to increase index l.

The time complexity is $O(N)$.

Join my Email List for more helpful insights, It's Free!😋