Two Pointers on array

Question

Given an array of integers, implement the Two Pointers technique to find two distinct indices such that the sum of the elements at these indices equals a given target value. Your solution should return the indices of the two numbers in the form of an array. If no such indices exist, return an empty array.

Codemia · Accepted Answer

To solve the problem of finding two distinct indices in an array such that the sum of the elements at these indices equals a given target value, we can utilize the Two Pointers technique. This technique is particularly effective here because:

1. **Sorted Input Requirement**: The Two Pointers technique typically requires sorted data to efficiently converge towards a solution. In our problem, if the input array were sorted, we could use two pointers starting from either end of the array to find the target sum.

2. **Distinct Indices**: We need to ensure that the indices are distinct. The Two Pointers approach helps us navigate the array without needing to check every possible pair explicitly, thus maintaining distinctness naturally by updating the pointers.

3. **Efficiency**: This approach can potentially reduce the time complexity to O(n) if we consider the sorted implementation, as opposed to a naive O(n^2) approach where every pair is checked.

The approach can be broken down into the following steps:

1. **Initial Setup**: Create a list of tuples where each tuple contains an element from the array and its original index. This will help us track indices after sorting.

Example: For the array `[2, 7, 11, 15]`, this will yield `[(2, 0), (7, 1), (11, 2), (15, 3)]`.

2. **Sort the List**: Sort this list based on the element values.

3. **Two Pointers Initialization**: Initialize two pointers: one (`left`) at the start of the sorted array and another (`right`) at the end.

4. **Iterate to Find Target Sum**: While `left < right`:
   - Calculate the sum of the elements at the `left` and `right` pointers.
   - If the sum equals the target, return the original indices of these elements.
   - If the sum is less than the target, move the `left` pointer to the right (to increase the sum).
   - If the sum is greater than the target, move the `right` pointer to the left (to decrease the sum).

5. **Return**: If no such indices are found, return an empty array.

Here is the Python implementation based on the above approach:

```python
def two_sum(nums, target):
    indexed_nums = [(num, i) for i, num in enumerate(nums)]
    indexed_nums.sort()  # Sort by the value of the elements

left, right = 0, len(indexed_nums) - 1
    while left < right:
        current_sum = indexed_nums[left][0] + indexed_nums[right][0]
        if current_sum == target:
            return [indexed_nums[left][1], indexed_nums[right][1]]  # Return original indices
        elif current_sum < target:
            left += 1  # Increase the sum
        else:
            right -= 1  # Decrease the sum

return []  # If no pairs found
```

This implementation effectively utilizes the Two Pointers technique.

The time complexity of this solution is O(n log n) due to the sorting step. After sorting, the Two Pointers iteration runs in O(n) time, leading to an overall complexity dominated by the sorting step. The space complexity is O(n) because we store the original indices in a separate list.

Given the constraints of the problem (with n being the number of elements in the array), this approach is efficient and scales well.

Specific edge cases to consider include:
1. **Empty Array**: If the input array is empty, the function should return an empty array immediately.
   - Example: `two_sum([], 10)` should return `[]`.

2. **No Valid Pairs**: If there are no two numbers that sum up to the target, the function should return an empty array.
   - Example: `two_sum([1, 2, 3], 10)` should return `[]`.

3. **Negative Numbers**: The function should handle arrays with negative numbers, which can also sum to a positive target.
   - Example: `two_sum([-1, 1, 2], 1)` should return the indices of the elements `[-1]` and `[2]`.

4. **Duplicate Values**: If the array contains duplicate values, the function should still ensure that the returned indices are distinct.
   - Example: `two_sum([3, 3, 4, 5], 6)` should return indices of the first occurrence of `3` and `5`.

Two Pointers on array

Doordash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Doordash Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string