Find the distance between two person after reconstruction of queue

0 0 6 minutes read

Given a 2D array of size N containing distinct height of people standing in a queue, and a number corresponding to each person (P) that gives the number of persons who are shorter than P and standing in front of P. The task is to determine the distance between two people A and B in the actual order of people’s height.
Example:

Input: A = 6, B = 5, arr[][] = {{5, 0}, {3, 0}, {2, 0},
{6, 4}, {1, 0}, {4, 3}}
Output: 4
Actual arrangement of people’s height
{5, 0}, {3, 0}, {2, 0}, {1, 0}, {6, 4}, {4, 3}
Distance between 6 and 5 is 4
Input: A = 1, B = 3, arr[][] = {{3, 0}, {1, 0}, {2, 1}};
Output: 1

Naive Approach: A brute force approach is to try out all possible permutation of the given heights of the order of the phoenix members, and verify if the in front numbers match for the given sequence, then find the distance between two people.
Time Complexity: O(N!)
Efficient Approach: Another approach is to store person height and it’s front value, store it in any vector and sort the vector according to heights in ascending order. Now, traverse the vector and insert the person at the kth position in the position vector where k is the number of people standing in front of the people of the current person.
Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the correct order and then
// return the distance between the two persons
int getDistance(int arr[][2], int n, int a, int b)
{
    vector<pair<int, int> > vp;
 
    // Make pair of both height & infront
    // and insert to vector
    for (int i = 0; i < n; i++) {
        vp.push_back({ arr[i][0], arr[i][1] });
    }
 
    // Sort the vector in ascending order
    sort(vp.begin(), vp.end());
 
    // Find the correct place for every person
    vector<int> pos;
 
    // Insert into position vector
    // according to infront value
    for (int i = 0; i < vp.size(); i++) {
        int height = vp[i].first;
        int k = vp[i].second;
        pos.insert(pos.begin() + k, height);
    }
 
    int first = -1, second = -1;
 
    for (int i = 0; i < pos.size(); i++) {
        if (pos[i] == a)
            first = i;
        if (pos[i] == b)
            second = i;
    }
 
    return abs(first - second);
}
 
