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

0 0 7 minutes read

Given an integer array A[] of length N and an integer K. The 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 A[] is minimized.

An integral point is defined as the point with both the coordinates as integers. Also, in the x-axis, we don’t need to consider y-coordinate because y-coordinated of all the points is equal to zero.

Examples:

Input: A[] = { -1, 4, 6 }, K = 3
Output: -2, 0, 3
Explanation:
Nearest point for -2 in A[] is -1 -> distance = 1
Nearest point for 0 in A[] is -1 -> distance = 1
Nearest point for 3 in A[] is 4 -> distance = 1
Total distance = 1 + 1 + 1 = 3 which is minimum possible distance.
Other results are also possible with the same minimum distance.
Input: A[] = { 0, 1, 3, 4 }, K = 5
Output: -1, 2, 5, -2, 6
Explanation:
Nearest point for -1 in A[] is 0 -> distance = 1
Nearest point for 2 in A[] is 3 -> distance = 1
Nearest point for 5 in A[] is 4 -> distance = 1
Nearest point for -2 in A[] is 0 -> distance = 2
Nearest point for 6 in A[] is 4 -> distance = 2
Total distance = 2 + 1 + 1 + 1 + 2 = 7 which is minimum possible distance.

Approach: We will solve this problem by using the concept of Breadth First Search.

We will initially assume the given set of integers as the root element and push it in Queue and Hash.
Then for any element say X, we will simply check if (X-1) or (X+1) is encountered or not using a hashmap. If any of them are not encountered so far then we push that element in our answer array and queue and hash as well.
Repeat this until we encountered K new elements.

Below is the implementation of the above approach.

C++

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

Java

// Java implementation of above approach
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
 
class Geeks{
     
// Function to find points at
// minimum distance
static void minDistancePoints(int A[], 
                              int K, int n)
{
     
    // Hash to store points
    // that are encountered
    Map<Integer, 
        Boolean> m = new HashMap<Integer, 
                                 Boolean>();
 
    // Queue to store initial
    // set of points
    Queue<Integer> q = new LinkedList<Integer>();
 
    for(int i = 0; i < n; ++i)
    {
        m.put(A[i], true);
        q.add(A[i]);
    }
 
    // List to store integral
    // points
    LinkedList<Integer> ans = new LinkedList<Integer>();
 
    // Using bfs to visit nearest
    // points from already
    // visited points
    while (K > 0)
    {
         
        // Get first element from
        // queue
        int x = q.poll();
 
        // Check if (x-1) is not
        // encountered so far
        if (!m.containsKey(x - 1) && K > 0) 
        {
             
            // Update hash with
            // this new element
            m.put(x - 1, true);
 
            // Insert (x-1) into
            // queue
            q.add(x - 1);
 
            // Push (x-1) as
            // new element
            ans.add(x - 1);
 
            // Decrement counter
            // by 1
            K--;
        }
 
        // Check if (x+1) is not
        // encountered so far
        if (!m.containsKey(x + 1) && K > 0)
        {
             
            // Update hash with
            // this new element
            m.put(x + 1, true);
 
            // Insert (x+1) into
            // queue
            q.add(x + 1);
 
            // Push (x+1) as
            // new element
            ans.add(x + 1);
 
            // Decrement counter
            // by 1
            K--;
        }
    }
 
    // Print result array
    for(Integer i : ans)
        System.out.print(i + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = new int[] { -1, 4, 6 };
    int K = 3;
    int n = A.length;
     
    minDistancePoints(A, K, n);
}
}
 
// This code is contributed by Rajnis09

Python3

# Python 3 implementation
# of above approach
 
# Function to find points 
# at minimum distance
def minDistancePoints(A, K, n):
   
    # Hash to store points
    # that are encountered
    m = {}
 
    # Queue to store initial
    # set of points
    q = []
 
    for i in range(n):
        m[A[i]] = 1
        q.append(A[i])
 
    # Vector to store 
    # integral points
    ans = []
 
    # Using bfs to visit nearest
    # points from already
    # visited points
    while (K > 0):
       
        # Get first element from
        # queue
        x = q[0]
        q = q[1::]
 
        # Check if (x-1) is not
        # encountered so far
        if ((x - 1) not in m and
             K > 0):
           
            # Update hash with
            # this new element
            m[x - 1] = m.get(x - 1, 0) + 1
 
            # Insert (x-1) into
            # queue
            q.append(x - 1)
 
