Given an array arr[] of N integers, the task is to maximize the number of indices such that an element is greater than the element to its left, i.e. arr[i+1] > arr[i] after rearranging the array.
Examples:
Input: arr[] = {200, 100, 100, 200}
Output: 2
Explanation:
By arranging the array in following way we have: arr[] = {100, 200, 100, 200}
The possible indices are 0 and 2 such that:
arr[1] > arr[0] (200 > 100)
arr[3] > arr[2] (200 > 100)
Input: arr[] = {1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7}
Output: 7
Explanation:
By arranging the array in following way we have: arr[] = {1, 5, 7, 8, 9, 5, 7, 8, 7, 8, 4}
The possible indices are 0, 1, 2, 3, 5, 6 and 7 such that:
arr[1] > arr[0] (5 > 1)
arr[2] > arr[1] (7 > 5)
arr[3] > arr[2] (8 > 7)
arr[4] > arr[3] (9 > 8)
arr[6] > arr[5] (7 > 5)
arr[7] > arr[6] (8 > 7)
arr[8] > arr[7] (8 > 7)
Approach: This problem can be solved using Greedy Approach. Below are the steps:
- To get the maximum number of indices(say i) such that arr[i+1] > arr[i], arrange the elements of the arr[] such that set of all unique element occurs first, then next set of unique elements occurs after the first set till all the elements are arranged.
For Example:
Let arr[] = {1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7}
1st Set = {1, 5, 7, 8, 9}
2nd Set = {5, 7, 8}
3rd Set = {7, 8}
4th Set = {4}
Now the new array will be:
arr[] = {1, 5, 7, 8, 9, 5, 7, 8, 7, 8, 4}
- After the above arrangement, the element with the higher value will not be a part of the given condition as it is followed by a number smaller than itself.
- Therefore the total number of pairs satisfying the given condition can be given by:
total_pairs = (number_of_elements – highest_frequency_of_a_number)
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum pairs// such that arr[i+1] > arr[i]void countPairs(int arr[], int N){ // To store the frequency of the // element in arr[] unordered_map<int, int> M; // Store the frequency in map M for (int i = 0; i < N; i++) { M[arr[i]]++; } int maxFreq = 0; // To find the maximum frequency // store in map M for (auto& it : M) { maxFreq = max(maxFreq, it.second); } // Print the maximum number of // possible pairs cout << N - maxFreq << endl;}// Driver Codeint main(){ int arr[] = { 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 }; int N = sizeof(arr) / sizeof(arr[0]); countPairs(arr, N); return 0;} |
Java
// Java program of the above approachimport java.util.*;class GFG{ // Function to find the maximum pairs// such that arr[i+1] > arr[i]static void countPairs(int arr[], int N){ // To store the frequency of the // element in arr[] HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Store the frequency in map M for (int i = 0; i < N; i++) { if(mp.containsKey(arr[i])){ mp.put(arr[i], mp.get(arr[i])+1); }else{ mp.put(arr[i], 1); } } int maxFreq = 0; // To find the maximum frequency // store in map M for (Map.Entry<Integer,Integer> it : mp.entrySet()) { maxFreq = Math.max(maxFreq, it.getValue()); } // Print the maximum number of // possible pairs System.out.print(N - maxFreq +"\n");} // Driver Codepublic static void main(String[] args){ int arr[] = { 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 }; int N = arr.length; countPairs(arr, N);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the above approach# Function to find the maximum pairs# such that arr[i + 1] > arr[i]def countPairs(arr, N) : # To store the frequency of the # element in arr[] M = dict.fromkeys(arr, 0); # Store the frequency in map M for i in range(N) : M[arr[i]] += 1; maxFreq = 0; # To find the maximum frequency # store in map M for it in M.values() : maxFreq = max(maxFreq,it); # Print the maximum number of # possible pairs print(N - maxFreq);# Driver Codeif __name__ == "__main__" : arr = [ 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 ]; N = len(arr); countPairs(arr, N); # This code is contributed by AnkitRai01 |
C#
// C# program of the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the maximum pairs// such that arr[i+1] > arr[i]static void countPairs(int []arr, int N){ // To store the frequency of the // element in []arr Dictionary<int,int> mp = new Dictionary<int,int>(); // Store the frequency in map M for (int i = 0; i < N; i++) { if(mp.ContainsKey(arr[i])){ mp[arr[i]] = mp[arr[i]]+1; }else{ mp.Add(arr[i], 1); } } int maxFreq = 0; // To find the maximum frequency // store in map M foreach (KeyValuePair<int,int> it in mp) { maxFreq = Math.Max(maxFreq, it.Value); } // Print the maximum number of // possible pairs Console.Write(N - maxFreq +"\n");} // Driver Codepublic static void Main(String[] args){ int []arr = { 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 }; int N = arr.Length; countPairs(arr, N);}} // This code is contributed by Rajput-Ji |
Javascript
<script>// Js program of the above approach// Function to find the maximum pairs// such that arr[i+1] > arr[i]function countPairs( arr, N){ // To store the frequency of the // element in arr[] let M = new Map(); // Store the frequency in map M for (let i = 0; i < N; i++) { if(M[arr[i]]) M[arr[i]]++; else M[arr[i]] = 1 } let maxFreq = 0; // To find the maximum frequency // store in map M for (let it in M) { maxFreq = Math.max(maxFreq, M[it]); } // Print the maximum number of // possible pairs document.write(N - maxFreq,'<br>');}// Driver Codelet a = [ 1, 8, 5, 9, 8, 8, 7, 7, 5, 7, 7 ];let N = a.length; countPairs(a, N);</script> |
7
Time Complexity: O(N), where N is the number of element in the array.
Auxiliary Space: O(N), where N is the number of element in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
