Finding the coordinates of an element in a 2D array

#typescript #algorithms #tutorial

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.

Top comments (5)

Christian Engel • May 25 '22 • Edited

If you go for speed, working without callback functions should be faster!

function findCoordinate(in2dArray, searchValue){
    for(let x = 0; x < in2dArray[0].length; x++){
        for(let y = 0; y < in2dArray.length; y++){
            if(in2dArray[y][x] === searchValue){
                return {x, y};
            }
        }
    }
    return null;
}

Maybe you can throw this against your benchmark 😅

A note:
When working with computers and coordinates I never had the case that the horizontal position was labeled with y.

So in my code, I chose to use x for the horizontal axis.

Another difference to your function is that it returns null if no coordinate was found.

Christian Engel • May 25 '22

Here is another approach when you want to go for SPEED (maybe you need to look up coordinates very often?).

let fastMap = null;

function computeFastMap(in2DArray){
    fastMap = {};

    for(let x = 0; x < in2dArray[0].length; x++){
        for(let y = 0; y < in2dArray.length; y++){
            fastMap[in2dArray[y][x]] = {x, y};
        }
    }
}

function find2DCoordinate(value){
    if(!fastMap){
        throw new Error("Compute the fastMap, first!");
    }

    return fastMap[value] || null;
}

To make this work, you need to call computeFastMap(grid) at the beginning, once.
Afterwards, you can call find2DCoordinate() often but since all coordinates are pre-computed, the lookup in the
map is basically "for free" and will be VERY fast.

Karey Higuera • Jun 1 '22

Good call, I hadn't worked under the assumption of needing to do multiple lookups. It reminds me of a tweet I saw of using coordinate pairs in tuples for dictionary lookups in Python twitter.com/nedbat/status/15225434...

Mike Talbot ⭐ • May 25 '22

Nice! This might be slightly faster as it uses the internal indexOf function:

function find2dCoordinates(grid, number) {
    let output = null;
    grid.some((row, y)=> {
        const x = row.indexOf(number);
        if(x >= 0) {
           output = {x,y}
           return true;
        }
        return false;
    });
    return output;
}