Given an array arr[] of N unique elements and Q queries. Every query consists of two integers L and R. The task is to print the absolute difference between the indices of the Lth smallest and the Rth smallest element.
Examples:
Input: arr[] = {1, 5, 4, 2, 8, 6, 7},
que[] = {{2, 5}, {1, 3}, {1, 5}, {3, 6}}
Output:
2
2
5
4
For the first query the second smallest number is 2, which is at index 3
and the 5th smallest number is 6 which is at index 5. Hence the
absolute difference between both such index is 2.Input: arr[] = {1, 2, 3, 4},
que[] = {{1, 1}, {2, 3}}
Output:
0
1
Approach: The following steps can be followed to solve the above problem.
- Store the elements and their indices in an array of pairs.
- Sort the array according to the first element.
- For every query the answer will be abs(arr[l – 1].second – arr[r – 1].second)
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the result// for a particular queryint answerQuery(pair<int, int> arr[], int l, int r){ // Get the difference between the indices of // L-th and the R-th smallest element int answer = abs(arr[l - 1].second - arr[r - 1].second); // Return the answer return answer;}// Function that performs all the queriesvoid solveQueries(int a[], int n, int q[][2], int m){ // Store the array numbers // and their indices pair<int, int> arr[n]; for (int i = 0; i < n; i++) { arr[i].first = a[i]; arr[i].second = i; } // Sort the array elements sort(arr, arr + n); // Answer all the queries for (int i = 0; i < m; i++) cout << answerQuery(arr, q[i][0], q[i][1]) << endl;}// Driver codeint main(){ int a[] = { 1, 5, 4, 2, 8, 6, 7 }; int n = sizeof(a) / sizeof(a[0]); int q[][2] = { { 2, 5 }, { 1, 3 }, { 1, 5 }, { 3, 6 } }; int m = sizeof(q) / sizeof(q[0]); solveQueries(a, n, q, m); return 0;} |
Java
// Java implementation of the approach import java.util.*;import java.util.Comparator;public class GFG{ // pair classstatic class pair{ int first,second; pair(int f, int s) { first = f; second = s; }}// Function to return the result // for a particular query static int answerQuery(pair arr[], int l, int r) { // Get the difference between the indices of // L-th and the R-th smallest element int answer = Math.abs(arr[l - 1].second - arr[r - 1].second); // Return the answer return answer; } // Function that performs all the queries static void solveQueries(int a[], int n, int q[][], int m) { // Store the array numbers // and their indices pair arr[] = new pair[n]; for (int i = 0; i < n; i++) { arr[i] = new pair(0, 0); arr[i].first = a[i]; arr[i].second = i; } // Sort pair Comparator<pair> comp = new Comparator<pair>() { public int compare(pair e1, pair e2) { if(e1.first < e2.first) { return -1; } else if (e1.first > e2.first) { return 1; } else { return 0; } } }; // Sort the array elements Arrays.sort(arr,comp); // Answer all the queries for (int i = 0; i < m; i++) System.out.println( answerQuery(arr, q[i][0], q[i][1])); } // Driver code public static void main(String args[]){ int a[] = { 1, 5, 4, 2, 8, 6, 7 }; int n = a.length; int q[][] = { { 2, 5 }, { 1, 3 }, { 1, 5 }, { 3, 6 } }; int m = q.length; solveQueries(a, n, q, m); } }// This code is contributed by Arnab Kundu |
Python3
# Python 3 implementation of the approach# Function to return the result# for a particular querydef answerQuery(arr, l, r): # Get the difference between the indices # of L-th and the R-th smallest element answer = abs(arr[l - 1][1] - arr[r - 1][1]) # Return the answer return answer# Function that performs all the queriesdef solveQueries(a, n, q, m): # Store the array numbers # and their indices arr = [[0 for i in range(n)] for j in range(n)] for i in range(n): arr[i][0] = a[i] arr[i][1] = i # Sort the array elements arr.sort(reverse = False) # Answer all the queries for i in range(m): print(answerQuery(arr, q[i][0], q[i][1]))# Driver codeif __name__ == '__main__': a = [1, 5, 4, 2, 8, 6, 7] n = len(a) q = [[2, 5], [1, 3], [1, 5], [3, 6]] m = len(q) solveQueries(a, n, q, m)# This code is contributed by# Surendra_Gangwar |
Javascript
<script>// JavaScript implementation of the approach// Function to return the result// for a particular queryfunction answerQuery(arr, l, r){ // Get the difference between the indices of // L-th and the R-th smallest element let answer = Math.abs(arr[l - 1][1] - arr[r - 1][1]); // Return the answer return answer;}// Function that performs all the queriesfunction solveQueries(a, n, q, m){ // Store the array numbers // and their indices let arr = new Array(n); for(let i = 0; i < n; i++){ arr[i] = new Array(n).fill(0) } for (let i = 0; i < n; i++) { arr[i][0] = a[i]; arr[i][1] = i; } // Sort the array elements arr.sort((a, b) => a[0] - b[0]); // Answer all the queries for (let i = 0; i < m; i++) document.write(answerQuery(arr, q[i][0], q[i][1]) + "<br>");}// Driver code let a = [ 1, 5, 4, 2, 8, 6, 7 ]; let n = a.length; let q = [ [ 2, 5 ], [ 1, 3 ], [ 1, 5 ], [ 3, 6 ] ]; let m = q.length; solveQueries(a, n, q, m);// This code is contributed by _saurabh_jaiswal</script> |
C#
using System;using System.Linq;class GFG{ // pair class private class Pair { public int first; public int second; public Pair(int f, int s) { first = f; second = s; } } // Function to return the result // for a particular query private static int answerQuery(Pair[] arr, int l, int r) { // Get the difference between the indices of // L-th and the R-th smallest element int answer = Math.Abs(arr[l - 1].second - arr[r - 1].second); // Return the answer return answer; } // Function that performs all the queries private static void solveQueries(int[] a, int n, int[][] q, int m) { // Store the array numbers // and their indices Pair[] arr = new Pair[n]; for (int i = 0; i < n; i++) { arr[i] = new Pair(0, 0); arr[i].first = a[i]; arr[i].second = i; } // Sort pair Array.Sort(arr, (e1, e2) => { if (e1.first < e2.first) { return -1; } else if (e1.first > e2.first) { return 1; } else { return 0; } }); // Answer all the queries for (int i = 0; i < m; i++) Console.WriteLine(answerQuery(arr, q[i][0], q[i][1])); } // Driver code public static void Main(string[] args) { int[] a = { 1, 5, 4, 2, 8, 6, 7 }; int n = a.Length; int[][] q = { new int[] { 2, 5 }, new int[] { 1, 3 }, new int[] { 1, 5 }, new int[] { 3, 6 } }; int m = q.Length; solveQueries(a, n, q, m); }} |
Output:
2 2 5 4
Time Complexity: O(N*logN), as we are using an inbuilt sort function to sort an array of size N. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the array arr of size N. Where N is the number of elements in the 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
