Arrays and lists in everyday code

Most problems hand you an array and ask for something about it. This lesson is the everyday toolkit: making arrays, growing them, sorting them and handing one back. How arrays are laid out in memory, and why that makes them fast, comes in a later lesson.

Fixed size or growable#

Every language has two kinds: one whose size is fixed when it is made, and one that grows as you add to it.

// Fixed: ask for the memory yourself.
int* squares = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) squares[i] = i * i;

// Growable: C has none built in. Allocate the most you could need,
// and keep your own count of how many are used.
int* evens = malloc(n * sizeof(int));
int count = 0;
for (int i = 0; i < n; i++) {
    if (nums[i] % 2 == 0) evens[count++] = nums[i];
}

vector<int> squares(n);                 // n zeros, fixed until you change it
for (int i = 0; i < n; i++) squares[i] = i * i;

vector<int> evens;                      // empty, grows as you push
for (int x : nums) {
    if (x % 2 == 0) evens.push_back(x);
}

int[] squares = new int[n];             // n zeros, and n forever
for (int i = 0; i < n; i++) squares[i] = i * i;

List<Integer> evens = new ArrayList<>(); // grows as you add
for (int x : nums) {
    if (x % 2 == 0) evens.add(x);
}

squares = [0] * n                       # n zeros
for i in range(n):
    squares[i] = i * i

evens = []                              # grows as you append
for x in nums:
    if x % 2 == 0:
        evens.append(x)

# Or in one line, which Python programmers use constantly:
evens = [x for x in nums if x % 2 == 0]

Adding to the end of a growable array is fast, one step on average. Adding to the front is not: everything has to shift along by one. If you find yourself inserting at the front in a loop, build the array backwards and reverse it once at the end.

Handing an array back to the judge#

When a problem returns an array, the growable kind is often the easiest to build, but the signature may ask for the fixed kind.

// Allocate, fill, and say how many you filled.
int* answer = malloc(count * sizeof(int));
for (int i = 0; i < count; i++) answer[i] = evens[i];
*returnSize = count;
return answer;

return evens;    // a vector is returned as it is

// The signature says int[], so copy the list across.
int[] answer = new int[evens.size()];
for (int i = 0; i < evens.size(); i++) answer[i] = evens.get(i);
return answer;

return evens     # a list is returned as it is

Sorting#

You will rarely write your own sort. Each language has one that takes about n log n steps, which for 100,000 numbers is under two million.

int ascending(const void* a, const void* b) {
    int x = *(const int*) a, y = *(const int*) b;
    return (x > y) - (x < y);
}

qsort(nums, numsSize, sizeof(int), ascending);

sort(nums.begin(), nums.end());                      // ascending
sort(nums.begin(), nums.end(), greater<int>());      // descending

Arrays.sort(nums);                                   // an int[], ascending
Collections.sort(list);                              // a List, ascending
list.sort(Comparator.reverseOrder());                // descending

nums.sort()                        # in place, ascending
nums.sort(reverse=True)            # descending
ordered = sorted(nums)             # a new sorted list; nums is untouched

In C, write the comparison as (x > y) - (x < y) rather than the tempting x - y. The subtraction overflows for large values of opposite sign and sorts them the wrong way round.

Grids#

A grid is an array of rows. Position [r][c] is row r, column c.

int** grid = malloc(rows * sizeof(int*));
for (int r = 0; r < rows; r++) {
    grid[r] = calloc(cols, sizeof(int));     // calloc fills with zeros
}

vector<vector<int>> grid(rows, vector<int>(cols, 0));

int[][] grid = new int[rows][cols];

grid = [[0] * cols for _ in range(rows)]
# Not [[0] * cols] * rows: that makes every row the same list,
# so changing one row changes all of them.

The Python trap in that last comment is one of the most asked questions about the language. The list comprehension builds a fresh row each time; multiplying the outer list copies a reference to one row.

Useful one-liners#

To find	C++	Java	Python
the largest	`*max_element(v.begin(), v.end())`	`Arrays.stream(a).max().getAsInt()`	`max(a)`
the total	`accumulate(v.begin(), v.end(), 0LL)`	`Arrays.stream(a).asLongStream().sum()`	`sum(a)`
reversed	`reverse(v.begin(), v.end())`	loop, swapping from both ends	`a[::-1]` or `a.reverse()`

In C you write each of these as a short loop, which is no bad thing: you can see exactly what it costs.

Try it#

Move zeroes asks you to rearrange an array in place, keeping the order of the non-zero values. Pascal's triangle returns a grid whose rows have different lengths, which is good practice at building one row at a time.