Maximize the number of indices such that element is greater than element to its left

0 0 5 minutes read

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 Code
int 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 approach
import 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 Code
public 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 Code
if __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 approach
using 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 Code
public 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 Code
let a = [ 1, 8, 5, 9, 8, 8, 7,
                  7, 5, 7, 7 ];
let N = a.length;
 
    countPairs(a, N);
 
 
</script>

Output:

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.

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 zambiatek!