Partitioning Souvenirs

Given a list of integers, we want to know if there is a way to split it evenly in three parts, so that the sum of each part is the same than the other ones.

Problem given in week six of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

This 3-partition problem is not too different from the classic 2-partition one, for which I have described the well known dynamic programming solution in the previous post. As before, we build a table where the rows represents the sums we want to get and the columns the elements in the collection we are about to consider.
However, we have to change a bit the meaning of the value that we push in each cell. This time we check two of the three tentative subcollections, and we want to keep track of how many of them could have as sum the row index, given the elements of the input list available in that column.

Consider as example this input:

[3, 1, 1, 2, 2]

We are looking for three subcollections having all a sum of three. The table is having six columns and four rows, including a first dummy one. We initialize all its cells to zero, and we loop on all the "real" cells applying rules close to the ones we have seen for the 2-partition problem, with slight variations.
(a) If the column element matches the row index, I increase the value of the left-hand cell, up to reach 2.
(b) If there is not a match, but the column element added to the previous one matches it, I still increase the value of the left-hand cell, up to reach 2.
(c) Otherwise, I copy the value in the left-hand cell to the current one.
The result should be reflected by this table:

And the answer to the original question is yes only if the bottom-left value in the table is two.

Here is my python code to implement this algorithm.

def solution(values):
    total = sum(values)
    if len(values) < 3 or total % 3:  # 1
        return False
    third = total // 3
    table = [[0] * (len(values) + 1) for _ in range(third + 1)]  # 2

    for i in range(1, third + 1):
        for j in range(1, len(values) + 1):  # 3
            ii = i - values[j - 1]  # 4
            if values[j - 1] == i or (ii > 0 and table[ii][j - 1]):  # 5
                table[i][j] = 1 if table[i][j - 1] == 0 else 2
            else:
                table[i][j] = table[i][j - 1]  # 6

    return True if table[-1][-1] == 2 else False

1. If dividing the sum of values by three I get a remainder, or if there are less than three elements in the list, for sure there is no way of 3-partition my list.
2. Build the table as discussed above. Note the zero as default value, even in the dummy top row - it is not formally correct, but those values are not used anywhere.
3. Loop on all the "real" cells.
4. Precalculate the row for the (b) check described above.
5. The first part of the condition is the (a) check above. If it fails, we pass to the second part, using the row calculate in (4). If one of the two conditions is true, the value of the current cell is increased up to 2.
6. Vanilla case, moving to the right we keep the value already calculate for the previous cell.

It looks easy, once one see it, doesn't it?

Actually, a tad too easy, as Shuai Zhao pointed out - see below in the comments. The problem is that the (b) check, as described above, is too simple. Before using a value I have to ensure it has not already used on the same line. Things are getting complicated, better to explain them in another post.

I pushed my python code and a few test cases to GitHub. The latest version is the patched code, working also for the Shuai test. Get back in the history if you want to see the solution described here.

Go to the full post

2-partition problem

Having a list of integers, we want to know if we can split it evenly in two parts.

There is a well known, elegant and relatively fast dynamic programming solution to this problem.

Say that this is the list

[3, 1, 1, 2, 2, 1]

Being the sum of its elements ten, we'll have a positive answer to the problem if we could find a subcollection with a sum of five.

To check it, we build a table having rows from zero to the sum of the subcollection we are looking for - five in this case. Actually, the zeroth row is pretty useless here, I keep it just because it makes indices less confusing in the code. The columns represents the partial sum of elements in the list we have in input, column zero is for the empty collection, one contains just the first element (3 in the example), column two the first two items (3 and 1 here), up to the last one that keep all.

The content in each cell is the answer to the question: is there a combination of elements in the subcollection specified by the column that have a sum specified by the row?

So, for instance, table[2][3] means: could I get 2 as a sum from [3, 1, 1]? The answer is yes, because of latter two elements.

The bottom-right cell in the table is the answer for the original problem.

Let's construct the table. Whatever I put in the topmost row is alright, since I won't use it in any way. They would represent the answer to the question if I could get a sum zero from a collection that could be empty (leftmost cell) up to including all the element in the original input (rightmost cell). Logically, we should put a True inside each of them but, since we don't care, I leave instead a bit misleading False. Forgive me, but this let me initialize with more ease the table, considering that each first cell in any row (but the zeroth one) should be initialized with False, since it is impossible having a sum different from zero from an empty collection.

