15.6 find the closest entries in 3 sorted array exit condition

#1

Hi,
I have a question on solution for 15.6 find the closest entries in 3 sorted array problem.
I understand the basic idea of the solution but couldn’t figure out why the
while loop returns when an array comes to its end(the bolder line in the code block below)?

while (true) {
int min_value = iter_and_tail.cbegin()->first,
max_value = iter_and_tail.crbegin()->first;
min_distance_so_far = min(max_value - min_value, min_distance_so_far);
const auto next_min = next(iter_and_tail.cbegin()->second.iter),
next_end = iter_and_tail.cbegin()->second.tail;
// Return if some array has no remaining elements.
if (next_min == next_end) {
return min_distance_so_far;
}
iter_and_tail.emplace(*next_min, IterTail{next_min, next_end});
iter_and_tail.erase(iter_and_tail.cbegin());
}
}

If say sorted array B reaches to the end j = B.size( )-1 and A and C haven’t and A iterates at i and C iterates at k, will it be a chance the smallest entry happens at j = B.size()-1 and i’> i or k’ > k? Why the solution does not iterate all arrays to their ends?

Thanks!

0 Likes
#2

We had a proof of this before but most readers don’t like mathematical proof so we remove that. To prove this won’t happen, you simply just understand the fact that entry on i’ will be greater than or equal to entry on i if i’ > i. Similar thing applied on k’ and k as well. So if there is any solution using i’ or k’, the distance of this tuple won’t be smaller than the answer use (i, j, k) because the arrays are sorted.

1 Like