This problem is special because it took me more than 15 attempts to solve properly. Initially my thought was to generate all possible heights and then for each height, compute what is the width, and then take the maximum of them, but that produced an O(n^3) solution. Given n <= 1000, we were getting TLE.
The trick to this problem is that two unique heights can produce only combined height, i.e. if a + b = c then for any other d if a + d = c, implied b = d. So we just had to count what is the contribution to the width for any two unique heights (which is minimum of availability of both the planks).
Additionally, same plank can either contribute as itself, or we can use two of same height plank, to produce a fence double the height. These two cases were required to be handled separately.
class Solution {
private Map<Integer, Integer> getCounter(final int[] vals) {
final Map<Integer, Integer> counter = new HashMap<Integer, Integer>();
for (final int val : vals) {
counter.merge(val, 1, Integer::sum);
}
return counter;
}
public int maximumWidth(final int[] planks) {
final Map<Integer, Integer> counter = getCounter(planks);
final int n = counter.size();
final int[] vals = new int[n];
final int[] cnts = new int[n];
int idx = 0;
for (final Map.Entry<Integer, Integer> e : counter.entrySet()) {
vals[idx] = e.getKey();
cnts[idx] = e.getValue();
idx++;
}
final Map<Integer, Integer> widths = new HashMap<>();
for (int i = 0; i < n; ++i) {
widths.merge(vals[i], cnts[i], Integer::sum);
widths.merge(2 * vals[i], cnts[i] / 2, Integer::sum);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
final int h = vals[i] + vals[j];
final int c = Math.min(cnts[i], cnts[j]);
final int w = c + widths.getOrDefault(h, 0);
widths.put(h, w);
}
}
return Collections.max(widths.values());
}
}