DEV Community

Karey Higuera
Karey Higuera

Posted on • Originally published at kbravh.dev

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
]
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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.
Benchmark of a 2x3 array

Pretty comparable scores! But then I ran it against a 50x10 array.
Benchmark of 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.

Discussion (6)

Collapse
lukeshiru profile image
Luke Shiru

The way I would personally do it:

const findCoordinates =
    <Item>(predicate: (item: Item) => boolean) =>
    (grid: ReadonlyArray<ReadonlyArray<Item>>) => {
        let y = -1;

        return {
            x: grid.findIndex(x => (y = x.findIndex(predicate)) !== -1),
            y,
        };
    };
Enter fullscreen mode Exit fullscreen mode

And because is curried, you can use it like this:

const findCoordinatesFor2 = findCoordinates((value: number) => value === 2);

findCoordinatesFor2([[1, 2], [3, 4]]); // { x: 0, y: 1 }
findCoordinatesFor2([[5, 6], [7, 8]]); // { x: -1, y: -1 }
Enter fullscreen mode Exit fullscreen mode

You might notice I'm returning -1, and that's mainly because in JS that's what I expect when an index is not found. This is also assuming the grid is the other way around:

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

But it should work for your y/x grid as well by just changing the names a little. Also because it uses a predicate function, you can search for more complex things like objects with a particular property, or stuff like that.

Cheers!

Collapse
paratron profile image
Christian Engel • Edited on

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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Collapse
paratron profile image
Christian Engel

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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Collapse
kbravh profile image
Karey Higuera Author

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...

Collapse
miketalbot profile image
Mike Talbot

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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
cassidoo profile image
Cassidy Williams

Awesome!