CODEWITHSUNDEEP
algorithm
Jitendra Sarswat
Jitendra Sarswat

Reputation: 111

Finding largest minimum distance among k objects in n possible distinct positions?

What is an efficient way to find largest minimum distance among k objects in n possible distinct positions?

For eg:

N: Number of distinct positions Lets say N = 5 and the 5 positions are {1,2,4,8,9}

K: Number of objects let say k = 3

So the possible answer (Largest Minimum Distance) would be: 3 if we put objects at {1,4,8} or {1,4,9}

Upvotes: 6

Views: 9455

Answers (1)

kraskevich
kraskevich

Reputation: 18556

  1. Let's do a binary search over the answer.

  2. For a fixed answer x, we can check whether it is feasible or not using a simple linear greedy algorithm(pick the first element and then iterate over the rest of the array adding the current element if the distance between it and the last picked element is greater than or equal to x). In the end, we just need to check that the number of picked elements is at least k.

The time complexity is O(n * log MAX_A), where MAX_A is the maximum element of the array.

Here is a pseudo code for this algorithm:

def isFeasible(positions, dist, k):
    taken = 1
    last = positions[0]
    for i = 1 ... positions.size() - 1:
        if positions[i] - last >= dist:
            taken++
            last = positions[i]
    return taken >= k

def solve(positions, k):
    low = 0 // definitely small enough
    high = maxElement(positions) - minElement(positions) + 1 // definitely too big
    while high - low > 1:
        mid = (low + high) / 2
        if isFeasible(positions, mid, k):
            low = mid
        else:
            high = mid
    return low

Upvotes: 8

Related Questions