Queries to find minimum absolute difference between adjacent array elements in given ranges
Given an array arr[] consisting of N integers and an array query[] consisting of queries of the form {L, R}, the task for each query is to find the minimum of the absolute difference between adjacent elements over the range [L, R].
Examples:
Input: arr[] = {2, 6, 1, 8, 3, 4}, query[] = {{0, 3}, {1, 5}, {4, 5}}
Output:
4
1
1
Explanation:
Following are the values of queries performed:
- The minimum absolute difference between adjacent element over the range [0, 3] is min(|2 β 6|, |6 β 1|, |1 β 8|) = 4.
- The minimum absolute difference between adjacent element over the range [1, 5] is min(|6 β 1|, |1 β 8|, |8 β 3|, |3 β 4| ) = 1.
- The minimum absolute difference between adjacent element over the range [4, 5] is min(|3 β 4|) = 1.
Therefore, print 4, 1, 1 as the results of the given queries.
Input: arr[] = [10, 20, 1, 1, 5 ], query[] = [0, 1], [1, 4], [2, 3]
Output:
10
0
0
Naive Approach: The simplest approach to solve the given problem is to create an array diff[] that stores the absolute difference between adjacent elements for each array element. Now for each query, traverse the array diff[] over the range [L, R β 1] and print the value of minimum all the values in the range [L, R β 1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure for query range struct Query { int L, R; }; int MAX = 5000; // Function to find the minimum difference // between adjacent array element over the // given range [L, R] for Q Queries void minDifference( int arr[], int n, Query q[], int m) { // Find the sum of all queries for ( int i = 0; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; int ans = MAX; for ( int i = L; i < R; i++) { ans = min(ans, arr[i]); } // Print the sum of the // current query range cout << ans << '\n' ; } } // Function to find the minimum absolute // difference of adjacent array elements // for the given range void minimumDifference( int arr[], Query q[], int N, int m) { // Stores the absolute difference of // adjacent elements int diff[N]; for ( int i = 0; i < N - 1; i++) diff[i] = abs (arr[i] - arr[i + 1]); // Find the minimum difference of // adjacent elements minDifference(diff, N - 1, q, m); } // Driver Code int main() { int arr[] = { 2, 6, 1, 8, 3, 4 }; int N = sizeof (arr) / sizeof (arr[0]); Query Q[] = { { 0, 3 }, { 1, 5 }, { 4, 5 } }; int M = sizeof (Q) / sizeof (Q[0]); minimumDifference(arr, Q, N, M); return 0; } |
Java
// Java program for the above approach class GFG{ // Structure for query range static class Query { int L, R; public Query( int l, int r) { super (); L = l; R = r; } }; static int MAX = 5000 ; // Function to find the minimum difference // between adjacent array element over the // given range [L, R] for Q Queries static void minDifference( int arr[], int n, Query q[], int m) { // Find the sum of all queries for ( int i = 0 ; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; int ans = MAX; for ( int j = L; j < R; j++) { ans = Math.min(ans, arr[j]); } // Print the sum of the // current query range System.out.println(ans); } } // Function to find the minimum absolute // difference of adjacent array elements // for the given range static void minimumDifference( int arr[], Query q[], int N, int m) { // Stores the absolute difference of // adjacent elements int []diff = new int [N]; for ( int i = 0 ; i < N - 1 ; i++) diff[i] = Math.abs(arr[i] - arr[i + 1 ]); // Find the minimum difference of // adjacent elements minDifference(diff, N - 1 , q, m); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 6 , 1 , 8 , 3 , 4 }; int N = arr.length; Query Q[] = { new Query( 0 , 3 ), new Query( 1 , 5 ), new Query( 4 , 5 ) }; int M = Q.length; minimumDifference(arr, Q, N, M); } } // This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach MAX = 5000 ; # Function to find the minimum difference # between adjacent array element over the # given range [L, R] for Q Queries def minDifference(arr, n, q, m) : # Find the sum of all queries for i in range (m) : # Left and right boundaries # of current range L = q[i][ 0 ]; R = q[i][ 1 ]; ans = MAX ; for i in range (L, R) : ans = min (ans, arr[i]); # Print the sum of the # current query range print (ans); # Function to find the minimum absolute # difference of adjacent array elements # for the given range def minimumDifference(arr, q, N, m) : # Stores the absolute difference of # adjacent elements diff = [ 0 ] * N; for i in range (N - 1 ) : diff[i] = abs (arr[i] - arr[i + 1 ]); # Find the minimum difference of # adjacent elements minDifference(diff, N - 1 , q, m); # Driver Code if __name__ = = "__main__" : arr = [ 2 , 6 , 1 , 8 , 3 , 4 ]; N = len (arr); Q = [ [ 0 , 3 ], [ 1 , 5 ], [ 4 , 5 ] ]; M = len (Q); minimumDifference(arr, Q, N, M); # This code is contributed by AnkThon |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Structure for query range class Query { public int L, R; public Query( int l, int r) { this .L = l; this .R = r; } }; static int MAX = 5000; // Function to find the minimum difference // between adjacent array element over the // given range [L, R] for Q Queries static void minDifference( int []arr, int n, Query []q, int m) { // Find the sum of all queries for ( int i = 0; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; int ans = MAX; for ( int j = L; j < R; j++) { ans = Math.Min(ans, arr[j]); } // Print the sum of the // current query range Console.WriteLine(ans); } } // Function to find the minimum absolute // difference of adjacent array elements // for the given range static void minimumDifference( int []arr, Query []q, int N, int m) { // Stores the absolute difference of // adjacent elements int []diff = new int [N]; for ( int i = 0; i < N - 1; i++) diff[i] = Math.Abs(arr[i] - arr[i + 1]); // Find the minimum difference of // adjacent elements minDifference(diff, N - 1, q, m); } // Driver Code public static void Main() { int []arr = { 2, 6, 1, 8, 3, 4 }; int N = arr.Length; Query []Q = { new Query( 0, 3 ), new Query( 1, 5 ), new Query( 4, 5 ) }; int M = Q.Length; minimumDifference(arr, Q, N, M); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach; let MAX = 5000; // Function to find the minimum difference // between adjacent array element over the // given range [L, R] for Q Queries function minDifference(arr, n, q, m) { // Find the sum of all queries for (let i = 0; i < m; i++) { // Left and right boundaries // of current range let L = q[i][0], R = q[i][1]; let ans = MAX; for (let i = L; i < R; i++) { ans = Math.min(ans, arr[i]); } // Print the sum of the // current query range document.write(ans+ '<br>' ); } } // Function to find the minimum absolute // difference of adjacent array elements // for the given range function minimumDifference(arr, q, N, m) { // Stores the absolute difference of // adjacent elements let diff = new Array(N); for (let i = 0; i < N - 1; i++) diff[i] = Math.abs(arr[i] - arr[i + 1]); // Find the minimum difference of // adjacent elements minDifference(diff, N - 1, q, m); } // Driver Code let arr = [2, 6, 1, 8, 3, 4]; let N = arr.length; let Q = [[0, 3], [1, 5], [4, 5]]; let M = Q.length; minimumDifference(arr, Q, N, M); //This code is contributed by Potta Lokesh </script> |
4 1 1
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by using the Sparse Table that supports query in constant time O(1) with extra space O(N log N). Instead of passing original arr[] pass diff[] to get the required answer. Follow the steps below to solve the problem:
- Initialize a global array lookup[][] for the sparse array.
- Define a function preprocess(arr, N) and perform the following operations:
- Iterate over the range [0, N) using the variable i and set the value of lookup[i][0] as i.
- Iterate over the range [1, N) using the variable j and i nestedly and if arr[lookup[i][j-1]] is less than arr[lookup[i + (1 << (j-1))][j-1], then set lookup[i][j] as lookup[i][j-1], otherwise set lookup[i][j] as lookup[i + (1 << (j β 1))][j β 1].
- Define a function query(int arr[], int L, int M) and perform the following operations:
- Initialize the variable j as (int)log2(R β L + 1).
- If arr[lookup[L][j]] is less than equal to arr[lookup[R β (1 << j) + 1][j]], then return arr[lookup[L][j]], else return arr[lookup[R β (1 << j) + 1][j]].
- Define a function Min_difference(arr, n, q, m) and perform the following operations:
- Call the function preprocess(arr, n) to preprocess the sparse array.
- Traverse the given array of queries Q[] and the value returned by the function query(arr, L, R β 1) gives the result for the current query.
- Initialize an array diff[] of size N and store the absolute differences of arr[i]-arr[i+1] for every value of i.
- Call the function Min_difference(diff, N-1, q, m) to find the minimum absolute difference for each query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAX 500 // Stores the index for the minimum // value in the subarray arr[i, j] int lookup[MAX][MAX]; // Structure for query range struct Query { int L, R; }; // Function to fill the lookup array // lookup[][] in the bottom up manner void preprocess( int arr[], int n) { // Initialize M for the intervals // with length 1 for ( int i = 0; i < n; i++) lookup[i][0] = i; // Find the values from smaller // to bigger intervals for ( int j = 1; (1 << j) <= n; j++) { // Compute minimum value for // all intervals with size 2^j for ( int i = 0; (i + (1 << j) - 1) < n; i++) { // For arr[2][10], compare // arr[lookup[0][3]] and // arr[lookup[3][3]] if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]]) lookup[i][j] = lookup[i][j - 1]; // Otherwise else lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]; } } } // Function find minimum of absolute // difference of all adjacent element // in subarray arr[L..R] int query( int arr[], int L, int R) { // For [2, 10], j = 3 int j = ( int )log2(R - L + 1); // For [2, 10], compare arr[lookup[0][3]] // and arr[lookup[3][3]], if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]]) return arr[lookup[L][j]]; else return arr[lookup[R - (1 << j) + 1][j]]; } // Function to find the minimum of the // ranges for M queries void Min_difference( int arr[], int n, Query q[], int m) { // Fills table lookup[n][Log n] preprocess(arr, n); // Compute sum of all queries for ( int i = 0; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; // Print sum of current query range cout << query(arr, L, R - 1) << '\n' ; } } // Function to find the minimum absolute // difference in a range void minimumDifference( int arr[], Query q[], int N, int m) { // diff[] is to stores the absolute // difference of adjacent elements int diff[N]; for ( int i = 0; i < N - 1; i++) diff[i] = abs (arr[i] - arr[i + 1]); // Call Min_difference to get minimum // difference of adjacent elements Min_difference(diff, N - 1, q, m); } // Driver Code int main() { int arr[] = { 2, 6, 1, 8, 3, 4 }; int N = sizeof (arr) / sizeof (arr[0]); Query Q[] = { { 0, 3 }, { 1, 5 }, { 4, 5 } }; int M = sizeof (Q) / sizeof (Q[0]); minimumDifference(arr, Q, N, M); return 0; } |
Java
// Java program for the above approach import java.util.*; import javax.management.Query; class GFG{ static final int MAX = 500 ; // Stores the index for the minimum // value in the subarray arr[i, j] static int [][]lookup = new int [MAX][MAX]; // Structure for query range static class Query { int L, R; public Query( int l, int r) { super (); L = l; R = r; } }; // Function to fill the lookup array // lookup[][] in the bottom up manner static void preprocess( int arr[], int n) { // Initialize M for the intervals // with length 1 for ( int i = 0 ; i < n; i++) lookup[i][ 0 ] = i; // Find the values from smaller // to bigger intervals for ( int j = 1 ; ( 1 << j) <= n; j++) { // Compute minimum value for // all intervals with size 2^j for ( int i = 0 ; (i + ( 1 << j) - 1 ) < n; i++) { // For arr[2][10], compare // arr[lookup[0][3]] and // arr[lookup[3][3]] if (arr[lookup[i][j - 1 ]] < arr[lookup[i + ( 1 << (j - 1 ))][j - 1 ]]) lookup[i][j] = lookup[i][j - 1 ]; // Otherwise else lookup[i][j] = lookup[i + ( 1 << (j - 1 ))][j - 1 ]; } } } // Function find minimum of absolute // difference of all adjacent element // in subarray arr[L..R] static int query( int arr[], int L, int R) { // For [2, 10], j = 3 int j = ( int )Math.log(R - L + 1 ); // For [2, 10], compare arr[lookup[0][3]] // and arr[lookup[3][3]], if (arr[lookup[L][j]] <= arr[lookup[R - ( 1 << j) + 1 ][j]]) return arr[lookup[L][j]]; else return arr[lookup[R - ( 1 << j) + 1 ][j]]; } // Function to find the minimum of the // ranges for M queries static void Min_difference( int arr[], int n, Query q[], int m) { // Fills table lookup[n][Log n] preprocess(arr, n); // Compute sum of all queries for ( int i = 0 ; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; // Print sum of current query range System.out.println(query(arr, L, R - 1 )); } } // Function to find the minimum absolute // difference in a range static void minimumDifference( int arr[], Query q[], int N, int m) { // diff[] is to stores the absolute // difference of adjacent elements int []diff = new int [N]; for ( int i = 0 ; i < N - 1 ; i++) diff[i] = Math.abs(arr[i] - arr[i + 1 ]); // Call Min_difference to get minimum // difference of adjacent elements Min_difference(diff, N - 1 , q, m); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 6 , 1 , 8 , 3 , 4 }; int N = arr.length; Query Q[] = { new Query( 0 , 3 ), new Query( 1 , 5 ), new Query( 4 , 5 ) }; int M = Q.length; minimumDifference(arr, Q, N, M); } } // This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach: import math MAX = 500 ## Structure for query range class Query: def __init__( self , l, r): self .L = l self .R = r ## Function to fill the lookup array ## lookup[][] in the bottom up manner def preprocess(arr, n): ## Initialize M for the intervals ## with length 1 for i in range (n): lookup[i][ 0 ] = i; ## Find the values from smaller ## to bigger intervals j = 1 while True : if ( 1 << j) > n: break ## Compute minimum value for ## all intervals with size 2^j for i in range (n + 1 - ( 1 << j)): ## For arr[2][10], compare ## arr[lookup[0][3]] and ## arr[lookup[3][3]] if (arr[lookup[i][j - 1 ]] < arr[lookup[i + ( 1 << (j - 1 ))][j - 1 ]]): lookup[i][j] = lookup[i][j - 1 ]; ## Otherwise else : lookup[i][j] = lookup[i + ( 1 << (j - 1 ))][j - 1 ] j + = 1 ## Function find minimum of absolute ## difference of all adjacent element ## in subarray arr[L..R] def query(arr, L, R): ## For [2, 10], j = 3 j = int (math.log2(R - L + 1 )) ## For [2, 10], compare arr[lookup[0][3]] ## and arr[lookup[3][3]], if (arr[lookup[L][j]] < = arr[lookup[R - ( 1 << j) + 1 ][j]]): return arr[lookup[L][j]] else : return arr[lookup[R - ( 1 << j) + 1 ][j]] ## Function to find the minimum of the ## ranges for M queries def Min_difference(arr, n, q, m): ## Fills table lookup[n][Log n] preprocess(arr, n) ## Compute sum of all queries for i in range ( 0 , m): ## Left and right boundaries ## of current range L = q[i].L R = q[i].R; ## Print sum of current query range print (query(arr, L, R - 1 )) ## Function to find the minimum absolute ## difference in a range def minimumDifference(arr, q, N, m): ## diff[] is to stores the absolute ## difference of adjacent elements diff = []; for i in range (N): diff.append( 0 ) for i in range ( 0 , N - 1 ): diff[i] = abs (arr[i] - arr[i + 1 ]); ## Call Min_difference to get minimum ## difference of adjacent elements Min_difference(diff, N - 1 , q, m) ## Driver code if __name__ = = '__main__' : arr = [ 2 , 6 , 1 , 8 , 3 , 4 ] N = len (arr) Q = [ Query( 0 , 3 ), Query( 1 , 5 ), Query( 4 , 5 ) ] M = len (Q) ## Stores the index for the minimum ## value in the subarray arr[i, j] global lookup lookup = [] for i in range ( 0 , MAX ): lookup.append([]) for j in range ( 0 , MAX ): lookup[i].append( 0 ) minimumDifference(arr, Q, N, M) # This code is contributed by subhamgoyal2014. |
C#
// C# program for the above approach using System; public class GFG{ static readonly int MAX = 500; // Stores the index for the minimum // value in the subarray arr[i, j] static int [,]lookup = new int [MAX, MAX]; // Structure for query range class Query { public int L, R; public Query( int l, int r) { L = l; R = r; } }; // Function to fill the lookup array // lookup[,] in the bottom up manner static void preprocess( int []arr, int n) { // Initialize M for the intervals // with length 1 for ( int i = 0; i < n; i++) lookup[i,0] = i; // Find the values from smaller // to bigger intervals for ( int j = 1; (1 << j) <= n; j++) { // Compute minimum value for // all intervals with size 2^j for ( int i = 0; (i + (1 << j) - 1) < n; i++) { // For arr[2,10], compare // arr[lookup[0,3]] and // arr[lookup[3,3]] if (arr[lookup[i,j - 1]] < arr[lookup[i + (1 << (j - 1)),j - 1]]) lookup[i,j] = lookup[i,j - 1]; // Otherwise else lookup[i,j] = lookup[i + (1 << (j - 1)),j - 1]; } } } // Function find minimum of absolute // difference of all adjacent element // in subarray arr[L..R] static int query( int []arr, int L, int R) { // For [2, 10], j = 3 int j = ( int )Math.Log(R - L + 1); // For [2, 10], compare arr[lookup[0,3]] // and arr[lookup[3,3]], if (arr[lookup[L,j]] <= arr[lookup[R - (1 << j) + 1,j]]) return arr[lookup[L,j]]; else return arr[lookup[R - (1 << j) + 1,j]]; } // Function to find the minimum of the // ranges for M queries static void Min_difference( int []arr, int n, Query []q, int m) { // Fills table lookup[n,Log n] preprocess(arr, n); // Compute sum of all queries for ( int i = 0; i < m; i++) { // Left and right boundaries // of current range int L = q[i].L, R = q[i].R; // Print sum of current query range Console.WriteLine(query(arr, L, R - 1)); } } // Function to find the minimum absolute // difference in a range static void minimumDifference( int []arr, Query []q, int N, int m) { // diff[] is to stores the absolute // difference of adjacent elements int []diff = new int [N]; for ( int i = 0; i < N - 1; i++) diff[i] = Math.Abs(arr[i] - arr[i + 1]); // Call Min_difference to get minimum // difference of adjacent elements Min_difference(diff, N - 1, q, m); } // Driver Code public static void Main(String[] args) { int []arr = { 2, 6, 1, 8, 3, 4 }; int N = arr.Length; Query []Q = { new Query( 0, 3 ), new Query( 1, 5 ), new Query( 4, 5 ) }; int M = Q.Length; minimumDifference(arr, Q, N, M); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach let MAX = 500; // Stores the index for the minimum // value in the subarray arr[i, j] let lookup = new Array(MAX).fill(0).map(() => new Array(MAX).fill(0)); // Structure for query range class Query { constructor(l, r) { this .L = l; this .R = r; } } // Function to fill the lookup array // lookup[][] in the bottom up manner function preprocess(arr, n) { // Initialize M for the intervals // with length 1 for (let i = 0; i < n; i++) lookup[i][0] = i; // Find the values from smaller // to bigger intervals for (let j = 1; 1 << j <= n; j++) { // Compute minimum value for // all intervals with size 2^j for (let i = 0; i + (1 << j) - 1 < n; i++) { // For arr[2][10], compare // arr[lookup[0][3]] and // arr[lookup[3][3]] if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]]) lookup[i][j] = lookup[i][j - 1]; // Otherwise else lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]; } } } // Function find minimum of absolute // difference of all adjacent element // in subarray arr[L..R] function query(arr, L, R) { // For [2, 10], j = 3 let j = Math.floor(Math.log(R - L + 1)); // For [2, 10], compare arr[lookup[0][3]] // and arr[lookup[3][3]], if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]]) return arr[lookup[L][j]]; else return arr[lookup[R - (1 << j) + 1][j]]; } // Function to find the minimum of the // ranges for M queries function Min_difference(arr, n, q, m) { // Fills table lookup[n][Log n] preprocess(arr, n); // Compute sum of all queries for (let i = 0; i < m; i++) { // Left and right boundaries // of current range let L = q[i].L, R = q[i].R; // let sum of current query range document.write(query(arr, L, R - 1) + "<br>" ); } } // Function to find the minimum absolute // difference in a range function minimumDifference(arr, q, N, m) { // diff[] is to stores the absolute // difference of adjacent elements let diff = new Array(N); for (let i = 0; i < N - 1; i++) diff[i] = Math.abs(arr[i] - arr[i + 1]); // Call Min_difference to get minimum // difference of adjacent elements Min_difference(diff, N - 1, q, m); } // Driver Code let arr = [2, 6, 1, 8, 3, 4]; let N = arr.length; let Q = [ new Query(0, 3), new Query(1, 5), new Query(4, 5)]; let M = Q.length; minimumDifference(arr, Q, N, M); // This code is contributed by _saurabh_jaiswal. </script> |
4 1 1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N*N)