07. Arrays and vector

Most OSN problems give you a sequence of data: exam scores, tree heights, coordinates, item weights. Storing them in separate variables is clearly impossible. Arrays and vector are containers for sequences of data like that.

Arrays

int a[5];              // five boxes, contents not yet defined
int b[5] = {3, 1, 4, 1, 5};

cout << b[0] << "\n";  // 3  -- the first index is 0
cout << b[4] << "\n";  // 5  -- the last index is length - 1
b[2] = 99;

An array is n boxes of the same type laid out contiguously in memory. What makes it fast: the computer only needs to know where the first box is, and the i-th box is then found with a single calculation — the start address plus i times the size of one box. That is why indices start at 0: a[0] means "zero boxes from the start".

index:     0     1     2     3     4
        +-----+-----+-----+-----+-----+
b:      |  3  |  1  |  4  |  1  |  5  |
        +-----+-----+-----+-----+-----+

Accessing b[3] takes the same time as accessing b[0], whether the array holds five boxes or a million.

Important rules:

• Indices start at 0. An array of size n has indices 0 through n - 1.
• The size must be known at compile time (a fixed number or a const int).
• Reading or writing out of bounds is not prevented by the compiler. The program still runs, with garbage values, or crashes.

The pattern for reading n numbers:

const int MAKS = 100005;
int a[MAKS];

int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

Basic patterns on arrays

// sum
long long total = 0;
for (int i = 0; i < n; i++) total += a[i];

// largest and smallest
int besar = a[0], kecil = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] > besar) besar = a[i];
    if (a[i] < kecil) kecil = a[i];
}

// counting elements that meet a condition
int genap = 0;
for (int i = 0; i < n; i++) if (a[i] % 2 == 0) genap++;

// searching for a value, storing its position
int posisi = -1;
for (int i = 0; i < n; i++) {
    if (a[i] == target) { posisi = i; break; }
}

Note the "largest" pattern: its initial value is a[0], not 0. If all the data is negative, starting from 0 gives a wrong answer. Since the initial value is already a[0], the loop starts from i = 1 — checking a[0] again is not wrong, just wasteful.

All four patterns above have the same shape: one pass, one accumulator, one decision per element. The number of steps is O(n), so they all stay fast up to n in the millions. Only when a problem demands comparing each element with every other element does the work jump to n² — and that is covered in Chapter 11.

vector

A vector is an array whose size can change while the program runs.

#include <vector>

vector<int> v;             // empty
v.push_back(10);           // append at the back
v.push_back(20);
cout << v.size() << "\n";  // 2
cout << v[0] << "\n";      // 10

vector<int> w(5, 0);       // 5 elements, all 0
vector<int> u = {3, 1, 4};

Iterating over a vector:

for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";

for (int x : v) cout << x << " ";      // short form

push_back adds one element at the back, and the vector manages growing its own memory. The average cost stays small, so appending a million elements one at a time is still fast.

Use a plain array when the size is already known from the problem's limits, and a vector when the size is only known at run time or when it needs to be passed to a function.

Sorting

sort from the <algorithm> library sorts from smallest to largest:

#include <algorithm>

sort(a, a + n);                  // array
sort(v.begin(), v.end());        // vector

For descending order:

sort(v.begin(), v.end(), greater<int>());

The two values given to sort are the start and one past the end. So sort(a, a + n) sorts a[0] through a[n-1], and sort(a + 2, a + 5) sorts only the three elements in the middle. This "one past the end" pattern is used throughout the C++ standard library.

Sorting n items takes about n log n steps — for 100,000 items about 1.7 million steps, very fast. Compare that with sorting by hand using two nested loops, which takes about 5 billion steps for the same n. In contests, writing your own sort is almost never the right choice.

Sorting often turns a problem that looks hard into an easy one: "the two most similar numbers" becomes "two adjacent numbers" (Chapter 08), "take the most profitable" becomes "take from the front" (Chapter 12). Many greedy problems in Chapter 12 do begin with a single sort line.

Two-dimensional arrays

For tables or maps:

int grid[100][100];

for (int i = 0; i < baris; i++)
    for (int j = 0; j < kolom; j++)
        cin >> grid[i][j];

grid[i][j] means row i, column j — row first, then column. This order is a frequent source of confusion, because in mathematical coordinates x (horizontal) is usually named first.

            j=0   j=1   j=2
         +-----+-----+-----+
   i=0   |  7  |  2  |  9  |     grid[0][2] is 9
         +-----+-----+-----+
   i=1   |  4  |  1  |  3  |     grid[1][0] is 4
         +-----+-----+-----+

The amount of work is rows × columns, so a 1000 × 1000 map means a million steps for a single pass.

Two-dimensional arrays get large quickly: int grid[1000][1000] already uses about 4 MB, and int grid[5000][5000] about 100 MB — more than the memory limit of most problems. If the row limit is large while the column count is small, write grid[100005][5], not the other way around.

Arrays as markers: the prime number sieve

One of the most frequent uses of arrays in OSN: using one as a list of markers. The Sieve of Eratosthenes finds all prime numbers up to n by crossing out the multiples of each prime number.

const int MAKS = 1000001;
bool coret[MAKS];

void saring(int n) {
    coret[0] = coret[1] = true;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (!coret[i]) {
            for (int j = i * i; j <= n; j += i) coret[j] = true;
        }
    }
}

