Techie Delight
Coding made easy
Given three sorted arrays of variable length, efficiently compute the minimum range with at-least one element from each of the arrays.
For example,
Input: 3 sorted arrays of variable length
[ 3, 6, 8, 10, 15 ]
[ 1, 5, 12 ]
[ 4, 8, 15, 16 ]
Output: Minimum range is 3-5
Input: 3 sorted arrays of variable length
[ 2, 3, 4, 8, 10, 15 ]
[ 1, 5, 12 ]
[ 7, 8, 15, 16 ]
Output: Minimum range is 4-7
Naive solution is to compute the range for every possible triplet and return minimum of all values. The time complexity of this solution is O(n3) as we need three nested loops to consider every triplet.
C++
|
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
50
51
|
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
// Function to find the low range with at-least one element from
// each of the given arrays
auto findMinRange(auto &a, auto &b, auto &c)
{
// create a pair to store the result
pair<int, int> pair;
// stores the low difference
int diff = numeric_limits<int>::max();
// consider all triplets formed by (a[i], b[j], c[k])
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < b.size(); j++)
{
for (int k = 0; k < c.size(); k++)
{
// find minimum and maximum value in current triplet
int low = min(min(a[i], b[j]), c[k]);
int high = max(max(a[i], b[j]), c[k]);
// update the low difference if current difference is more
// and store the range in a pair
if (diff > high – low)
{
pair = make_pair(low, high);
diff = high – low;
}
}
}
}
return pair;
}
int main()
{
vector<int> a = { 3, 6, 8, 10, 15 };
vector<int> b = { 1, 5, 12 };
vector<int> c = { 4, 8, 15, 16 };
auto pair = findMinRange(a, b, c);
cout << “Minimum Range is [“ << pair.first << “, “ << pair.second << “]”;
return 0;
}
|
Output:
Minimum Range is [3, 5]
Java
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
// Pair class
class Pair
{
private final int first; // first field of a Pair
private final int second; // second field of a Pair
// Constructs a new Pair with specified values
private Pair(int first, int second)
{
this.first = first;
this.second = second;
}
// Factory method for creating a Typed Pair immutable instance
public static Pair of(int a, int b)
{
// calls private constructor
return new Pair(a, b);
}
@Override
public String toString() {
return “[“ + first + “, “ + second + ‘]’;
}
}
public class Main
{
// Function to find the minimum range with at-least one element from
// each of the given arrays
public static Pair findMinRange(int[] a, int[] b, int[] c)
{
// create a pair to store the result
Pair pair = null;
// stores the minimum difference
int diff = Integer.MAX_VALUE;
// consider all triplets formed by (a[i], b[j], c[k])
for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < b.length; j++)
{
for (int k = 0; k < c.length; k++)
{
// find minimum and maximum value in current triplet
int low = Math.min(Math.min(a[i], b[j]), c[k]);
int high = Math.max(Math.max(a[i], b[j]), c[k]);
// update the minimum difference if current difference is more
// and store the range in a pair
if (diff > high – low)
{
pair = Pair.of(low, high);
diff = high – low;
}
}
}
}
return pair;
}
public static void main(String[] args)
{
int[] a = { 3, 6, 8, 10, 15 };
int[] b = { 1, 5, 12 };
int[] c = { 4, 8, 15, 16 };
Pair pair = findMinRange(a, b, c);
System.out.print(“Minimum Range is “ + pair);
}
}
|
Output:
Minimum Range is [3, 5]
Python
|
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
|
# Function to find the minimum range with at-least one element from:
# each of the given lists
def findMinRange(a, b, c):
# create a pair to store the result
pair = None
# stores the minimum difference
diff = float(‘inf’)
# consider all triplets formed by (a[i], b[j], c[k])
for i in range(len(a)):
for j in range(len(b)):
for k in range(len(c)):
# find minimum and maximum value in current triplet
low = min(min(a[i], b[j]), c[k])
high = max(max(a[i], b[j]), c[k])
# update the minimum difference if current difference is more
# and store the range in a pair
if diff > high – low:
pair = (low, high)
diff = high – low
return pair
if __name__ == ‘__main__’:
a = [3, 6, 8, 10, 15]
b = [1, 5, 12]
c = [4, 8, 15, 16]
pair = findMinRange(a, b, c)
print(“Minimum Range is”, pair)
|
Output:
Minimum Range is (3, 5)
Download Run Code
Output:
Minimum Range is [3, 5]
Download Run Code
Output:
Minimum Range is [3, 5]
Download Run Code
Output:
Minimum Range is (3, 5)
We can easily reduce the time complexity to linear as we don’t need to consider every triplet. The idea is to take advantage of the fact that the arrays are already sorted. In solution below, we compute the range for some selected triplets and return the minimum.
The algorithm can be implemented as follows in C++, Java and Python:
C++
|
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
50
51
52
53
54
55
56
57
58
59
|
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
// Function to find the minimum range with at-least one element from
// each of the given arrays
auto findMinRange(auto &a, auto &b, auto &c)
{
// create a pair to store the result
pair<int, int> pair;
// stores the minimum difference
int diff = numeric_limits<int>::max();
// a triplet is formed by (a[i], b[j], c[k])
int i = 0, j = 0, k = 0;
// loop till the end of any array is reached
while (i < a.size() && j < b.size() && k < c.size())
{
// find minimum and maximum value in current triplet
int low = min(min(a[i], b[j]), c[k]);
int high = max(max(a[i], b[j]), c[k]);
// update the minimum difference if current difference is more
// and store the elements in a pair
if (diff > high – low)
{
pair = make_pair(low, high);
diff = high – low;
}
// advance index of the array with minimum value
if (a[i] == low) {
i++;
}
else if (b[j] == low) {
j++;
}
else {
k++;
}
}
return pair;
}
int main()
{
vector<int> a = { 2, 3, 4, 8, 10, 15 };
vector<int> b = { 1, 5, 12 };
vector<int> c = { 7, 8, 15, 16 };
auto pair = findMinRange(a, b, c);
cout << “Minimum Range is [“ << pair.first << “, “ << pair.second << “]”;
return 0;
}
|
Output:
Minimum Range is [4, 7]
Java
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
// Pair class
class Pair<U, V>
{
private final U first; // first field of a Pair
private final V second; // second field of a Pair
// Constructs a new Pair with specified values
private Pair(U first, V second) {
this.first = first;
this.second = second;
}
// Factory method for creating a Typed Pair immutable instance
public static <U, V> Pair <U, V> of(U a, V b) {
// calls private constructor
return new Pair<>(a, b);
}
@Override
public String toString() {
return “[“ + first + “, “ + second + ‘]’;
}
}
public class Main
{
// Function to find the minimum range with at-least one element from
// each of the given arrays
public static Pair<Integer, Integer> findMinRange(int[] a, int[] b, int[] c)
{
// create a pair to store the result
Pair<Integer, Integer> pair = null;
// stores the minimum difference
int diff = Integer.MAX_VALUE;
// a triplet is formed by (a[i], b[j], c[k])
int i = 0, j = 0, k = 0;
// loop till the end of any array is reached
while (i < a.length && j < b.length && k < c.length)
{
// find minimum and maximum value in current triplet
int low = Math.min(Math.min(a[i], b[j]), c[k]);
int high = Math.max(Math.max(a[i], b[j]), c[k]);
// update the minimum difference if current difference is more
// and store the elements in a pair
if (diff > high – low)
{
pair = Pair.of(low, high);
diff = high – low;
}
// advance index of the array with minimum value
if (a[i] == low) {
i++;
}
else if (b[j] == low) {
j++;
}
else {
k++;
}
}
return pair;
}
public static void main(String[] args)
{
int[] a = { 2, 3, 4, 8, 10, 15 };
int[] b = { 1, 5, 12 };
int[] c = { 7, 8, 15, 16 };
Pair<Integer, Integer> pair = findMinRange(a, b, c);
System.out.print(“Minimum Range is “ + pair);
}
}
|
Output:
Minimum Range is [4, 7]
Python
|
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
|
# Function to find the minimum range with at-least one element from:
# each of the given lists
def findMinRange(a, b, c):
# stores the minimum difference
diff = float(‘inf’)
# A triplet is formed by (a[i], b[j], c[k])
i = j = k = 0
# loop till the end of any list is reached
while i < len(a) and j < len(b) and k < len(c):
# find minimum and maximum value in current triplet
low = min(a[i], b[j], c[k])
high = max(a[i], b[j], c[k])
# update the minimum difference if current difference is more
# and store the elements in a pair
if diff > high – low:
pair = (low, high)
diff = high – low
# advance index of the list with minimum value
if a[i] == low:
i = i + 1
elif b[j] == low:
j = j + 1
else:
k = k + 1
return pair
if __name__ == ‘__main__’:
a = [2, 3, 4, 8, 10, 15]
b = [1, 5, 12]
c = [7, 8, 15, 16]
print(“Minimum Range is”, findMinRange(a, b, c))
|
Output:
Minimum Range is (4, 7)
Download Run Code
Output:
Minimum Range is [4, 7]
Download Run Code
Output:
Minimum Range is [4, 7]
Download Run Code
Output:
Minimum Range is (4, 7)
The time complexity of above solution is O(n) where n is the total number of elements in all three arrays.
source