Queries to add, remove and return the difference of maximum and minimum.
Given Q queries. The queries are of three types and are described below:
- Add the number num to the list.
- Remove the number num from the list.
- Return the difference between the maximum and minimum number in the list.
The task is to write a program the performs the above queries.
Note: The numbers are distinct and at every call of query-3, there will be a minimum of 1 element in the list.
Examples:
Input:
Q = 5
Query of type 1: num = 3
Query of type 1: num = 5
Query of type 1: num = 6
Query of type 2: num = 6
Query of type 1: num = 2
Query of type 3:Output: 4
Since query of type 3 has been called once only, the answer at the instant is 4.
After first query of type-1, the list is {3}
After second query of type-1, the list is {3, 5}
After third query of type-1, the list is {3, 5, 6}
After fourth query of type-2, the list is {3, 5}
After fifth query of type-1, the list is {2, 3, 5}
On sixth query of type-3, the answer is 5-2.
A simple solution is to follow the below steps:
- store the numbers in an array of vectors.
- For the query of type-1 add an element to the array.
- For a query of type-2 remove the element from the vector or array.
- For the query of type-3, traverse the array and find the minimum and maximum in the array and return the difference of them.
Time Complexity:
- Type-1 query: O(1) as insertion of an element will cost O(1) time.
- Type-2 query: O(N) as in worst case we would need to traverse the whole array to search and remove the element.
- Type-3 query: O(N) as we need to traverse the array to find minimum and maximum element.
Auxiliary Space: O(N), as we need to use extra space for array.
An efficient solution is to use a self-balancing binary search tree (Implemented as set container in C++ or TreeSet in Java). The below steps are followed to solve the above problem.
Below is the implementation of the efficient approach:
C++
// C++ program to perform Queries to // add, remove and return // the difference of maximum and minimum. #include <bits/stdc++.h> using namespace std; set< int > s; // function to perform query 1 void performQueryOne( int num) { // insert the element s.insert(num); } // function to perform query 2 void performQueryTwo( int num) { // erase the element s.erase(num); } // function to perform query 3 int performQueryThree() { int mini = *(s.begin()); int maxi = *(s.rbegin()); return maxi - mini; } // Driver Code int main() { // query type-1 int num = 3; performQueryOne(num); // query type-1 num = 5; performQueryOne(num); // query type-1 num = 6; performQueryOne(num); // query type-2 num = 5; performQueryTwo(num); // query type-1 num = 2; performQueryOne(num); // query type-3 cout << performQueryThree(); return 0; } |
Java
// Java program to perform Queries // to add, remove and return // the difference of maximum and // minimum using TreeSet. import java.util.*; class GFG { static SortedSet<Integer> t = new TreeSet<Integer>(); // function to perform query 1 static void performQueryOne( int num) { // insert the element t.add(num); } // function to perform query 2 static void performQueryTwo( int num) { // erase the element t.remove(num); } // function to perform query 3 static int performQueryThree() { int mini = t.first(); int maxi = t.last(); return maxi - mini; } // Driver Code public static void main(String[] args) { // query type-1 int num = 3 ; performQueryOne(num); // query type-1 num = 5 ; performQueryOne(num); // query type-1 num = 6 ; performQueryOne(num); // query type-2 num = 5 ; performQueryTwo(num); // query type-1 num = 2 ; performQueryOne(num); // query type-3 System.out.println(performQueryThree()); } } // This code is contributed by debjitdbb |
Python3
# Python3 program to perform Queries # to add, remove and return # difference of maximum and minimum. # Function to perform query 1 def performQueryOne(num): # insert the element s.add(num) # Function to perform query 2 def performQueryTwo(num): # erase the element s.remove(num) # function to perform query 3 def performQueryThree(): mini = min (s) maxi = max (s) return maxi - mini # Driver Code if __name__ = = "__main__" : s = set () # query type-1 num = 3 performQueryOne(num) # query type-1 num = 5 performQueryOne(num) # query type-1 num = 6 performQueryOne(num) # query type-2 num = 5 performQueryTwo(num) # query type-1 num = 2 performQueryOne(num) # query type-3 print (performQueryThree()) # This code is contributed by Rituraj Jain |
C#
// C# program to perform Queries // to add, remove and return // the difference of maximum and // minimum using TreeSet. using System; using System.Collections.Generic; class GFG { static SortedSet< int > t = new SortedSet< int >(); // function to perform query 1 static void performQueryOne( int num) { // insert the element t.Add(num); } // function to perform query 2 static void performQueryTwo( int num) { // erase the element t.Remove(num); } // function to perform query 3 static int performQueryThree() { int mini = t.Min; int maxi = t.Max; return maxi - mini; } // Driver Code public static void Main(String[] args) { // query type-1 int num = 3; performQueryOne(num); // query type-1 num = 5; performQueryOne(num); // query type-1 num = 6; performQueryOne(num); // query type-2 num = 5; performQueryTwo(num); // query type-1 num = 2; performQueryOne(num); // query type-3 Console.WriteLine(performQueryThree()); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to perform Queries to // add, remove and return // the difference of maximum and minimum. var s = new Set(); // function to perform query 1 function performQueryOne( num) { // insert the element s.add(num); } // function to perform query 2 function performQueryTwo( num) { // erase the element s. delete (num); } // function to perform query 3 function performQueryThree() { var tmp = [...s].sort((a,b)=>a-b); var mini = tmp[0]; var maxi = tmp[tmp.length-1]; return maxi - mini; } // Driver Code // query type-1 var num = 3; performQueryOne(num); // query type-1 num = 5; performQueryOne(num); // query type-1 num = 6; performQueryOne(num); // query type-2 num = 5; performQueryTwo(num); // query type-1 num = 2; performQueryOne(num); // query type-3 document.write( performQueryThree()); </script> |
4
Complexity Analysis:
- Time Complexity: O(log N) for every query, as we are using tree set and insert, remove and getting minimum or maximum element will take logN time.
- Auxiliary Space: O(N), as we are using extra space for the tree set.
Contact Us