Now let's scan all the cell in the table, from (1, 1) to the bottom-right one, moving from left to right, row by row.
If the currently added element in the list has the same value of the row index (that is, the total we are looking for), we can put a True in it.
If the cell on the immediate left contains a True, we can, again, safely put a True in it. Adding an element to the collection won't change the positive answer we already get.
If the first two checks don't hold, I try to get the total adding up the current value to the previous one. If so, bang, True again.

At the end of looping, we should get a table like the one shown here below.

(a) The cell (1, 2) is set to True because the column represent the subcollection {3,1}, having as latest element the row index.
(b) The cell (1, 4) is True because (1, 3) is True
(c) The cell (4, 2) is True because of cell (3, 1), checked because being the left adjacent column, moving up 1 (from the latest element in current subcollection {3,1}).

Checking the bottom-right cell we have a True, so the answer to our original question is yes.

Here is my python implementation of this algorithm:

def solution(values):
    total = sum(values)  # 1
    if total % 2:
        return False

    half = total // 2
    table = [[False] * (len(values) + 1) for _ in range(half + 1)]  # 2

    for i in range(1, half + 1):
        for j in range(1, len(values) + 1):  # 3
            if values[j-1] == i or table[i][j-1]:  # 4
                table[i][j] = True
            else:  # 5
                ii = i-values[j-1]
                if ii > 0 and table[ii][j-1]:
                    table[i][j] = True

    return table[-1][-1]  # 6

1. If the sum of values is not an even number, we already know that the list can't be split evenly.
2. Build the table as described above. Don't pay attention to the topmost row, it's just a dummy.
3. Loop on all the "real" cell, skipping the leftmost ones, that are left initialized to False.
4. See above, case (a) and (b) as described and visualized in the picture
5. This code implements the case (c). I get the the tentative row index in ii. If the relative cell on the left adjacent column is available and it is set to True, the current cell is set to True too.
6. Get the solution to the problem.

I pushed my python code and a few test cases on GitHub.

Go to the full post

Other Dynamic Programming problems

Sixth and last week of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, again on Dynamic Programming. Just three problems, fully described in this pdf.

The first one, named "Maximum Amount of Gold", states that you have a bag of given capacity, and you see n gold bars of (possibly) different weights. Push as much gold as you can in the bag.

It is easy to say that it is a variation on the classic 0/1 knapsack problem. Here the bars have all the same unitary value, so we just need to know their weight to build our solution. Not much sweat to solve it, anyway I pushed to GitHub first a python script to solve the generic problem, then one tailored on the specific requirements of the problem.

Much more challenging the other two problems. "Partitioning Souvenirs" is a 3-Partition problem. Before solving it, I practiced with the more common 2-partition version. "Maximizing the Value of an Arithmetic Expression" is well described, step by step, in the course, and I guess that I solved it easily only because of this intensive training. You could see my python implementation on GitHub.

Go to the full post

Longest Common Subsequence of Three Sequences

And finally, the last one of this group of Dynamic Programming problems. Actually, from the algorithmic point of view this is the less interesting one, being just a variation on the previous one. Now we have in input three sequences instead of two, still we have to get the longest subsequence among them.

The interest here is all in extending the algorithm to work with a three-dimensional cache. Basically just an implementation issue, that each programming language could solve in its own way.

Here is how I did it in python:

def solution_dp(a, b, c):
    cube = []
    for m in range(len(c) + 1):  # 1
        sheet = [[0] * (len(b) + 1)]
        for n in range(1, len(a) + 1):
            sheet.append([0] * (len(b) + 1))
        cube.append(sheet)

    for i in range(1, len(cube)):
        for j in range(1, len(cube[0])):
            for k in range(1, len(cube[0][0])):
                if a[j - 1] == b[k - 1] == c[i - 1]:  # 2
                    cube[i][j][k] = cube[i - 1][j - 1][k - 1] + 1
                else:
                    cube[i][j][k] = max(cube[i - 1][j][k], cube[i][j - 1][k], cube[i][j][k - 1])

    return cube[-1][-1][-1]

1. If you compare this code with the one for the 2-sequences problem, you would see how the difference is all in this extra for-loop. Now the cache is a three dimensional matrix (actually, it is not a cube but a parallelepiped, you could guess why I used a wrong name here).
2. The comparisons get now three way. Luckily, python helps us keeping them readable.

Once you manage correctly the three-level loop, the job is done.

