### PROBLEM LINK:

Practice

Contest

Video Editorial

**Author:** Hasan Jaddouh

**Tester:** Misha Chorniy

**Editorialist:** Pushkar Mishra

### DIFFICULTY:

Simple

### PREREQUISITES:

Greedy

### PROBLEM:

Given an array of A of N integers which represent stick lengths, we have to report the maximal area over all the rectangles that we can form with the given sticks without breaking any.

### EXPLANATION:

The problem is a simple one based on a very basic property of all rectangles: the opposite sides of a rectangle are parallel, and hence, equal in length. The area of a rectangle is given by base B multiplied by height H. Now, to maximise the area, we simply need to maximise the length of sticks we choose as our B and H. This is pretty intuitive but we can also invoke the exchange argument method (page 3 of link) to give a more formal argument as proof of why this works (left to reader as a simple learning exercise).

Now we come to the implementation detail of the above mentioned algorithm. Note that N and A_{max} both range between 1 and 10^3. So, one way is that we simply keep an array Count of length 10^3 wherein Count[i] is the number of sticks of length i that we have. Once we have populated this structure, we can simply scan from 10^3 down to 1. If while scanning, we can find one field which has more than 3 sticks, then that i can be our height and base both; at this point we terminate our scan. If we find a field that has more than 1 stick, we can make it either our height or base and continue our scan to find a value for the other one. If at the end of scan we donâ€™t find at least two i for which the count is more than 1, then we output -1 since no rectangle can be formed.

The other implementation can be by using a map instead of an array. In that case, if the N is much smaller than A_{max}, we can get a better performance. Both of the implementations easily pass for the given constraints.

Please see editorialistâ€™s/setterâ€™s program for implementation details.

### COMPLEXITY:

\mathcal{O}(N\log N) or \mathcal{O}(A_{max}) per test case.