Best way to find elements in array X and also in array Y

Question

What is the best way to find all equal elements in 2 sorted arrays?

how can I make it done by O(n) ?

it's solved here: https://stackoverflow.com/questions/19129382/better-way-to-find-matches-in-two-sorted-lists-than-using-for-loops — Gladiatorr, Jan 27 '20 at 21:39

score 2 · Answer 1 · answered Jan 27 '20 at 21:40

Since they are both sorted you could walk down them both until you hit the end of either. Assuming integers it would look something like this (Java example). You didn't really define how to handle duplicates so I'm assuming you'd want to see them if they were both arrays many times.

public class TwoArraysWalkIntoABar {
    public static void main(String[] args) {
        int[] a = { 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9 };
        int[] b = { 2, 4, 4, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
        int ax = 0, bx = 0;

        while (true) {
            if (ax >= a.length || bx >= b.length) {
                break;
            } else if (a[ax] == b[bx]) {
                System.out.println("Match: " + a[ax]);
                ax++;
                bx++;
            } else if (a[ax] < b[bx]) {
                ax++;
            } else if (a[ax] > b[bx]) {
                bx++;
            }
        }
    }
}

Results in:

Match: 2
Match: 4
Match: 4
Match: 4
Match: 6
Match: 8

Best way to find elements in array X and also in array Y

1 Answers1