Find integral points with minimum distance from given set of integers using BFS

Aman Chourasiya
Last Updated: May 13, 2022

Understanding

This blog will analyze a problem based on Breadth-First Search (BFS) - one of the most popular topics in Graphs and related algorithms. Breadth-First Search is a widely asked topic in coding interviews and programming contests. It is based on the Breadth-First Traversal of a tree, with few minor changes because a graph can have cycles. There are certain variations of BFS as well, for example, 0-1 BFS, multi-source BFS, etc. In this blog, we will solve a problem based on multi-source BFS.

 

The Problem Statement

Ninja has given you an array points of size N and an integer K. Each element of the points array represents a point on the x-axis. For example, the element on the ith index, points[i], represents (points[i], 0) coordinate on the x-axis.

Your task is to find K distinct integral points that are not present in the given array such that the sum of their distances from the nearest point in the given array is minimized.

An integral point means that x-coordinate of the point must be an integer.

 

Input

points = [-1, 1, 3]

K = 3

 

Output

[0, 2, 4]

 

Explanation

Each point in the output - (0, 0), (2, 0), and (4, 0) are at a unit distance from their nearest point in the points array. It is the optimal answer as the minimum distance between two distinct integral points cannot be less than one.

There are other optimal solutions as well, for example, [-2, 2, 4].

 

Approach

We will solve this challenge using multi-source Breadth-First Search. As you can observe, we should first include all such points which are at a unit distance from their corresponding nearest point in the array. After this, we should consider points at two units of distance and so on.

This observation serves as the motivation to use multi-source BFS to solve the problem. If we run a BFS with all elements in the points array as starting points, we would traverse the required points in order of increasing distance.

As we need to include only distinct integral points different from the ones already present in the given array, we can keep track of the points visited so far using the map container in C++.

Algorithm

  1. Create a queue and a map container. Include all the array elements in the queue and mark them visited in the map container as well.
  2. Then, for any element, say X, we'll use the hashmap to see if (X-1) or (X+1) is encountered or not. If any of them haven't been encountered yet, we add that element to our answer array, queue, and hash.
  3. Repeat this until we encounter K new elements.

 

Program

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; cin>>n; // size of the array.
    vector<int> points(n); // points array.
    for(int i = 0; i < n; i++){
        cin>>points[i]; 
    }
    int K; cin>>K; // number of integral points required.

    map<int,int> mpx; // map container required to keep track of visited points.
    queue<int> q;
    for(int i = 0; i < n; i++){
        q.push(points[i]); // multi-source BFS initialization.
        mpx[points[i]] = 1// the required must be different from the elements in the array.
    }

    vector<int> answer; // vector to store the answer.
    while(!q.empty() && K > 0){
        int point = q.front();
        q.pop();

        if(mpx.find(point - 1) == mpx.end()){ // check if the left point is not visited.
            mpx[point - 1] = 1// include it in the answer by marking it visited.
            answer.push_back(point-1); // push it in the answer.
            K--;
            q.push(point - 1); // push it in the queue for generating other points.
        }

        if(K > 0 && mpx.find(point + 1) == mpx.end()){ // similarly check for the right point.
            mpx[point + 1] = 1// include it in the answer by marking it visited.
            answer.push_back(point + 1);
            K--;
            q.push(point + 1);
        }
    }

    for(int i = 0; i < answer.size(); i++){ // print the answer.
        cout<<answer[i]<<" ";
    }
    cout<<endl;
}

 

Input

points = [-1, 0, 2, 3]

K = 5

 

Output

[-2, 1, 4, -3, 5]

Time Complexity

The time complexity of the above approach is O(M * log(M)), where M=N+K. It is because time complexity of the map container's find function is O(log(N)), where N is the size of the container. We make at most O(N + K) calls to the find function. Hence the given time complexity.

 

Space Complexity

The space complexity of the above approach is O(N) as the size of the queue can be at most 2*N at any instant. 

 

Key Takeaways

In this blog, we learned about multi-source BFS and its applications. Multi-source BFS is a common variant of BFS that is frequently questioned in programming competitions. In multi-source BFS, as the name suggests, we run the BFS algorithm with more than one source. There are other variants of BFS as well as mentioned at the starting of the blog.

Hence learning never stops, and there is a lot more to learn.

So head over to our practice platform CodeStudio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes