Data Pointers; an Intermediate problem solving tool

‘Data pointers’ not to be mistaken as memory pointers found in higher programming languages.

The term ‘Data Pointer’ is used loosely as they’re simply known as pointers, or as counters. The data pointer for the sake of this discussion is defined as an integer variable that holds the index value of an array for our reference.

(Img Source: stackexchange.com)

If you’ve ever used a for loop where you’ve set a variable to count through the character in a list of an array, you’re already familiar with data pointers.

Img Source: ‘The For loop’ Oregon State

What we mean to do with them in this article is outline cases where we can exercise a greater control over our pointers to traverse our data effectively, reduce our memory usage, and/or the time complexity of a process.

Once you’ve learned how to use pointers as a tool, you’ll begin to think of creative ways to implement them. If you’re looking for a job in the programming world, the clever use of pointers will help you ace your White Board interview questions.

(Img Source: How to: Work at Google — Example Coding/Engineering Interview)

Websites such as LeetCode have plenty of practice interview problems that cannot be completed by using the first fast method that come to mind. You’ll have to think of more efficient solutions, such as pointers. Our first example of an effective pointer is from the following problem:

‘Given a sorted integer array and a target value, write a function to find the target value.’

The simple solution that comes to mind would be to create a for loop, and check each value in our array to find the target value. In the worse case scenario, we would have to check every single value. Since this list is sorted however, we can instead search the list in less than half the time by using two pointers in a way we call Binary Search.

The logic we will follow is to determine, if the item we are looking for is greater, or less then the value we’re looking at. And adjust our pointers to limit the search area.

The list and target value we will use for this example will be as follows:

list = [-9, -8, -5, 0, 1, 7, 8]
target = 1

We will create two data pointers, one for each side of the list.

p_left = 0
p_right = len(list) #p_right = 7

Using these two pointers, we will calculate our search to begin between the both of them.

p_target = ( p_left+p_right ) // 2 #p_target = 3

And use it to look at the value at the middle of our list.

list[p_target] = 0

This value(0) is LESS than our target(1). So we will move the pointer p_left to our current index position. By doing so, we’ve determined that nothing to the LEFT of our value is going to be equal to our target, so we’ve effectively cut the number of items to search by almost half.

p_left = p_target

and then repeat the process from the begining:

p_left = 3
p_right = 7

Of the indexes available between 3 and 7, we’ll update our target pointer p_target to search the middle value. Then search our list at this index value.

p_target = ( p_left+p_right ) // 2 #p_target = 5
list[p_target] = 7

This value(7) is GREATER than our target(1). So now we’ll move the pointer p_right to our current index position. We’ve determined that nothing to the RIGHT of this value is going to equal our target. By doing so, we again cut the number of searches we need to perform by nearly half.

p_right = p_target

and repeat:

p_left = 3
p_right = 5
p_target = ( p_left+p_right ) // 2 #p_target = 4
list[p_target] = 1

This value(1) is EQUAL to our target(1). So we’ll break the loop and return the index value of p_target as our answer.

There are a few more parts that our code would need to correctly complete a search without running into errors, but they are beyond the scope of our discussion of pointers.

But worth note; In the event we didn’t find the item at this point, we would have ended our search in failure. But we’ve searched a total of three times in a list of seven items to determine the item isn’t in our list. It’s a valuable time savings.

Data pointers can be used to search through multiple lists as well. Let’s look a more difficult problem.

“Find the median of the two sorted arrays”

The first thing we need to do is clarify what is being asked in this problem as the wording is ambiguous. Taking the median of each individual list, and then calculating them together is incorrect. We need to combine both sorted arrays together first, and then find the median of the new array. For example

list1=[0]

list2=[-1,3]

The median is 0. As the order of both lists when combined is [-1,0,3].

The simple solution that comes to mind would be to concatenate both lists together into a new list and then sort them. The process of sorting a large list is pretty time efficient, but isn’t necessary. We only need to find the middle value(s). So why bother sorting the entirety of both lists? Why bother storing in memory a 3rd sorted list when the original lists already have all the data we need? Given that both of our lists are already sorted, we can approach this problem using data pointers.

The logic we will follow is to look at the values of each array at both of our pointers. By walking through the individual lists in order, we can determine the value at the median.

Disclaimer: There are certainly more complex ways to solve this problem more efficiently. Using pointers in this way will satisfy the time complexity requirements were you to submit an answer on LeetCode. As a far easier concept this is to understand, it showcases the strength of using pointers.

The lists we will use for this example will be as follows

list1 = [-9, -8, 7, 8]

list2 = [-5, 0, 1]

We will create a data pointer for each of our lists and set them both to begin at index 0.

p1 = 0
p2 = 0

We will also need a fixed variable to tell us the index value of where our Median value is

p_median = ( len(list1) + len(list2) -1 )//2 #p_median=3

The logic we will follow is to look at the values of each array at both of our pointers. By walking through the individual lists in order, we can determine the median.

Looking at both of our lists at our pointer locations:

list1[p1] = -9
list2[p2] = -5

We can determine the order of the digits from lowest to highest. -9, the item at list1[p1] is the lower number, we don’t need to store this value anywhere. Instead, we advance pointer p1 to look at the next value of its list.

p1 = 1
p2 = 0
p_median = 3

The sum of our pointers is less than the pointer of our median. So we’ll continue

list1[p1] = -8
list2[p2] = -5

As before, we compare values. The item at list1[p1] would be the lower value. So we’ll advance pointer p1.

p1 = 2
p2 = 0
p_median = 3

The sum of our pointers are less than our median. So we’ll continue

list1[p1] = 7
list2[p2] = -5

This time the value at list2[p2] is lower, so we’ll increment pointer p2

p1 = 2
p2 = 1
p_median = 3

At this point, the sum of our pointers has reached the value of our median designated by p_median.

We evaluate both of our lists once again

list1[p1] = 7
list2[p2] = 0

The lower value is 0, so we return it as the median of both lists and end our loop.

There are a few more parts that our code would need to correctly find the median number of two arrays without running into errors, but they are beyond the scope of pointers.

The point… is that by using pointers, we can make clever calculations, compare data, and store a minimal amount of information in order to reach our results. Both saving in time complexity and memory usage. While not a big savings with the small example lists we’ve used, they are valuable when dealing with large sets of data. I hope that by looking at these two examples you’ll think of pointers as another tool for problem solving. They’re not to be taken lightly. While the binary search problem is rated as an Easy task, finding the Median of two lists is rated as Hard.

Hopefully, you’ll never see such a complex question in an actual interview. But regardless of the question being asked. You have a new tool at your disposal.