            # Push (x-1) as
            # new element
            ans.append(x - 1)
 
            # Decrement counter
            # by 1
            K -= 1
 
        # Check if (x+1) is not
        # encountered so far
        if ((x + 1) not in m and
             K > 0):
            # Update hash with
            # this new element
            m[x + 1] = m.get(x + 1, 0) + 1
 
            # Insert (x+1) into
            # queue
            q.append(x + 1)
 
            # Push (x+1) as
            # new element
            ans.append(x + 1)
            # Decrement counter
            # by 1
            K -= 1
 
    # Print result array
    for i in ans:
        print(i, end = " ")
 
# Driver code
if __name__ == '__main__':
   
    A =  [-1, 4, 6]
    K = 3
    n =  len(A)
    minDistancePoints(A, K, n)
 
# This code is contributed by bgangwar59

C#

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find points at
// minimum distance
static void minDistancePoints(int []A, 
                              int K, int n)
{
     
    // Hash to store points
    // that are encountered
    Dictionary<int, 
               Boolean> m = new Dictionary<int, 
                                           Boolean>();
 
    // Queue to store initial
    // set of points
    Queue<int> q = new Queue<int>();
 
    for(int i = 0; i < n; ++i)
    {
        m.Add(A[i], true);
        q.Enqueue(A[i]);
    }
 
    // List to store integral
    // points
    List<int> ans = new List<int>();
 
    // Using bfs to visit nearest
    // points from already
    // visited points
    while (K > 0)
    {
         
        // Get first element from
        // queue
        int x = q.Dequeue();
 
        // Check if (x-1) is not
        // encountered so far
        if (!m.ContainsKey(x - 1) && K > 0) 
        {
             
            // Update hash with
            // this new element
            m.Add(x - 1, true);
 
            // Insert (x-1) into
            // queue
            q.Enqueue(x - 1);
 
            // Push (x-1) as
            // new element
            ans.Add(x - 1);
 
            // Decrement counter
            // by 1
            K--;
        }
 
        // Check if (x+1) is not
        // encountered so far
        if (!m.ContainsKey(x + 1) && K > 0)
        {
             
            // Update hash with
            // this new element
            m.Add(x + 1, true);
 
            // Insert (x+1) into
            // queue
            q.Enqueue(x + 1);
 
            // Push (x+1) as
            // new element
            ans.Add(x + 1);
 
            // Decrement counter
            // by 1
            K--;
        }
    }
 
    // Print result array
    foreach(int i in ans)
        Console.Write(i + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    int []A = new int[] { -1, 4, 6 };
    int K = 3;
    int n = A.Length;
     
    minDistancePoints(A, K, n);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
    // Javascript implementation of above approach
     
    // Function to find points at
    // minimum distance
    function minDistancePoints(A, K, n)
    {
 
        // Hash to store points
        // that are encountered
        let m = new Map();
 
        // Queue to store initial
        // set of points
        let q = [];
 
        for(let i = 0; i < n; ++i)
        {
            m.set(A[i], true);
            q.push(A[i]);
        }
 
        // List to store integral
        // points
        let ans = [];
 
        // Using bfs to visit nearest
        // points from already
        // visited points
        while (K > 0)
        {
 
            // Get first element from
            // queue
            let x = q.shift();
 
            // Check if (x-1) is not
            // encountered so far
            if (!m.has(x - 1) && K > 0)
            {
 
                // Update hash with
                // this new element
                m.set(x - 1, true);
 
                // Insert (x-1) into
                // queue
                q.push(x - 1);
 
                // Push (x-1) as
                // new element
                ans.push(x - 1);
 
                // Decrement counter
                // by 1
                K--;
            }
 
            // Check if (x+1) is not
            // encountered so far
            if (!m.has(x + 1) && K > 0)
            {
 
                // Update hash with
                // this new element
                m.set(x + 1, true);
 
                // Insert (x+1) into
                // queue
                q.push(x + 1);
 
                // Push (x+1) as
                // new element
                ans.push(x + 1);
 
                // Decrement counter
                // by 1
                K--;
            }
        }
 
        // Print result array
        for(let i = 0; i < ans.length; i++)
            document.write(ans[i] + " ");
    }
     
    let A = [ -1, 4, 6 ];
    let K = 3;
    let n = A.length;
      
    minDistancePoints(A, K, n);
 
// This code is contributed by divyeshrabadiya07.
</script>

Output:

-2 0 3

Time Complexity: O(M*log(M)), where M = N + K.

Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!