Given an array arr[] of size N where arr[i] is in the form [xi, yi] denoting a point (xi, yi) on a 2D plane. The array is sorted on x-coordinates. Also, an integer K is given. The task is to minimize the value of the equation yi + yj + |xi – xj| where |xi – xj| ≤ K and 1 ≤ i < j ≤ N. It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi – xj| ≤ K.
Examples:
Input: arr[4] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Output: 1
Explanation: The first two points satisfies the given condition |xi – xj| ≤ 1.
Now, the equation = 3 + 0 + |1 – 2| = 4.
Similarly, Third and fourth points also satisfy the condition and
give a value of 10 + -10 + |5 – 6| = 1.
Except these 2 pairs no other points satisfy the given condition.
Minimum of 4 and 1 is 1. So output is 1.Input: arr[4] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3.
It gives the value of 0 + 0 + |0 – 3| = 3.
Approach: The problem reduces to find the minimum value of (yj + xj) + (yi – xi). Since the absolute difference of the x coordinates of the points considered must be less than or equal to K so the problem can be solved using a minimum heap. For each and every point consider the top value of the heap and check if the x coordinate of the top and the current point is less than K, take minimum among those and update the heap and follow the same for the rest of the coordinates. Follow the steps below to solve this problem:
- Initialize the minimum priority queue minh[].
- Initialize the variable min_val as INT_MAX.
- Iterate over the range [0, n) using the variable index and perform the following tasks:
- Pop the elements from the min-heap minh[] until the difference in x-coordinates is greater than K.
- If the heap is not empty, then update the value of min_val.
- Push the value of {arr[index][1] – arr[index][0], arr[index][0]}.
- After performing the above steps, print the value of min_val as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pi;// Utility function to find minimum// value of equationint MinimumValue(int arr[][2], int n, int k){ // Minimum heap for storing // (x-y) difference and x // coordinate as the pair priority_queue<pi, vector<pi>, greater<pi> > minh; int min_val = INT_MAX; for (int index = 0; index < n; index++) { // Pop until the x-coordinates // difference is greater than K while (( !minh.empty() && ((arr[index][0] - minh.top().second) > k))) { minh.pop(); } // If not heap empty update min_val if (!minh.empty()) { min_val = min(min_val, arr[index][0] + arr[index][1] + minh.top().first); } // Push the current pair in the heap minh.push({ arr[index][1] - arr[index][0], arr[index][0] }); } return min_val;}// Driver Codeint main(){ // Input taken int arr[4][2] = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; int n = 4; // Function called cout << MinimumValue(arr, n, K) << "\n"; return 0;} |
Java
// Java program for the above approachimport java.util.PriorityQueue;public class GFG { // Utility function to find minimum // value of equation static int MinimumValue(int[][] arr, int n, int k) { // Minimum heap for storing // (x-y) difference and x // coordinate as the pair PriorityQueue<int[]> minh = new PriorityQueue<int[]>((a, b) -> { if (a[0] == b[0]) return a[1] - b[1]; return a[0] - b[0]; }); int min_val = Integer.MAX_VALUE; for (int index = 0; index < n; index++) { // Pop until the x-coordinates // difference is greater than K while (!minh.isEmpty()) { int[] pi = minh.poll(); if ((arr[index][0] - (-1 * pi[1])) <= k) { minh.add(pi); break; } } // If not heap empty update min_val if (!minh.isEmpty()) { int[] pi = minh.poll(); min_val = Math.min( min_val, arr[index][0] + arr[index][1] + (-1 * pi[1])); minh.add(pi); } // Push the current pair in the heap minh.add(new int[] { -1 * arr[index][1] - (-1 * arr[index][0]), -1 * arr[index][0] }); } return min_val; } // Driver code public static void main(String[] args) { // Input taken int[][] arr = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; int n = 4; // Function called System.out.println(MinimumValue(arr, n, K)); }}// This code is contributed by Lovely Jain |
Python3
# python3 program for the above approachfrom queue import PriorityQueueINT_MAX = 2147483647# Utility function to find minimum# value of equationdef MinimumValue(arr, n, k): # Minimum heap for storing # (x-y) difference and x # coordinate as the pair minh = PriorityQueue() min_val = INT_MAX for index in range(0, n): # Pop until the x-coordinates # difference is greater than K while (not minh.empty()): pi = minh.get() if((arr[index][0] - (-1*pi[1])) <= k): minh.put(pi) break # If not heap empty update min_val if (not minh.empty()): pi = minh.get() min_val = min(min_val, arr[index][0] + arr[index][1] + (-1*pi[1])) minh.put(pi) # Push the current pair in the heap minh.put([-1*arr[index][1] - (-1*arr[index][0]), -1*arr[index][0]]) return min_val# Driver Codeif __name__ == "__main__": # Input taken arr = [[1, 3], [2, 0], [5, 10], [6, -10]] K = 1 n = 4 # Function called print(MinimumValue(arr, n, K)) # This code is contributed by rakeshsahni |
Javascript
// JavaScript program for the above approachconst INT_MAX = 1000000009;function MinimumValue(arr, n, k) { let minh = []; let min_val = INT_MAX; for (let index = 0; index < n; index++) { while (minh.length > 0) { let pi = minh.shift(); if ((arr[index][0] - (-1 * pi[1])) <= k) { minh.unshift(pi); break; } } if (minh.length > 0) { let pi = minh.shift(); min_val = Math.min(min_val, arr[index][0] + arr[index][1] + (-1 * pi[1])); minh.unshift(pi); } minh.push([-1 * arr[index][1] - (-1 * arr[index][0]), -1 * arr[index][0]]); minh.sort((a, b) => a[0] - b[0]); } return min_val;}//Driver Codelet arr = [[1, 3], [2, 0], [5, 10], [6, -10]];let K = 1;let n = 4;console.log(MinimumValue(arr,k,n))//This code is contributed by Shivam Tiwari |
C#
using System;using System.Collections.Generic;public class GFG { // Utility function to find minimum value of equation static int MinimumValue(int[, ] arr, int n, int k) { // Minimum heap for storing (x-y) difference and x // coordinate as the pair A min heap is used to keep // track of the minimum values of (x - y) and x var minh = new SortedSet<Tuple<int, int> >( (x, y) = > x.Item1.CompareTo(y.Item1)); int min_val = int.MaxValue; for (int index = 0; index < n; index++) { while (minh.Count > 0 && arr[index, 0] - minh.Min.Item2 > k) { minh.Remove(minh.Min); } if (minh.Count > 0) { min_val = Math.Min( min_val, arr[index, 0] + arr[index, 1] + minh.Min.Item1); } minh.Add( Tuple.Create(arr[index, 1] - arr[index, 0], arr[index, 0])); } return min_val; } static void Main(string[] args) { // Input taken int[, ] arr = new int[, ] { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; int n = 4; // Function call Console.WriteLine(MinimumValue(arr, n, K)); }}// This code is contributed by Shivam Tiwari |
1
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
