Find integral points with minimum distance from given set of integers using BFS | C ++ implementation of above approach ; Function to find points at minimum distance ; Hash to store points that are encountered ; Queue to store initial set of points ; Vector to store integral points ; Using bfs to visit nearest points from already visited points ; Get first element from queue ; Check if ( x - 1 ) is not encountered so far ; Update hash with this new element ; Insert ( x - 1 ) into queue ; Push ( x - 1 ) as new element ; Decrement counter by 1 ; Check if ( x + 1 ) is not encountered so far ; Update hash with this new element ; Insert ( x + 1 ) into queue ; Push ( x + 1 ) as new element ; Decrement counter by 1 ; Print result array ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minDistancePoints ( int A [ ] , int K , int n ) { map < int , int > m ; queue < int > q ; for ( int i = 0 ; i < n ; ++ i ) { m [ A [ i ] ] = 1 ; q . push ( A [ i ] ) ; } vector < int > ans ; while ( K > 0 ) { int x = q . front ( ) ; q . pop ( ) ; if ( ! m [ x - 1 ] && K > 0 ) { m [ x - 1 ] = 1 ; q . push ( x - 1 ) ; ans . push_back ( x - 1 ) ; K -- ; } if ( ! m [ x + 1 ] && K > 0 ) { m [ x + 1 ] = 1 ; q . push ( x + 1 ) ; ans . push_back ( x + 1 ) ; K -- ; } } for ( auto i : ans ) cout << i << " ▁ " ; } int main ( ) { int A [ ] = { -1 , 4 , 6 } ; int K = 3 ; int n = sizeof ( A ) / sizeof ( A [ 0 ] ) ; minDistancePoints ( A , K , n ) ; return 0 ; }