Finding the coordinates of an element in a 2D array

While working on a coding challenge that @cassidoo sent out in her latest newsletter, I needed to find the coordinates of a particular number in a two-dimensional array of numbers. Here's a quick method for doing so!

Finding the coordinates using loops

Let's assume that we have a 3x3 array of numbers, and we want to find the location of the number '5'. I've arbitrarily assigned the axes x and y here.

const grid = [
---> y
|  [8,6,7],
|  [5,3,0],
v  [9,1,2]
x
]

While it may be a simple approach, looping through our array is a straightforward way to find our target element. Check out the function below:

const find2dCoordinates = <T>(
  grid: T[][],
  target: T
): {x: number, y: number} => {
  let coords = {x: -1, y: -1}
  grid.every((row, i) => row.every((item, j) => {
    if (item === target) {
      coords = {x: i, y: j}
      return false
    }
    return true
  }))
  return coords
}

We first define a set of coordinates: let coords = {x: -1, y: -1}; since we know we'll never have negative coordinates with an array, we can know that we ran into an error if the returned object has negative values.

Next, we're going to loop through each item in each row. Since we want the indices as well as the items themselves, we use the .every() function instead of for...of loops. We then check if each item is equal to our target. If you had an array of objects instead of numbers, you'd want to use some other equality check here.

Now, when we find a match, we store the coordinates in our coords variable. But we have a slight problem! Since we're not using for...of loops, we can't use a break to jump out of our loops early. 😕 Have no fear, because we planned for this 😎 By using .every() instead of .forEach(), we have an escape hatch.

The .every() method accepts a function as an argument and will run that function on each item in its array. This function should return true or false. If the every() function receives true back for every value in the array, it returns true. However if it finds an item that fails, it returns false.

In our case, we return true ourselves for each item that doesn't match our target so that every() will keep looking. Once we find our target, we return false, which causes every() to jump out early, and which bubbles up to the other .every() function as well. Success!

What about a flattened array?

Sometimes, we may have a two-dimensional array that has been flattened into one dimension. If you've ever worked with PNG images before, this is how their pixel information is stored. So our grid from earlier would be [8,6,7,5,3,0,9,1,2]. How can we find our coordinates now?

First, let's find the index of the number we're looking for. Then, if we know the original length of each row, we can calculate the coordinates it would have had!

export const find2dCoordinatesFlattened = <T>(
  grid: T[],
  target: T,
  rowLength: number
): {x: number, y: number} => {
  const position = grid.findIndex(item => item === target)
  return {
    x: Math.floor(position / rowLength),
    y: position % rowLength
  }
}

We first use the .findIndex() function to find the index of our target item in the one dimensional array. Then, we use two tricks to find the x and y coordinates. By dividing the index we found by the original row length and rounding down, we can find which row the item belongs on. Then, if we use the modulo operator on the index with the row length, we can see which column it belongs to.

Final thoughts

This was a fun little project, and I recommend you take a shot at the puzzle from the newsletter I mentioned in the intro!

Also, you might have asked yourself if flattening the array ourselves and using the second method might be faster than the first method of loops. Check out these benchmarks results comparing both methods.

First, I ran it on a very small 2x3 array.

Pretty comparable scores! But then I ran it against a 50x10 array.

Yikes 😬 Flattening it ourselves falls way behind. This makes sense, though, as we have to manipulate the entire array first to flatten it, while the loops can simply dive right in and jump out early when they find the result.