# What Is The Fastest Way To See If The Values From A 2 Dimensional Array Are Present In 3 Other Two Dimensional Arrays

## 18 June 2022 - 1 answer

I have 4 integer two dimensional arrays of the form:

`{{1,2,3},{1,2,3},{1,2,3}}`

The first 3(A,B,C) are of size/shape [1000][3] and the 4th(D) [57100][3].

The combination of integers in the 3 elements sub-arrays in A,B,C are all unique, while combinations of integers in the 3 elements sub-arrays in D are not.

What I have to do is to find in what array from A,B or C a sub-array from D is present and do something with it after, depending in which array I find it.

I tried using nested for loops with if statements and check each array one at a time (A->B->C) and break out when I find it but it takes to long.

Thank you

As suggested by my comments, let's assume your approach is a naive, look at one item at a time in a `for` loop to see if a match is found.

Instead of doing that, another approach is to store the arrays as a `std::set<std::tuple<int, int, int>>` and do a lookup on the sets. Doing this reduces the time complexity from linear to logarithmic. For example, a 1000 item set will have at most 10 tests to finally determine if the item exists instead of having to go through all 1000 items.

Here is a somewhat untested example. Note that the data in the arrays has not been populated (the assumption is that the data has been populated into the arrays):

``````#include <tuple>
#include <set>
#include <array>
#include <iostream>

using TupleSet = std::set<std::tuple<int, int, int>>;

int A[1000][3];
int B[1000][3];
int C[1000][3];
int D[57100][3];

void printTuple(const std::tuple<int,int,int>& ts)
{
std::cout << std::get<0>(ts) << "," <<
std::get<1>(ts) << "," <<
std::get<2>(ts) << "\n";
}

// Initialize the tuple set with the 3 column 2D array of items
void initializeTuple(int pArray[][3], int numItems, TupleSet& ts)
{
for (int i = 0; i < numItems; ++i)
ts.insert({pArray[i][0], pArray[i][1], pArray[i][2]});
}

int main()
{
// Assume that A, B, C, and D have been filled in with data
//...
static constexpr char *arrayName = "ABC";

// Declare an array of 3 tuple sets that represent A,B,C
std::array<TupleSet, 3> allTuples;

// This is for the "special" D Array
TupleSet tD;

//Store the data in the tuples
initializeTuple(A, 1000, allTuples[0]);
initializeTuple(B, 1000, allTuples[1]);
initializeTuple(C, 1000, allTuples[2]);
initializeTuple(D, 57100, tD);

// Now go through each tuple in D to see if it's
// in A, B, or C
for (auto& t : tD)
{
// print the tuple we're searching for
printTuple(t);

// Now see if it's in A, B, or C
for (int i = 0; i < 3; ++i)
{
auto iter = allTuples[i].find(t);
if ( iter != allTuples[i].end() )
{
std::cout << "Found a match in Array " <<
arrayName[i] << "\n";
break;
}
}
}
}
``````

Note how each 2D array is placed in a tuple set. Also, since a `std::set` does not store duplicates, the `D` array will have all of its duplicates removed when placed in the tuple set `tD`. Thus right there, the number of items that `D` represents will be minimized.

However, there are some issues you should be aware of:

1. The initial setup time of the tuples is part of this solution. However the setup time is done only once.

2. It may be even faster to use a `std::unordered_set`, but that would require you to write a hash function, and I leave that as an exercise to you.