0

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;
        }
    }
}
MarioGT
  • 632
  • 6
  • 8
  • 2
    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 Oct 20 '19 at 17:31
  • 2
    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 Oct 20 '19 at 17:33
  • sorry I forgot that, anyway this code is very slow. – MarioGT Oct 20 '19 at 17:36
  • 3
    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 Oct 20 '19 at 20:16
  • Thanks rmaddy and maraca for your suggestions, – MarioGT Oct 21 '19 at 00:41

1 Answers1

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

Raunak
  • 3,314
  • 1
  • 22
  • 28