Given a sorted 2D array arr[][2] of size N such that (arr[i][0], arr[i][1]) represents the coordinates of ith point in the cartesian plane and an integer K, the task is to find the maximum value of the expression (|arr[i][0] – arr[j][0]| + arr[i][1] + arr[j][1]) such that |arr[i][0] – arr[j][0]| ? K for any possible pair of coordinates (i, j).
Examples:
Input: arr[][] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Output: 4
Explanation:
Choose pairs (0, 1). Now the value of the expression is given by:
value = (abs(1 – 2) + 3 + 0) = 4, which is maximum and abs(1 – 2) = 1(? K).
Therefore, print 4.Input: arr[][] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Output: 3
Approach: The given problem can be solved using a Greedy Algorithm using the priority queue which is based on the following observations:
- Rearranging the expression for all i > j as (arr[i][0] – arr[i][1] + arr[j][0] + arr[j][1]).
- Now, keeping the pair of {arr[i]x – arr[i]y, arr[i]x} in sorted order, the value of the given expression for every array element at index j can be calculated.
Follow the steps below to solve the problem:
- Initialize a priority_queue of pairs say PQ that stores the pair of differences of coordinated axes of a point and X coordinate of that point.
- Initialize a variable say res as INT_MIN to store the maximum value.
- Traverse the array arr[][] and considering {X, Y} is the current point perform the following operations:
- Iterate while PQ is not empty and (X – PQ.top()[1]) is greater than K and remove the top element from the priority_queue PQ.
- If PQ is not empty then update the value of res as the maximum of res and PQ.top()[0] + X + Y).
- Push the pair {Y – X, X} into the priority_queue PQ.
- After completing the above steps, print the value of res as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum value// of the given expression possible// for any pair of co-ordinatesvoid findMaxValueOfEquation( vector<vector<int> >& arr, int K){ // Stores the differences between pairs priority_queue<vector<int> > pq; // Stores the maximum value int res = INT_MIN; // Traverse the array arr[][] for (auto point : arr) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (!pq.empty() && point[0] - pq.top()[1] > K) { // Removes the top element pq.pop(); } // If pq is not empty if (!pq.empty()) { // Update the value res res = max(res, pq.top()[0] + point[0] + point[1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.push({ point[1] - point[0], point[0] }); } // Print the result cout << res;}// Driver Codeint main(){ vector<vector<int> > arr = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; findMaxValueOfEquation(arr, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to find the maximum value // of the given expression possible // for any pair of co-ordinates static void findMaxValueOfEquation(int arr[][], int K) { // Stores the differences between pairs PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> { if (a[0] != b[0]) return b[0] - a[0]; return b[1] - a[1]; }); // Stores the maximum value int res = Integer.MIN_VALUE; // Traverse the array arr[][] for (int point[] : arr) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (!pq.isEmpty() && point[0] - pq.peek()[1] > K) { // Removes the top element pq.poll(); } // If pq is not empty if (!pq.isEmpty()) { // Update the value res res = Math.max(res, pq.peek()[0] + point[0] + point[1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.add(new int[] { point[1] - point[0], point[0] }); } // Print the result System.out.println(res); } // Driver Code public static void main(String[] args) { int[][] arr = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; findMaxValueOfEquation(arr, K); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to find the maximum value# of the given expression possible# for any pair of co-ordinatesdef findMaxValueOfEquation(arr, K): # Stores the differences between pairs pq = [] # Stores the maximum value res = -10**8 # Traverse the array arr[][] for point in arr: # While pq is not empty and # difference between point[0] # and pq.top()[1] > K while (len(pq)>0 and point[0] - pq[-1][1] > K): # Removes the top element del pq[-1] # If pq is not empty if (len(pq) > 0): # Update the value res res = max(res, pq[-1][0] + point[0] + point[1]) # Push pair {point[1] - point[0], # point[0]} in pq pq.append([point[1] - point[0], point[0]]) pq = sorted(pq) # Print the result print (res)# Driver Codeif __name__ == '__main__': arr = [ [ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ] ] K = 1 findMaxValueOfEquation(arr, K)# This code is contributed by mohit kumar 29. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class Program { static void FindMaxValueOfEquation(int[][] arr, int K) { // Stores the differences between pairs var pq = new SortedSet<int[]>( Comparer<int[]>.Create((a, b) => { if (a[0] != b[0]) { return b[0] - a[0]; } return b[1] - a[1]; })); // Stores the maximum value int res = int.MinValue; // Traverse the array arr[][] foreach(int[] point in arr) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (pq.Count > 0 && point[0] - pq.Min[1] > K) { // Removes the top element pq.Remove(pq.Min); } // If pq is not empty if (pq.Count > 0) { // Update the value res res = Math.Max(res, pq.Min[0] + point[0] + point[1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.Add(new int[] { point[1] - point[0], point[0] }); } // Print the result Console.WriteLine(res); } static void Main(string[] args) { int[][] arr = { new int[] { 1, 3 }, new int[] { 2, 0 }, new int[] { 5, 10 }, new int[] { 6, -10 } }; int K = 1; FindMaxValueOfEquation(arr, K); }}// This code is contributed by phasing17 |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum value // of the given expression possible // for any pair of co-ordinatesfunction findMaxValueOfEquation(arr,K){ // Stores the differences between pairs let pq=[]; // Stores the maximum value let res = Number.MIN_VALUE; // Traverse the array arr[][] for (let point=0;point< arr.length;point++) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (pq.length!=0 && arr[point][0] - pq[0][1] > K) { // Removes the top element pq.shift(); } // If pq is not empty if (pq.length!=0) { // Update the value res res = Math.max(res, pq[0][0] + arr[point][0] + arr[point][1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.push([ arr[point][1] - arr[point][0], arr[point][0] ]); pq.sort(function(a,b){ if (a[0] != b[0]) return b[0] - a[0]; return b[1] - a[1];}) } // Print the result document.write(res);}// Driver Codelet arr = [[ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ]];let K = 1;findMaxValueOfEquation(arr, K);// This code is contributed by unknown2108</script> |
Output:
4
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
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!
