Given two sorted arrays, finding their intersection involves returning the elements that appear in both of them. For example, the intersection of the arrays,

Since the arrays are sorted, we can simply iterate through both of them simultaneously using different loop counters. While doing so, we can do an element-wise comparison in both arrays, and if both elements are the same, the elements can be added to the intersection (if it hasn't already been added before). However, if the elements are not the same, the counter of one of the arrays is incremented (depending on which element was greater). The whole process is repeated until one of the arrays has been completely traversed. This process is depicted below with an example:

def sortedArrayIntersection(arr1, arr2):counter1 = 0counter2 = 0intersection = []while (1):if(counter1 >= len(arr1) or counter2 >= len(arr2)): # as soon as one of the arrays has been completely traversed, return the intersectionreturn intersectionif arr1[counter1] == arr2[counter2]: # element exists in both arraysif counter1 == 0 or arr1[counter1] != arr1[counter1 - 1]: # checking if the current element is equal to the previous element (to avoid duplicates)intersection.append(arr1[counter1])# increment both counterscounter1 += 1counter2 += 1elif arr1[counter1] < arr2[counter2]:counter1 += 1else:counter2 += 1arr1 = [2, 15]arr2 = [3, 3, 7, 15, 31]print(sortedArrayIntersection(arr1, arr2))

The `sortedArrayIntersection()`

function highlighted in the code above is explained below:

**Lines 6â€“8:**We use`counter1`

to iterate through`arr1`

. We use`counter2`

to iterate through`arr2`

. This is done until one of the counters exceeds the length of the array it is traversing, in which case we return`intersection`

.**Lines 10â€“12:**If`arr1[counter1] == arr2[counter2]`

, check whether this element is a duplicate (by comparing it with the previous element of one of the arrays). If it isn't a duplicate, add it to the`intersection`

and increment`counter1`

and`counter2`

.**Lines 18â€“22:**If`arr1[counter1] > arr2[counter2]`

, increment`counter2`

(the arrays are sorted, so the next value in`arr2`

will be greater than or equal to the current one). Otherwise, increment`counter1`

.

Since this solution only involves traversing through each of the

Copyright Â©2024 Educative, Inc. All rights reserved

TRENDING TOPICS