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 () 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
to17
. - We define an array
solution
, which will contain the solution and will be filled by oursolve
function. Thesolve
solution will be our implementation of the brute-force algorithm. It receives the array, its size, the target, and thesolution
array.
Get hands-on with 1200+ tech skills courses.