Maximizing Strength difference in Two groups
Given an integer N and an array A[] of size 3*N. We need to remove N integers and form 2 groups with the remaining 2*N integers of each size N. 1st group will be of integers having the smallest index and 2nd group will be of the larger index. Let the total sum of the strength of group1 be S1 and the total sum of the strength of group2 be S2. The task is to maximize S1 – S2.
Examples:
Input: N = 2, A[] = {1, 3, 5, 2, 1, 1}
Output: 6
Explanation: Integers 1 and 4 will be removed. Then S1=(3+5)=8 and S2=(1+1)=2. s1-s2 = 8-2 = 6.Input: N = 2, A[] = {1, 1, 5, 3, 7, 7}
Output: -4
Explanation: The best way is to remove Fighter 1 and 6 S1 – S2 = (1+5) – (3+7) = -4.
Approach: This can be solved with the following idea:
Using Priority queue data structure, we can find which elements need to be removed to have maximum s1 and minimum s2 under size n. So, that overall difference become maximum s1 – s2.
Below are the steps involved:
- Declare a vector prefix and suffix of size (3*n).
- Iterate from i = 0, which will help us to find the maximum sum in s1 having n elements using a priority queue.
- Iterate from i = 3*n -1, which will help us to find minimum sum in s2 having n elements using priority queue.
- Iterate from i = n to 2 * n, and check whether:
- max(ans, prefix[i – 1] – suffix[i]), where ans is initialised with minimum value.
- Return ans.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to maximise s1-s2 long long maxDiff( int n, vector< int > arr) { // Intialize ans with minimum value long long ans = INT_MIN; // Declare prefix and suffix vector vector< long long > prefix(3 * n); vector< long long > suffix(3 * n); long long sum = 0; // Priority queue to increase the sum s1 priority_queue< int , vector< int >, greater< int > > pq; for ( int i = 0; i < 3 * n; i++) { pq.push(arr[i]); sum += arr[i]; // If size becomes more than n if (pq.size() > n) { int val = pq.top(); pq.pop(); sum -= val; } prefix[i] = sum; // cout<<prefix[i]<<" "; } // Priority_queue to decrease the sum s2 sum = 0; priority_queue< int > pq2; for ( int i = 3 * n - 1; i >= 0; i--) { pq2.push(arr[i]); sum += arr[i]; // If size becomes more than n if (pq2.size() > n) { int val = pq2.top(); pq2.pop(); sum -= val; } suffix[i] = sum; } // Iterate to find max diff s1-s2 for ( int i = n; i <= 2 * n; i++) { ans = max(ans, prefix[i - 1] - suffix[i]); } return ans; } // Driver code int main() { int n = 2; vector< int > arr = { 2, 3, 4, 2, 1, 4 }; // Function call cout << maxDiff(n, arr); return 0; } |
Java
// Java code for the above approach: import java.util.PriorityQueue; public class GFG { // Function to maximise s1 - s2 public static long maxDiff( int n, int [] arr) { // Initialize ans with the minimum value long ans = Long.MIN_VALUE; // Declare prefix and suffix arrays long [] prefix = new long [ 3 * n]; long [] suffix = new long [ 3 * n]; long sum = 0 ; // Priority queue to increase the sum s1 PriorityQueue<Integer> pq = new PriorityQueue<>(); for ( int i = 0 ; i < 3 * n; i++) { pq.offer(arr[i]); sum += arr[i]; // If the size becomes more than n if (pq.size() > n) { int val = pq.poll(); sum -= val; } prefix[i] = sum; } // Priority queue to decrease the sum s2 sum = 0 ; PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a); for ( int i = 3 * n - 1 ; i >= 0 ; i--) { pq2.offer(arr[i]); sum += arr[i]; // If the size becomes more than n if (pq2.size() > n) { int val = pq2.poll(); sum -= val; } suffix[i] = sum; } // Iterate to find max diff s1-s2 for ( int i = n; i <= 2 * n; i++) { ans = Math.max(ans, prefix[i - 1 ] - suffix[i]); } return ans; } // Driver code public static void main(String[] args) { int n = 2 ; int [] arr = { 2 , 3 , 4 , 2 , 1 , 4 }; // Function call System.out.println(maxDiff(n, arr)); } } |
Python3
import heapq # Function to maximize s1 - s2 def max_diff(n, arr): # Initialize ans with the minimum value ans = float ( '-inf' ) # Declare prefix and suffix arrays prefix = [ 0 ] * ( 3 * n) suffix = [ 0 ] * ( 3 * n) sum_val = 0 # Priority queue to increase the sum s1 pq = [] for i in range ( 3 * n): heapq.heappush(pq, arr[i]) sum_val + = arr[i] # If the size becomes more than n if len (pq) > n: val = heapq.heappop(pq) sum_val - = val prefix[i] = sum_val # Priority queue to decrease the sum s2 sum_val = 0 pq2 = [] for i in range ( 3 * n - 1 , - 1 , - 1 ): heapq.heappush(pq2, - arr[i]) sum_val + = arr[i] # If the size becomes more than n if len (pq2) > n: val = heapq.heappop(pq2) sum_val - = - val suffix[i] = sum_val # Iterate to find max diff s1-s2 for i in range (n, 2 * n + 1 ): ans = max (ans, prefix[i - 1 ] - suffix[i]) return ans # Driver code if __name__ = = "__main__" : n = 2 arr = [ 2 , 3 , 4 , 2 , 1 , 4 ] # Function call print (max_diff(n, arr)) #This code is contributed by Rohit Singh |
C#
using System; using System.Collections.Generic; class MaxDiff { // Function to maximize s1 - s2 static int MaximizeDifference( int n, int [] arr) { // Initialize ans with the minimum value int ans = int .MinValue; // Declare prefix and suffix arrays int [] prefix = new int [3 * n]; int [] suffix = new int [3 * n]; int sumVal = 0; // Priority queue to increase the sum s1 MinHeap< int > pq = new MinHeap< int >(); for ( int i = 0; i < 3 * n; i++) { pq.Add(arr[i]); sumVal += arr[i]; // If the size becomes more than n if (pq.Count > n) { int val = pq.Remove(); sumVal -= val; } prefix[i] = sumVal; } // Priority queue to decrease the sum s2 sumVal = 0; MaxHeap< int > pq2 = new MaxHeap< int >(); for ( int i = 3 * n - 1; i >= 0; i--) { pq2.Add(arr[i]); sumVal += arr[i]; // If the size becomes more than n if (pq2.Count > n) { int val = pq2.Remove(); sumVal -= val; } suffix[i] = sumVal; } // Iterate to find max diff s1-s2 for ( int i = n; i <= 2 * n; i++) { ans = Math.Max(ans, prefix[i - 1] - suffix[i]); } return ans; } // Driver code static void Main() { int n = 2; int [] arr = { 2, 3, 4, 2, 1, 4 }; // Function call Console.WriteLine(MaximizeDifference(n, arr)); } } // MinHeap implementation class MinHeap<T> where T : IComparable<T> { private List<T> heap = new List<T>(); public int Count => heap.Count; public void Add(T item) { heap.Add(item); int childIndex = heap.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (heap[childIndex].CompareTo(heap[parentIndex]) >= 0) break ; Swap(childIndex, parentIndex); childIndex = parentIndex; } } public T Remove() { if (heap.Count == 0) throw new InvalidOperationException( "Heap is empty." ); T root = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); int currentIndex = 0; while ( true ) { int leftChildIndex = 2 * currentIndex + 1; int rightChildIndex = 2 * currentIndex + 2; int smallestChildIndex = currentIndex; if (leftChildIndex < heap.Count && heap[leftChildIndex].CompareTo(heap[smallestChildIndex]) < 0) smallestChildIndex = leftChildIndex; if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[smallestChildIndex]) < 0) smallestChildIndex = rightChildIndex; if (smallestChildIndex == currentIndex) break ; Swap(currentIndex, smallestChildIndex); currentIndex = smallestChildIndex; } return root; } private void Swap( int index1, int index2) { T temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } } // MaxHeap implementation class MaxHeap<T> where T : IComparable<T> { private List<T> heap = new List<T>(); public int Count => heap.Count; public void Add(T item) { heap.Add(item); int childIndex = heap.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (heap[childIndex].CompareTo(heap[parentIndex]) <= 0) break ; Swap(childIndex, parentIndex); childIndex = parentIndex; } } public T Remove() { if (heap.Count == 0) throw new InvalidOperationException( "Heap is empty." ); T root = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); int currentIndex = 0; while ( true ) { int leftChildIndex = 2 * currentIndex + 1; int rightChildIndex = 2 * currentIndex + 2; int largestChildIndex = currentIndex; if (leftChildIndex < heap.Count && heap[leftChildIndex].CompareTo(heap[largestChildIndex]) > 0) largestChildIndex = leftChildIndex; if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[largestChildIndex]) > 0) largestChildIndex = rightChildIndex; if (largestChildIndex == currentIndex) break ; Swap(currentIndex, largestChildIndex); currentIndex = largestChildIndex; } return root; } private void Swap( int index1, int index2) { T temp = heap[index1]; heap[index1] = heap[index2]; heap[index2] = temp; } } |
Javascript
// Function to maximize s1-s2 function maxDiff(n, arr) { // Initialize ans with minimum value let ans = Number.MIN_SAFE_INTEGER; // Declare prefix and suffix array let prefix = new Array(3 * n).fill(0); let suffix = new Array(3 * n).fill(0); let sum = 0; // Priority queue to increase the sum s1 let pq = []; for (let i = 0; i < 3 * n; i++) { pq.push(arr[i]); sum += arr[i]; // If size becomes more than n if (pq.length > n) { let val = pq.shift(); sum -= val; } prefix[i] = sum; } // Priority_queue to decrease the sum s2 sum = 0; let pq2 = []; for (let i = 3 * n - 1; i >= 0; i--) { pq2.push(arr[i]); sum += arr[i]; // If size becomes more than n if (pq2.length > n) { let val = pq2.shift(); sum -= val; } suffix[i] = sum; } // Iterate to find max diff s1-s2 for (let i = n; i <= 2 * n; i++) { ans = Math.max(ans, prefix[i - 1] - suffix[i]); } return ans; } // Driver code function main() { let n = 2; let arr = [2, 3, 4, 2, 1, 4]; // Function call console.log(maxDiff(n, arr)); } main(); // This code is contributed by shivamgupta310570 |
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us