Find integral points with minimum distance from given set of integers using BFS | 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
def minDistancePoints ( A , K , n ) : NEW_LINE INDENT m = { } NEW_LINE q = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ A [ i ] ] = 1 NEW_LINE q . append ( A [ i ] ) NEW_LINE DEDENT ans = [ ] NEW_LINE while ( K > 0 ) : NEW_LINE INDENT x = q [ 0 ] NEW_LINE q = q [ 1 : : ] NEW_LINE if ( ( x - 1 ) not in m and K > 0 ) : NEW_LINE INDENT m [ x - 1 ] = m . get ( x - 1 , 0 ) + 1 NEW_LINE q . append ( x - 1 ) NEW_LINE ans . append ( x - 1 ) NEW_LINE K -= 1 NEW_LINE DEDENT if ( ( x + 1 ) not in m and K > 0 ) : NEW_LINE INDENT m [ x + 1 ] = m . get ( x + 1 , 0 ) + 1 NEW_LINE q . append ( x + 1 ) NEW_LINE ans . append ( x + 1 ) NEW_LINE K -= 1 NEW_LINE DEDENT DEDENT for i in ans : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ - 1 , 4 , 6 ] NEW_LINE K = 3 NEW_LINE n = len ( A ) NEW_LINE minDistancePoints ( A , K , n ) NEW_LINE DEDENT