I have pushed the complete python script and its test case to GitHub.

Go to the full post

Longest Common Subsequence of Two Sequences

Close to the previous problem, where we had to compute the minimum edit distance between two strings, here we have to get the maximum number of common elements in the same order between two sequences.

The similarity drives us to look again for a Dynamic Programming solution (adding up to the hint that these problems are in the same lot).

Here is my python solution:

def solution_dp(lhs, rhs):
    table = [[0] * (len(rhs) + 1)]  # 1
    for _ in range(1, len(lhs) + 1):
        table.append([0] * (len(rhs) + 1))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1] + 1  # 3
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])  # 4
    return table[-1][-1]

1. The cache is created as in the previous problem, bidimensional, with extra dummy row and column to keep the code simple.
2. Again, we loop on all the "real" cells in the cache, from left to right, up to down.
3. The code change in the algorithm. If the corresponding elements in the input sequences match, we put as current value the counter stored in the top-left cell, increased it by one.
4. If it is a mismatch, we don't increase anything, just get the bigger value coming from the two possible alternatives.

And that's all. Richard Bellman, who found out this algorithm, was a genius.

Python script and testcase pushed to GitHub.

Go to the full post

Computing the Edit Distance Between Two Strings

Given two strings, we should compute their edit distance. It is a well know problem, commonly solved by Dynamic Programming.

As we should expect, the idea is very close to the one seen in the previous problem, with the noticeable difference that here we are working on two lists, so our cache is going to be a bidimensional matrix and the complexity of the algorithm is moving to the O(n * m) realm, being n and m the sizes of the two strings in input.

def solution_dp(lhs, rhs):
    table = [[x for x in range(len(rhs) + 1)]]  # 1
    for k in range(1, len(lhs) + 1):
        table.append([k] + [0] * len(rhs))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1]  # 3
            else:
                table[i][j] = min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1]) + 1  # 4

    return table[-1][-1]  # 5

1. This is our cache. Instead of having a single dummy cell, here we have both zeroth row and column just filled with zeroes and not touched anymore. Again, not strictly a necessity, still the code is much more readable in this way.
2. Let's loop on all "real" elements in the matrix.
3. If the corresponding characters in the strings are the same, we have a match. Meaning the edit distance won't change, so we just copy in the current cell the value of the one on the left top corner.
4. Otherwise we have seen a change. Since we are looking to the minimal distance, we get the lowest value in the top / left cells, and increase it by one.
5. At the end of the loop, the bottom-right cell contains the result.

Incredible simple, isn't it?

Python code and testcase on GitHub.

Go to the full post

Primitive Calculator

We always start from 1, and we get the positive integer we should get to. We could apply just three operations, multiply by 2, by 3, or adding one. Which is the minimum number of operations that gives us the expected result? Which sequence will be generated?

This problem is close to the previous one, about changing money. After all, are all part of the same lot about Dynamic Programming.

The first part of the code follows almost naturally from looking at the money changer:

