Efficient Algorithm for comparing and iterate through two large arrays

Question

I have this problem:

I want to iterate and compare each item of array1 against each item of array2, both arrays have the same lenght. When the value of both items coincide I store the value j in my indexOfInterest[] array for later use.

This is the code that I use, works well but its extremely slow comparing large arrays (thousands of items), can anyone help me in implement an efficient algorithm for this task.

int i,j;

int counter = [array1 count];

int indexOfInterest[counter];


for (i = 0; i < counter; i++) {

    for (j = 0; j < counter; j++) {

        if ([[array1 objectAtIndex:i] intValue] == [[array2 objectAtIndex:j]intValue] ) {

            indexOfInterest[i] = j;
        }
    }
}

At least add a break; inside the if. No need to do any further checking once you find a match for the current value of i. — rmaddy
– rmaddy, Commented Oct 20, 2019 at 17:31
And between the two for loops, add a variable for the value of [[array1 objectAtIndex:i] intValue] and use that variable in the if. No need to call [[array1 objectAtIndex:i] intValue] more than once per iteration. — rmaddy
– rmaddy, Commented Oct 20, 2019 at 17:33
It would be easy to do in O(n) if the arrays are sorted instead of O(n^2), e.g. by using "pointers". But you can still get O(n) for unsorted arrays, e.g. by using a hash map with the value as key and the index as value. Put all items of one array into the hash map O(n), go through the other array and look if you find a match in the hash map O(n). — maraca
– maraca, Commented Oct 20, 2019 at 20:16

Raunak · Accepted Answer · 2019-10-21 04:02:35Z

2

You can store the indices of array1 in a hashmap (NSDictionary) where the keys are the elements/values and the value is the index of that element (or array of indices if elements are allowed to repeat). Call it map_of_array1.

Then iterate through array2 and find if map_of_array1[array2[[i]] is not null.

This way your time complexity will be O(n+m) instead of O(n*m).

answered Oct 21, 2019 at 4:02

Raunak

3,4341 gold badge24 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

MarioGT Over a year ago

Thanks Raunak, i will try that approach, I will be informing my results, thanks again !!

Collectives™ on Stack Overflow

Efficient Algorithm for comparing and iterate through two large arrays

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related