// Driver code
int main()
{
    int arr[][2] = {
        { 5, 0 },
        { 3, 0 },
        { 2, 0 },
        { 6, 4 },
        { 1, 0 },
        { 4, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int a = 6, b = 5;
 
    cout << getDistance(arr, n, a, b);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
class GFG {
 
  // Function to find the correct order and then
  // return the distance between the two persons
  static int getDistance(int[][] arr, int n, int a, int b)
  {
    int vp[][] = new int[n][2];
 
    // Make pair of both height & infront
    // and insert to vector
    for(int i=0; i < n; i++) {
      vp[i][0] = arr[i][0];
      vp[i][1] = arr[i][1];
    }
 
    // Sort the vector in ascending order
    Arrays.sort(vp, (c,d)-> c[0]-d[0]);
 
    // Find the correct place for every person
    int pos[] = new int[n];
    for(int i = 0; i < n; i++) {
      pos[i] = 0;
    }
 
    // Insert into position vector
    // according to infront value
    for(int i = 0; i < vp.length; i++) {
      int height = vp[i][0];
      int k = vp[i][1];
      pos[k] = height;
    }
 
    int first = -1, second = -1;
 
    for(int i = 0; i < pos.length; i++) {
      if (pos[i] == a)
        first = i;
      if (pos[i] == b)
        second = i;
    }
 
    return Math.abs(first - second);
  }
 
  public static void main(String[] args)
  {
    // Driver code
    int arr[][] = { { 5, 0 }, { 3, 0 }, { 2, 0 },
                   { 6, 4 }, { 1, 0 }, { 4, 3 } };
    int n = arr.length;
    int a = 6, b = 5;
 
    System.out.println(getDistance(arr, n, a, b));
  }
}
 
//  This code is contributed by aadityaburujwale.

Python

# Python implementation of the approach
 
# Function to find the correct order and then
# return the distance between the two persons
def getDistance(arr, n, a, b):
    vp = []
 
    # Make pair of both height & infront
    # and insert to vector
    for i in range(n):
        vp.append([arr[i][0], arr[i][1]])
 
    # Sort the vector in ascending order
    vp = sorted(vp)
 
    # Find the correct place for every person
    pos = [0 for i in range(n)]
 
    # Insert into position vector
    # according to infront value
    for i in range(len(vp)):
        height = vp[i][0]
        k = vp[i][1]
        pos[k] = height
 
    first = -1
    second = -1
 
    for i in range(n):
        if (pos[i] == a):
            first = i
        if (pos[i] == b):
            second = i
 
    return abs(first - second)
 
# Driver code
arr = [[5, 0],
        [3, 0],
        [2, 0],
        [6, 4],
        [1, 0],
        [4, 3]]
n = len(arr)
a = 6
b = 5
 
print(getDistance(arr, n, a, b))
 
# This code is contributed by mohit kumar 29

C#

using System;
using System.Collections.Generic;
 
public class GFG {
 
  public static int cmp(KeyValuePair<int, int> a,
                        KeyValuePair<int, int> b)
  {
    if (a.Key > b.Key)
      return 1;
    return -1;
  }
 
  // Function to find the correct order and then
  // return the distance between the two persons
  public static int getDistance(int[, ] arr, int n, int a,
                                int b)
  {
    var vp = new List<KeyValuePair<int, int> >();
 
    // Make pair of both height & infront
    // and insert to vector
    for (int i = 0; i < n; i++) {
 
      vp.Add(new KeyValuePair<int, int>(arr[i, 0],
                                        arr[i, 1]));
    }
 
    // Sort the vector in ascending order
    vp.Sort(cmp);
 
    // Find the correct place for every person
    List<int> pos = new List<int>();
    for (int i = 0; i < 100; i++) {
      pos.Add(0);
    }
 
    // Insert into position vector
    // according to infront value
    for (int i = 0; i < vp.Count; i++) {
      int height = vp[i].Key;
      int k = vp[i].Value;
      pos[k] = height;
    }
 
    int first = -1, second = -1;
 
    for (int i = 0; i < pos.Count; i++) {
      if (pos[i] == a)
        first = i;
      if (pos[i] == b)
        second = i;
    }
 
    return Math.Abs(first - second);
  }
 
  static public void Main()
  {
 
    int[, ] arr = { { 5, 0 }, { 3, 0 }, { 2, 0 },
                   { 6, 4 }, { 1, 0 }, { 4, 3 } };
    int n = arr.GetLength(0);
    int a = 6, b = 5;
    Console.WriteLine(getDistance(arr, n, a, b));
  }
}
 
// This code is contributed by akashish__

Javascript

<script>
// Javascript implementation of the approach
 
// Function to find the correct order and then
// return the distance between the two persons    
function getDistance(arr,n,a,b)
{
    let vp=[];
    // Make pair of both height & infront
    // and insert to vector
    for (let i = 0; i < n; i++) {
        vp.push([ arr[i][0], arr[i][1] ]);
    }
   
    // Sort the vector in ascending order
    vp.sort(function(c,d){return c[0]-d[0];});
   
    // Find the correct place for every person
    let pos=new Array(n);
    for(let i=0;i<n;i++)
    {
        pos[i]=0;
    }
       
    // Insert into position vector
    // according to infront value
    for (let i = 0; i < vp.length; i++) {
        let height = vp[i][0];
        let k = vp[i][1];
        pos[k] = height
    }
   
    let first = -1, second = -1;
   
    for (let i = 0; i < pos.length; i++) {
        if (pos[i] == a)
            first = i;
        if (pos[i] == b)
            second = i;
    }
   
    return Math.abs(first - second);
}
 
// Driver code
let arr = [
        [ 5, 0 ],
        [ 3, 0 ],
        [ 2, 0 ],
        [ 6, 4 ],
        [ 1, 0 ],
        [ 4, 3 ]
    ];
    let n = arr.length;
    let a = 6, b = 5;
   
    document.write(getDistance(arr, n, a, b));
 
// This code is contributed by unknown2108
</script>

Output:

Time Complexity: O(n²)
Space Complexity: O(n) as arrays like pos and vp has been created. Here, n is the size of the input array.

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!