Practice: Target Sum in a Sorted Array
Practice working with pointers and arrays.
Introduction
We’ll present a technique called two-pointers in this lesson. We’ll be using pointer notation, which we can use to solve problems involving arrays efficiently.
Problem statement
Given an array sorted in increasing order and a target number, find a pair of elements so that their sum equals the target. Return the indices of these elements, where the first element has the index 0.
The input format guarantees that a solution exists. If there are multiple solutions, return any one of them.
There are no constraints on the size of the array. However, to have a concrete example during the implementation, we’ll use an array of size 6. In practice, it can be anything.
Example input and output
Input:
arr = {1,4,6,10,12,13}
target = 17
Output:
1 5
The pair with the sum equal to 17 is (4, 13). We return the indices, which are (1, 5).
Brute-force solution
We could write a brute-force approach and try every single pair of elements in the array. Such an approach has a complexity of ( ...