Maximizing number of rearrangedArr[i] > originalArr[i]-CodePudding

Given an array arr, we can rearrange it to form another array, rearrangedArr. The greatness of the array is defined as the number of indices 0 <= i < n where rearrangedArr[i] > originalArr[i].

Given the initial array original, you need to find the maximum possible greatness which can be achieved by some rearrangement of the array.

For example, if the original array is [1, 3, 5, 2, 1, 3, 1], the maximum greatness will be $4$ as the optimal rearrangement can be:

[1, 3, 5, 2, 1, 3, 1]
[2, 5, 1, 3, 3, 1, 1]

We can see the indices 0,1, 3 and 4 highlighted satisfy rearrangedArr[i] > originalArr[i].

My attempt was to find the closest minimum number for each number in originalArr. For example, the closest minimum number to 1 will be 2 (index 0 in originalArr) then 3 for the second 1 (index 1), again 3 for the third 1 (index 2), then for 2 (index 3) it will be 3, and so on. However, this approach was inefficient (and I suspect is suboptimal). So, my next attempt to solve it efficiently was to sort the array and then use the 2 pointer approach:

1 1 1 2 3 3 5
^__________^

However, this way doesn't seem to work as 1 will get 5, then the second 1 will get 3, the third 1 will get a 3 and then 2 won't have a number that can cover it.

What would the most optimal approach to solve this question? Is there a way to make my 2 pointer approach mentioned above work?

CodePudding user response：

Greedy approach should work. You try to get as many you can by looking at the next higher elements available.

Insert the numbers (or keys) in a structure like Java's TreeMap (backed by Red Black Tree) and then for each number in the array look at the next highest key, if its available increase the greatness by 1 and decrement the key's value in the TreeMap. If the key's value reaches 0 delete it. By the time you go through each number you will have maximum greatness.

Lets go through the array [1, 3, 5, 2, 1, 3, 1] to see how it works. When we build a treemap out of this it will look like:

1 -> 3
2 -> 1
3 -> 2
5 -> 1

Now for each number:

1 - Do we have a higher key? yes 2, increase greatness and decrement its value in treemap because it is 0, delete the key.

greatness = 1

map:

1 -> 3
3 -> 2
5 -> 1

3 - Do we have a higher key? yes 5, do the same as above.

greatness = 2

map:

1 -> 3
3 -> 2

5 - Do we have a higher key? No. nothing to do.

2 - Do we have a higher key? Yes. do the same as before.

greatness = 3

map:

1 -> 3
3 -> 1

1 - Do we have a higher key? Yes. its 3 now. and not 2.

greatness = 4

map:

1 -> 3

3 - Do we have a higher key? No. nothing to do.

1 - Nothing to do.

Result in greatness = 4.

Code in Java is:

private static int getMaximumGreatness(int[] arr) {
  int greatness = 0;
  TreeMap < Integer, Integer > treeMap = new TreeMap < > ();
  for (int a: arr) {
    if (treeMap.containsKey(a)) {
      treeMap.put(a, treeMap.get(a)   1);
    } else {
      treeMap.put(a, 1);
    }
  }

  for (int a: arr) {
    Integer higher = treeMap.higherKey(a);
    if (higher != null) {
      greatness  ;
      Integer value = treeMap.get(higher) - 1;
      if (value == 0) {
        treeMap.remove(higher);
      } else {
        treeMap.put(higher, value);
      }

    }
  }
  return greatness;
}

The complexity should be O(n log n) log n for the searches for next higher key.