Practice: Target Sum in a Sorted Array

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 $O$($n^{2}$) because we have to iterate over the array two times using a nested loop and check every possible pair.

Array notation

Let’s try to write this solution in array notation and then convert it into pointer notation.

First, let’s discuss the setup. Inside the main function:

• We define a test array arr with the data from our example.
• We set the target to 17.
• We define an array solution, which will contain the solution and will be filled by our solve function. The solve solution will be our implementation of the brute-force algorithm. It receives the array, its size, the target, and the solution array.