Given an array arr[] of N integers and an integer K, the task is to sort these integers according to their distance from given integer K. If more than 1 element is at the same distance, print them in increasing order.
Note: Distance between two elements in the array is measured as the difference between their index.
Note: The integer K is always present in array arr[] and is unique.
Examples:
Input: arr[] = {12, 10, 102, 31, 15}, K = 102
Output: 102 10 31 12 15
Explanation:
Elements at their respective distance from K are,
At distance 0: 102
At distance 1: 10, 31 in sorted form.
At distance 2: 12, 15 in sorted form.
Hence, our resultant array is [ 102, 10, 31, 12, 15 ]Input: arr[] = {14, 1101, 10, 35, 0}, K = 35
Output: 35 0 10 1101 14
Explanation:
Elements at their respective distance from K are,
At distance 0: 35
At distance 1: 10, 0 and in sorted form we have 0, 10.
At distance 2: 1101
At distance 3: 14
Hence, our resultant array is [ 35, 0, 10, 1101, 14 ]
Approach :
To solve the problem mentioned above we create an auxiliary vector to store elements at any distance from K. Then find the position of given integer K in the array arr[] and insert the element K at position 0 in the auxiliary vector. Traverse the array in the left direction from K and insert those elements in the vector at their distance from K. Repeat the above process for the right side elements of K. Finally, print the array elements from distance 0 in sorted order.
Below is the implementation of the above approach:
C++
// C++ implementation to Sort the integers in // array according to their distance from given // element K present in the array #include <bits/stdc++.h> using namespace std; // Function to get sorted array based on // their distance from given integer K void distanceSort( int arr[], int K, int n) { // Vector to store respective elements // with their distance from integer K vector< int > vd[n]; // Find the position of integer K int pos; for ( int i = 0; i < n; i++) { if (arr[i] == K) { pos = i; break ; } } // Insert the elements with their // distance from K in vector int i = pos - 1, j = pos + 1; // Element at distance 0 vd[0].push_back(arr[pos]); // Elements at left side of K while (i >= 0) { vd[pos - i].push_back(arr[i]); --i; } // Elements at right side of K while (j < n) { vd[j - pos].push_back(arr[j]); ++j; } // Print the vector content in sorted order for ( int i = 0; i <= max(pos, n - pos - 1); ++i) { // Sort elements at same distance sort(begin(vd[i]), end(vd[i])); // Print elements at distance i from K for ( auto element : vd[i]) cout << element << " " ; } } // Driver code int main() { int arr[] = {14, 1101, 10, 35, 0 }, K = 35; int n = sizeof (arr) / sizeof (arr[0]); distanceSort(arr, K, n); return 0; } |
Java
// Java implementation to Sort the integers in // array according to their distance from given // element K present in the array import java.util.*; class GFG{ // Function to get sorted array based on // their distance from given integer K @SuppressWarnings ( "unchecked" ) static void distanceSort( int arr[], int K, int n) { // Vector to store respective elements // with their distance from integer K Vector vd[] = new Vector[n]; for ( int i = 0 ; i < n; i++) { vd[i] = new Vector(); } // Find the position of integer K int pos = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] == K) { pos = i; break ; } } // Insert the elements with their // distance from K in vector int i = pos - 1 , j = pos + 1 ; // Element at distance 0 vd[ 0 ].add(arr[pos]); // Elements at left side of K while (i >= 0 ) { vd[pos - i].add(arr[i]); --i; } // Elements at right side of K while (j < n) { vd[j - pos].add(arr[j]); ++j; } // Print the vector content in sorted order for (i = 0 ; i <= Math.max(pos, n - pos - 1 ); ++i) { // Sort elements at same distance Collections.sort(vd[i]); // Print elements at distance i from K for (j = 0 ; j < vd[i].size(); j++) { int element = ( int )vd[i].get(j); System.out.print(element + " " ); } } } // Driver Code public static void main(String s[]) { int arr[] = { 14 , 1101 , 10 , 35 , 0 }; int K = 35 ; int n = arr.length; distanceSort(arr, K, n); } } // This code is contributed by rutvik_56 |
Python3
# Python3 implementation to Sort the integers in # array according to their distance from given # element K present in the array # Function to get sorted array based on # their distance from given integer K def distanceSort(arr,K,n): # Vector to store respective elements # with their distance from integer K vd = [[] for i in range (n)] # Find the position of integer K for i in range (n): if (arr[i] = = K): pos = i break # Insert the elements with their # distance from K in vector i = pos - 1 j = pos + 1 # Element at distance 0 vd[ 0 ].append(arr[pos]) # Elements at left side of K while (i > = 0 ): vd[pos - i].append(arr[i]) i - = 1 # Elements at right side of K while (j < n): vd[j - pos].append(arr[j]) j + = 1 # Print the vector content in sorted order for i in range ( max (pos, n - pos - 1 ) + 1 ): # Sort elements at same distance vd[i].sort(reverse = False ) # Print elements at distance i from K for element in vd[i]: print (element,end = " " ) # Driver code if __name__ = = '__main__' : arr = [ 14 , 1101 , 10 , 35 , 0 ] K = 35 n = len (arr) distanceSort(arr, K, n) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation to Sort the integers in // array according to their distance from given // element K present in the array using System; using System.Collections.Generic; class GFG{ // Function to get sorted array based on // their distance from given integer K static void distanceSort( int []arr, int K, int n) { // List to store respective elements // with their distance from integer K List< int > []vd = new List< int >[n]; int i ; for (i = 0; i < n; i++) { vd[i] = new List< int >(); } // Find the position of integer K int pos = 0; for (i = 0; i < n; i++) { if (arr[i] == K) { pos = i; break ; } } // Insert the elements with their // distance from K in vector int j = pos + 1; i = pos - 1; // Element at distance 0 vd[0].Add(arr[pos]); // Elements at left side of K while (i >= 0) { vd[pos - i].Add(arr[i]); --i; } // Elements at right side of K while (j < n) { vd[j - pos].Add(arr[j]); ++j; } // Print the vector content in sorted order for (i = 0; i <= Math.Max(pos, n - pos - 1); ++i) { // Sort elements at same distance vd[i].Sort(); // Print elements at distance i from K for (j = 0; j < vd[i].Count; j++) { int element = ( int )vd[i][j]; Console.Write(element + " " ); } } } // Driver Code public static void Main(String []args) { int []arr = {14, 1101, 10, 35, 0}; int K = 35; int n = arr.Length; distanceSort(arr, K, n); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript implementation to Sort the integers in // array according to their distance from given // element K present in the array // Function to get sorted array based on // their distance from given integer K function distanceSort(arr, K, n) { // Vector to store respective elements // with their distance from integer K let vd = new Array(n); for (let i = 0; i < n; i++) { vd[i] = new Array(); } // Find the position of integer K for (let i = 0; i < n; i++) { if (arr[i] == K) { pos = i break } } // Insert the elements with their // distance from K in vector let i = pos - 1 let j = pos + 1 // Element at distance 0 vd[0].push(arr[pos]) // Elements at left side of K while (i >= 0){ vd[pos - i].push(arr[i]) i -= 1 } // Elements at right side of K while (j < n){ vd[j - pos].push(arr[j]) j += 1 } // Print the vector content in sorted order for (let i = 0;i< Math.max(pos, n - pos - 1) + 1;i++){ // Sort elements at same distance vd[i].sort() // Print elements at distance i from K for (let element of vd[i]) document.write(element, " " ) } } // Driver code let arr = [14, 1101, 10, 35, 0] let K = 35 let n = arr.length distanceSort(arr, K, n) // This code is contributed by Shinjanpatra </script> |
35 0 10 1101 14
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!