FilesExpand file tree

 master

/

CommonThreeSortedArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

49 lines (44 loc) · 1.4 KB

 master

/

CommonThreeSortedArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

49 lines (44 loc) · 1.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

package com.interview.array;

import java.util.ArrayList;

import java.util.List;

/**

* Date 01/01/2016

* @author Tushar Roy

*

* Given 3 sorted array find common elements in these 3 sorted array.

*

* Time complexity is O(m + n + k)

*

* http://www.geeksforgeeks.org/find-common-elements-three-sorted-arrays/

*/

public class CommonThreeSortedArray {

public List<Integer> commonElements(int input1[], int input2[], int input3[]) {

int i = 0;

int j = 0;

int k = 0;

List<Integer> result = new ArrayList<>();

while (i < input1.length && j < input2.length && k < input3.length) {

if (input1[i] == input2[j] && input2[j] == input3[k]) {

result.add(input1[i]);

i++;

j++;

k++;

} else if (input1[i] < input2[j]) {

i++;

} else if (input2[j] < input3[k]) {

j++;

} else {

k++;

}

}

return result;

}

public static void main(String args[]) {

int input1[] = {1, 5, 10, 20, 40, 80};

int input2[] = {6, 7, 20, 80, 100};

int input3[] = {3, 4, 15, 20, 30, 70, 80, 120};

CommonThreeSortedArray cts = new CommonThreeSortedArray();

List<Integer> result = cts.commonElements(input1, input2, input3);

result.forEach(i -> System.out.print(i + " "));

}

}