Trace it for n = 30. Initially nothing is crossed out, then:

The loop stops at i = 6 because 6 × 6 exceeds 30. What remains is exactly the ten prime numbers up to 30.

Two details are worth noting. Crossing out starts from i * i, not from 2 * i, because the smaller multiples have certainly been crossed out by smaller prime numbers already. And numbers that are already crossed out are skipped entirely, because their multiples have also been crossed out.

After it runs, coret[x] == false (coret = "crossed out") means x is prime. Checking one at a time with the square-root method takes about n √n steps; the sieve only about n log log n — for n = 10⁶, that is the difference between several seconds and several milliseconds.

Homework

Most common mistakes

OSN tips

A counting array is the most frequently used technique. If the values in a problem are bounded to be small — for example 1 to 1000 or 1 to 10⁶ — there is almost always a solution that uses an array as long as that value limit, not as long as the number of data items. Reading the sentence "1 ≤ Aᵢ ≤ 1000" as a signal to "make cacah[1001]" (cacah = "count") saves a lot of thinking time.

The memory limit also shapes the solution. One int takes 4 bytes, one long long 8 bytes. From that, array sizes can be calculated:

The memory limit is written in the problem header. If the calculation goes over that limit, then the intended solution is not one that stores everything.

Large arrays are declared outside main. Local variables are stored on the stack, which is much smaller than the program's memory. int a[10000000]; inside main usually makes the program stop on its own before the first line runs. A declaration outside main uses global memory, and as a bonus its contents are automatically zero.

Out-of-bounds indices are not always immediately visible. C++ does not check array bounds. a[n] on an array of size n sometimes runs smoothly on your own computer and produces a Runtime Error or strange answers on the grading machine. If your answer is correct at home but rejected by the judge, check every index at the boundaries.

Sort first when the problem talks about "nearest", "pairs", or "consecutive". Sorting N items takes about N log N steps — for N = 200,000 that is under four million steps, practically free compared with comparing all pairs, which takes 2 × 10¹⁰ steps.

Problems that mention 1 to N are often easier with 1-based indices. Making an array of size n + 1 and leaving index 0 empty removes all the error-prone −1 adjustments. The memory wasted is one element.

Summary

• An array stores n values of the same type contiguously; its indices are 0 through n - 1, and access is always equally fast.
• Touching an out-of-bounds index is not prevented by the compiler and is the most frequent cause of Runtime Error.
• Large arrays are made global with a size slightly above the problem's limit.
• vector is used when the size is only known at run time; v.size() is unsigned, so cast it with (int) before subtracting.
• sort works on the range from the start to one past the end, takes about n log n steps, and often turns a hard problem into an easy one.
• Two-dimensional arrays are accessed as grid[row][column]; their size quickly uses up memory.
• A marker array (bool) is a versatile tool; the Sieve of Eratosthenes is its most important example.

OSN-style exercises

The following three problems cover the three array techniques that appear most often in OSN: counting arrays, sorting, and summing over a two-dimensional array.

The starter files for all three are in exercises/07/osn/.

Problem 1 — Score Mode

The committee collects the exam scores of N students. Determine the score that appears most often along with the number of times it appears. If more than one score has the same highest count, choose the smallest score.

Input format. The first line contains an integer N. The second line contains N integers A₁ A₂ … A_N.

Output format. One line containing two integers: the most frequent score, then the number of times it appears.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ Aᵢ ≤ 1000

Sample input

7
3 1 3 2 1 3 2

Sample output

3 3

Explanation. The score 3 appears three times, the scores 1 and 2 twice each. Note the constraint Aᵢ ≤ 1000: there are far fewer distinct values than data items, and that is the hint for how to solve it.

Starter file: exercises/07/osn/01-modus-nilai.cpp

Problem 2 — Smallest Difference

Given N integers, determine the smallest possible difference between two numbers at different positions. The difference is always computed as a non-negative number.

Input format. The first line contains an integer N. The second line contains N integers.

Output format. One line containing the smallest difference.

Constraints.

• 2 ≤ N ≤ 200,000
• −10¹⁸ ≤ Aᵢ ≤ 10¹⁸

Sample input

5
10 2 7 3 9

Sample output

1

Explanation. The pair (2, 3) and the pair (9, 10) both have a difference of 1, and no pair is closer. If two numbers are exactly equal, the answer is 0.

Starter file: exercises/07/osn/02-selisih-terkecil.cpp

Problem 3 — Largest Row and Column

A table with R rows and C columns contains integers. Determine the number of the row whose sum is largest and the number of the column whose sum is largest. Rows and columns are numbered starting from 1. If there is a tie, choose the smallest number.

Input format. The first line contains two integers R and C. Each of the next R lines contains C integers.

Output format. One line containing two integers: the row number and the column number, separated by a single space.

Constraints.

• 1 ≤ R, C ≤ 500
• −10⁶ ≤ table entry ≤ 10⁶

Sample input

2 3
1 2 3
4 5 6

Sample output

2 3

Explanation. The sum of the first row is 1 + 2 + 3 = 6, of the second row 4 + 5 + 6 = 15, so the largest row is row 2. The column sums are 5, 7, and 9 respectively, so the largest column is column 3.

Starter file: exercises/07/osn/03-baris-kolom-terbesar.cpp

Stuck or already done? Open the homework solutions page.