Data structure view
Vector is a fundamental data structure for a growable, indexable array. It is commonly known that, when the allocated buffer space needs to grow, it is reallocated with twice the previous size (so that "push" operation is kept at amortized O(1)). Therefore, the allocated buffer will be longer than the length (the number of actual elements) most of the time.
But, it should be noted that the
length property is what defines the content of the vector. Let's assume the buffer contains the values
[1, 2, 3, 4]. If the
length is 4, the vector object as a whole represents an array
[1, 2, 3, 4]. If it is 3, the object represents an array
[1, 2, 3].
They. Are. Not. Equal.
In order to be able to consider two objects the same, the expected behavior should be the same for all defined operations. Let's again consider the
[1, 2, 3, 4] and
[1, 2, 3] case. Accessing the indices 0 to 2 is not the only operations allowed on it.
- The most obvious one is requesting the length. The former will return 4 while the latter will return 3.
- If an out-of-bounds index is requested, it should result in an error. But accessing index 3 of
[1, 2, 3, 4] does not error.
Longer array behave like small ones as long as you don't access its length or out-of-range values
To achieve this effect, you should re-assign the length yourself (or equivalent in your language of choice).
[1, 2, 3, 4] resized into length 3 is identical to
[1, 2, 3], even if the 4 is still in the memory.
If you're working in C or a lower-level language, writing
n+extra items into the given buffer and returning
n is a valid method to effectively return an array of length
n. (Remember, a buffer and length combined defines an array. Also note that something of an array type (e.g.
int ) cannot be passed as an argument to or returned from a function.)
Software engineering view
Have you seen "test cases" on many challenges? They define a unit test which every submission shall pass. Unit tests for arrays (and nested structures) compare the
expected values via deep equality. Deep equality of two arrays
y is defined as follows:
- The length of
x is equal to that of
x[i] == y[i] for every valid index
If your submission outputs a longer array than requested, it violates the first condition of deep equality, and therefore it fails the unit test. What do you get if a unit test fails? A big red cross, a.k.a. "Sorry, your submission is invalid, and should be deleted."