[Two pointer] Exercising reducing time performance

I solved 167 Leetcode problem.

This is not hard. I think it is very good problem for practicing Time complexity reduction for interviews.

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

• Your solution must use only constant extra space.

Since the size of numbers is not large(ranging from 2 to 30,000), so a Brute-force algorithm is also possible.

I didn’t try this way but I think it would still meet the time constraints.

Idea: iterating from first to last index of list, and iterating to find the another value which is target - first value chosen from outer iteration in each iteration.

this brute-force algorithm takes
\(O(n^2)\)

---

From next, I implemented Binary search way.

Idea: iterate from index 0 to the last index of list. For each iteration, I search for value which is (target - number[i] ) (i is from iteration) using Binary search

this binary search algorithm takes \(O(n) \times O(\log n) = O(n \log n)\) .

This method was relatively slow when submitted on Leetcode, so I rethought that how to reduce the time complexity further.

---

Then I tried the two-pointer approach.

Idea: I declared two pointers: one pointing to the 0 index value, and the other pointing to the last. I looped through the list, checking sum of values two pointers point to.

• If sum is greater than the target, I moved the rear pointer one step backward.

• If sum is less than the target, I moved front pointer one step forward.

• If the sum is equals the target, I returned the result as [front position + 1, rear position +1].

This is my code base.

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        eidx: int = len(numbers) - 1
        res: List[int] = []
        for i in range(0, len(numbers)):
            sv: int = numbers[i]
            ev: int = numbers[eidx]
            sub_sum = sv+ev
            while (i < eidx) and (sub_sum >= target):    
                if sub_sum == target:
                    res = [i+1, eidx + 1]
                    break

                eidx = eidx - 1
                sub_sum = numbers[i] + numbers[eidx]
            
            if len(res) != 0:
                break
        
        return res

The point is how to setting finish condition of while-statement to move rear pointer

1. front index > rear index: already checked.
2. sum is less then target: rear pointer no longer need to move step backward(more less), so front pointer should move step forward.

This algorithm takes \(O(n)\) .

I got into the top 1% in terms of time performance among all submitted solutions.

When I solve this problem, I enjoyed the process of gradually decreasing the time complexity.

• algorithm
• two-pointer
• binary-search