cache = [0] * (target + 1)  # 1
for i in range(1, len(cache)):  # 2
    cache[i] = cache[i-1] + 1
    if i % 2 == 0:
        cache[i] = min(cache[i], cache[i // 2] + 1)
    if i % 3 == 0:
        cache[i] = min(cache[i], cache[i // 3] + 1)

1. Reserve a cache for all the intermediate results, again, a dummy zeroth element would make our code simpler.
2. Loop an all the elements, checking for all the possible alternatives. The minimum local solution would be kept an used to the next steps.

Now in the last element of the cache we have the answer to the first question. To get the second answer we need to backtrack the cache, identify each choice we did at each step.

result = [1] * cache[-1]  # 1
for i in range(1, cache[-1]):  # 2
    result[-i] = target  # 3
    if cache[target-1] == cache[target] - 1:  # 4
        target -= 1
    elif target % 2 == 0 and (cache[target // 2] == cache[target] - 1):  # 5
        target //= 2
    else:  # 6 # target % 3 == 0 and (cache[target // 3] == cache[target] - 1):
        target //= 3
return result

1. This is the list we are going to return. We know its size, stored in the last element of the cache, since I have to provide an initialization value, I use 1, the right value for its leftmost element.
2. I am going to set the result list, each value but the leftmost one, already correctly set.
3. I know the rightmost value would be the target passed by the user.
4. If the previous element in the cache is the current value of the cache minus one, I got there adding one, so I here apply the inverse operator, decreasing target by one
5. If the current target is divisible by 2, and the cache at position current divided by two is actually the value of the current element of the cache minus one, we got there multiplying by two. So I apply the inverse to backtrace.
6. Otherwise we got there multiplying by three. I could have written the full elif statement as shown in the comment. The point is that by construction we have only three choices to get to an element in the cache and this must be the third one.

Python code and testcase on GitHub.

Go to the full post

Money Change Again

Already seen as greedy problem, now we have to approach it with Dynamic Programming.

We have an integer, representing a total amount that we want to get adding coins of given denominations. Our job is finding the minimum number of required coins.

If the denominations are such that we can always guarantee a safe greedy choice, the greedy solution is better. However, if, as in this case, the denominations are [1, 3, 4] we have to look somewhere else.

A recursive approach is safe, but it would lead to an exponential time complexity.

Let's solve it instead using a Dynamic Programming approach:

DENOMINATIONS = [1, 3, 4]

# ...

cache = [0] * (target + 1)  # 1

for i in range(1, target + 1):  # 2
    cache[i] = cache[i-1] + 1  # 3
    for coin in DENOMINATIONS[1:]:  # 4
        if coin <= i:
            other = cache[i-coin] + 1
            cache[i] = min(cache[i], other)

return cache[-1]  # 5

1. Each step would need to have a look at previous results, so we keep them in a cache. Notice that we keep also a dummy extra value, not a strict necessity, but keeps our code simpler.
2. Let's loop on all the "real" elements - the zeroth one, dummy, is left untouched with is original value of 0.
3. Assuming that among the available denominations there is "1", we can always select it. This is usually a safe assumption. If we can't do it, our code should be more complex, and we should also consider the case where a result can't be generated correctly.
4. Let's check all the other denominations. If the current one could be used, go and fetch in the cache the previous step, add one to it, and put it in the cache at the current position, if this is less than the currently calculated value.
5. Finally return the last calculated value.

I pushed test case and python script to GitHub.

Go to the full post

Almost five Dynamic Programming problems

I'm following edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, and I've just completed week five, that is about Dynamic Programming. To pass it, I had to solve a few problems, presented in this pdf.

Here I present them, my annotated python solutions in following posts.

Money Change Again

Given an integer amount, and an (infinite) numbers of coins of given denomination, return the minimum number of coins needed to change the full amount.

In the (sort of disappointing) previous week, they presented a greedy approach to this problem. When it works, it is cool and fast. However, to use it we have to prove that each greedy selection is safe. And that it is true only for some set of available denominations. Otherwise we must follow a different approach. And here enters Dynamic Programming.

It is a simple problem, good introduction to this technique.

Primitive Calculator

We should get to a given integer, starting from 1 and applying just a limited number of operations. Can we minimize this number?

If you see the similarity with the previous problem you have already done large part of the job.

Edit Distance Between Two Strings

Given two strings, returns their edit distance. This is a classic problem that could be solved by Dynamic Programming. The two previous one need a linear cache, here we should push our intermediate solutions in a matrix. Things are a bit more complicated, however you could find lot of documentation about this problem on the net.

Longest Common Subsequence

Given two sequences, find the largest shared subsequences. It is close to the previous problem, here we are interested just in commonalities between the two input sequences. Similar structure, some implementation differences. Also this problem is well known and studied.

Longest Common Subsequence of Three Sequences

Extension of the previous one, now we have three sequences to be compared. The point is not so much in Dynamic Programming anymore - since the structure is essentially the same - but how the programming language you use for implementing the solution manages a three-dimensional matrix.

Go to the full post

The closest pair of points

Given n points on a plane, find the smallest distance between a pair of two (different) points.

Let's see first a naive solution:

def solution_naive(points):
    size = len(points)
    if size < 2:  # 1
        return 0.0

    result = float('inf')  # 2
    for i in range(size - 1):
        for j in range(i+1, size):
            result = min(result, distance(points[i], points[j]))
    return result

1. If only one point, or no point at all, is passed, the minimum distance is defaulted to zero.
2. Otherwise initialize it to infinite, then loop on all the possible couples of points to find the one with minimum distance.

Where the distance function could be implemented as:

def distance(a, b):
    return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

The flaw of this naive implementation is that it has an obvious O(n^2) time complexity. Meaning that it rapidly becomes useless with the growing of the number points in input.

Let's apply a divide and conquer approach to this problem. The thing is that to do that we need a bit of mathematics that is beyond my knowledge. You could read this document by Subhash Suri from UC Santa Barbara for more details.

Firstly we sort the points for their x component, then we call the recursive function:

def solution_dac(points):
    points.sort()
    return closest_distance(points)

We firstly divide the problem up to get pieces that are so simple that they can be solved with the naive algorithm, and apply a merging part to "conquer" that step:

def closest_distance(points):
    size = len(points)
    if size < 4:  # 1
        return solution_naive(points)

    lhs = points[:size // 2]  # 2
    rhs = points[size // 2:]

    left = closest_distance(lhs)
    right = closest_distance(rhs)
    result = min(left, right)
    if result == 0.0:
        return result

    median = (lhs[-1][0] + rhs[0][0]) / 2  # 3
    closers = []
    for i in range(len(lhs)):
        if abs(lhs[i][0] - median) < result:
            closers.append(lhs[i])
    for i in range(len(rhs)):
        if abs(rhs[i][0] - median) < result:
            closers.append(rhs[i])
    closers.sort(key=lambda p: p[1])  # 4

    for i in range(len(closers) - 1):  # 5
        for j in range(i + 1, min(i + 6, len(closers))):
            if abs(closers[i][1] - closers[j][1]) < result:
                result = min(result, distance(closers[i], closers[j]))
    return result

1. For up to 3 points we could use the naive approach.
2. Split the list of points in two parts, left hand side and right hand side, and iterate on them the algorithm. If we see a minimal distance of zero, meaning two overlapping points, there is no use in going on.
3. Draw a line between the rightmost point in the left part of point collection and the leftmost in right part. Then add to a buffer list all the points that have a distance to this median line that is less than the currently found closest distance.
4. Sort the points on their "y" component.
5. And here happens the magic. There is a theorem stating that we could stop checking at 6 when looking for a closest distance in this condition.

The cutoff at 6 ensures that the time complexity of this algorithm if O(n log n).

Full python code on GitHub.

Go to the full post

Majority element

Given a list of integers, return 1 if there is an element that appears more than half the time in the list, otherwise 0.

Naive solution

Loop on all the items in the list, and count each of them. If we find a result that is bigger than half the size of the list, we have a positive result.

We can try to apply some improvement to this algorithm, for instance, we can stop checking as soon as we reach the first element after the half size, and we don't need to check each element from the beginning of the list, since if there is an instance of that element before the current point we have already count it, and if there is not, there is no use in check it. Still, the time complexity is O(n^2), so we can use it only for very short input lists.

Divide and conquer

We divide the problem until we reach the base case of one or two elements - that could be solved immediately. Then we "conquer" this step determining which element is majority in the current subinterval. I described in detail my python code that implements this approach in the previous post.

Sorting

This is a simple improvement of the naive solution, still it is powerful enough to give better results than the divide and conquer approach.

The idea is sorting the input data, and then compare the i-th element against the i-th + half size of the list. If it is the same, that is a positive result. The most expensive part of this approach is in the sorting phase, O(n log n).

Hash table

If we don't mind to use some relevant extra space, we can scan the input list pushing in a hash table each new element that we find, increasing its value each time we see it again. Than we scan the values in the hash table looking for a more than half list size one.

The python Counter collection allows us to solve this problem as a one-liner:

def solution_hash(data):
    return True if Counter(data).most_common(1)[0][1] > len(data) // 2 else False

The time complexity is linear.

Boyer–Moore

The Boyer–Moore algorithm leads to a fun, elegant, and superfast solution.

We perform a first scan of the list, looking for a candidate:

def bm_candidate(data):
    result = None
    count = 0
    for element in data:  # 1
        if count == 0:  # 2
            result = element
            count = 1
        elif element == result:  # 3
            count += 1
        else:
            count -= 1

    return result

1. Loop on all the elements
2. If the candidate counter is zero, we get the current element as candidate, setting the count to one.
3. If we see another instance of the current candidate, we increase the counter. Otherwise we decrease the counter.

This scan ensures to identify the majority element, if it exists. However, if there is not a majority element, it returns the last candidate seen. So we need to perform another linear scan to ensure that the candidate is actually the majority element.

Nonetheless, Boyer–Moore wins easily against the other seen algorithms.

See my full python code for this problem, and the other from the same lot, on GitHub.

Go to the full post

A few divide and conquer problems

The exercises for week four of edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego are, in my opinion, a bit disappointing. I would have preferred if they pushed me to think more to how the divide and conquer strategy apply to different situation. Still, there are a few interesting points than we can get from them.

Binary Search

Task: Given in input two list of integers, being assured that the first one is sorted, output a list of integers where each value is the index of the positional matching element in the second list, as found in the first one, or -1 if missing.

There is almost nothing to say about to this problem. It is just a matter of implementing binary search.

Majority Element

Task: Given a list of integers, return true if it contains a majority element, that is, there is an element repeated more than half the size of the list.

Solving this problem with a divide and conquer approach, is not the best idea one could have. Even though it is certainly better than a naive approach, the common alternatives that should spring to the mind of any programmer (just a couple of hints, sorting, hashing) look more attractive. And I haven't even started talking about the amazing Boyer–Moore algorithm.

My python solution is a recursive function that returns the majority element in the closed subinterval [left..right] on the passed data list, or None if there is not such a beast:

def majority(data, left, right):
    size = right - left + 1
    if size < 3:  # 1
        return data[left] if data[left] == data[right] else None

    pivot = left + size // 2  # 2
    lhs = majority(data, left, pivot)
    rhs = majority(data, pivot + 1, right)

    if not lhs or not rhs:  # 3
        return lhs if lhs else rhs
    if lhs == rhs:
        return lhs

    for candidate in (lhs, rhs):  # 4
        count = 0
        for i in range(left, right + 1):
            if data[i] == candidate:
                count += 1
        if count > size // 2:
            return candidate
    return None

1. Base case, when we have just one or two elements, it is immediate to get the majority.
2. The divide part of the algorithm. Split the list in two, call recursively the function on the left and right side
3. Base cases for the conquering. If we have at least a None, return the definite element, if any, or None. Otherwise, if both the candidate majority are the same, return it.
4. The expensive part of the algorithm. We should decide which candidate choose, and to do that we just count the instances of both on the entire interval. If none of them has the majority here, we return None.

In the next post I provide different approaches to this problem.

Improving Quick Sort

Task: Improve the "plain" quick sort algorithm adapting it to support a 3-way partitioning.

I didn't spend any time at all for selecting a decent pivot, I just picked anytime the leftmost element. Don't mind about it, just focus on the partitioning.

Number of Inversions

Task: Count the number of inversions in a (partially sorted) list of integers.

Here the point is tweaking a merge sort algorithm to keep track of the detected inversions.

Organizing a Lottery

Given in input a list of segments on the x axis, each item being a 2-tuple of integers, begin and end, and a list of integers, representing points on the same axis, count for each point how many segments it intersects.

I spent quite a long time trying to figure out how to solve this problem using a divide and conquer approach. After a while, I decided to implement a solution based on sorting instead. Then I asked on the course forum about the right way to solve this exercise. Well, it looks like it was meant to be solved with sorting. How disappointing.

My solution is based on the consideration that I could get the number of intersecting segments in a point simply counting all the begin-end of segments up to there.

Here is my python code:

def solution_sort(segments, points):
    s_open = []  # 1
    s_close = []

    for segment in segments:
        s_open.append(segment[0])
        s_close.append(segment[1])

    s_open.sort()  # 2
    s_close.sort()
    points.sort()

    results = []
    count = 0  # 3
    oi = 0  # 4
    ci = 0
    size = len(segments)
    for point in points:  # 5
        while oi < size and s_open[oi] <= point:  # 6
            oi += 1
            count += 1
        while ci < size and s_close[ci] < point:  # 7
            ci += 1
            count -= 1
        results.append(count)

    return results

1. I put in the list s_open all the beginnings of segments, and in s_close their endings.
2. Segments and point had better to be sorted.
3. Current count for the number of segments currently open.
4. I am going to linearly scan open and close segment lists, oi and ci are the indexes for their current positions.
5. The scan is ruled by the points, being sorted, I start from the leftmost.
6. Each opening segment detected up to the point is added to the count of the currently open segments.
7. Decrease the count of open segments when a end of segment is seen. But be careful, the close should be strictly minor than the point.

Finding the Closest Pair of Points

Task: Given n points in a bidimensional space, find the smallest distance between a pair of them.

This is not an easy problem. Fortunately, it is also a well known one. See, for instance, this paper by Subhash Suri. In this other post, I show my python solution to this problem following that algorithm.

I pushed on GitHub the full python code for these problems.

Go to the full post