Table of contents
1.
Understanding
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
2.4.
Input
2.5.
Output
2.6.
Explanation
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

Maximize score by rearranging Array such that absolute difference of first and last element is minimum

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Understanding

This blog discusses a coding challenge based on greedy algorithms. Greedy algorithms are one of the simplest-to-understand algorithms. The logic behind such algorithms can be speculated intuitively. Problems based on greedy algorithms are increasingly asked in programming contests and technical interviews to test your observation skills. 

Problem Statement

Ninja has given you an array ‘ARR’ of size ‘N’. Your task is to rearrange the array so that the score of the array is maximised while keeping the absolute difference between the first and last elements as small as possible.

 

Score of an array

Number of possible indices IND such that ARR[IND] < ARR[IND + 1], where IND + 1 < N.

Input

N = 6

ARR = {8, 2, 1, 9, 4}

Output

3

Explanation

We can rearrange the array to {1, 4, 8, 9, 2} where the absolute difference between the first and last elements is one (minimum possible), and the score is 3.

Input

N = 6

ARR = {6, 3, 10, 13, 20, 25}

Output

Explanation

We can rearrange the array to {3, 10, 13, 20, 25, 6} or {10, 20, 25, 3, 6, 13} to achieve the maximum score of 3 while keeping the absolute difference between the first and last elements 3, which is the minimum possible case.

Approach

This coding challenge can be solved using a greedy approach. Two conditions that the problem demands are:

  1. Minimum possible absolute difference between the first and last elements
  2. Maximum score among all rearrangements.

Let's focus on the first one. To identify elements in the array with the minimum absolute difference, we can sort the array and check the absolute difference between adjacent elements. Let ‘IND’ be the index of the first element in such a pair of elements with a minimum absolute difference.

Now, let's focus on the second condition of the problem. Once we have identified the first and last elements, the task is to rearrange the remaining elements in the best way possible to achieve the maximum score. It can be done as follows:

  1. Create a new array, ‘OPTIMAL_ARRAY’ of size ‘N’ and put ‘OPTIMAL_ARRAY[0] = ARR[IND] and OPTIMAL_ARRAY[N - 1] = ARR[IND + 1].
  2. From the first index onwards, fill the array with elements greater than ARR[IND] in non-decreasing order.
  3. Fill the remaining indices with the left-out elements in non-decreasing order.

Algorithm

  1. Take the input.
  2. Sort the array.
  3. Find the index ‘IND’ such that ARR[IND + 1] - ARR[IND] is the minimum possible absolute difference between overall adjacent elements.
  4. Create a new array ‘OPTIMAL_ARRAY’ to store the rearranged array.
  5. Update OPTIMAL_ARRAY[0] = ARR[IND] and OPTIMAL_ARRAY[N - 1] = ARR[IND].
  6. Loop over the sorted array with current index i and maintain a variable INDEX = 1 to fill the empty indices in the OPTIMAL_ARRAY.
    1. If the current element ARR[i] is greater than ARR[IND] and i is not equal to either of IND or IND + 1, update OPTIMAL_ARRAY[INDEX++] = ARR[i].
  7. Fill the remaining elements in the OPTIMAL_ARRAY array with the left-out elements in the sorted array.

Program

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

// Solve for the given input.
void solve(vector<int>& arr, int N)
{
   // Sort the array.
   sort(arr.begin(), arr.end());

   int ind = 0;

   // Initial minimum absolute difference.
   int difference = arr[1] - arr[0];

   for(int i = 1; i < N - 1; i++)
   {
       // Check for the minimum absolute difference and update if required.
       if(difference > arr[i + 1] - arr[i])
       {
           difference = arr[i + 1] - arr[i];
           ind = i;
       }
   }

   // To store the rearranged array.
   int optimalArray[N];

   // As discussed in the approach.
   optimalArray[0] = arr[ind];
   optimalArray[N - 1] = arr[ind + 1];
   // To fill the remaining positions.
   int index = 1;
   for(int i = 0; i < N; i++)
   {
       // First fill the elements greater than optimalArray[0] in non-decreasing order.
       if(i != ind && i != ind + 1 && arr[i] > arr[ind])
       {
           optimalArray[index] = arr[i];
           index++;
       }
   }

   // Fill the remaining elements in non-decreasing order.
   for(int i = 0; i < N; i++)
   {
       if(i != ind && i != ind + 1 && arr[i] <= arr[ind])
       {
           optimalArray[index] = arr[i];
           index++;
       }
   }

   // Output the array.
   for(int i = 0; i < N; i++)
   {
       cout<<optimalArray[i]<<" ";
   }
   cout<<endl;
}

int main()
{
   // Take the input.
   int N; cin>>N;
   vector<int> arr(N);

   for(int i = 0; i < N; i++)
   {
       cin>>arr[i];
   }

   // Solve for the given input.
   solve(arr, N);
}
You can also try this code with Online C++ Compiler
Run Code

Input

6
6 3 10 13 20 25

Output

3 10 13 20 25 6

Time Complexity

The time complexity of the above approach is O(N * log N), where ‘N’ is the size of the array. It is because we are sorting the array to identify elements satisfying the first condition.

Space Complexity

The space complexity of the above approach is O(N), as we are using extra space to store the rearranged array.

Key Takeaways

In this blog, we discussed a problem based on greedy algorithms. Greedy algorithms are one of the most popular algorithms in technical interviews. It requires critical observations to identify the algorithm. Most of the time, it is easy to code a greedy algorithm, however, we may have to use set/map/multiset to implement a greedy approach in the proposed time limit.

Hence learning never stops, and there is a lot more to learn.

Recommended Problems -

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
 

Live masterclass