# Find the distance between two person after reconstruction of queue

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 4Input:A = 1, B = 3, arr[][] = {{3, 0}, {1, 0}, {2, 1}};Output:1

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**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;` `}` |

## 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` |

## 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:**

4

**Time Complexity:** O(n^{2})