Arrays, Strings & Character Operations
Learn 1D and 2D arrays in C++, row-major layout, std::string operations, and character manipulation for competitive programming.
Arrays, Strings & Character Operations
Arrays are the most fundamental data structure in competitive programming. Nearly every problem involves reading data into an array, processing it, and outputting a result. This chapter covers arrays, 2D arrays, strings, and the character operations you'll use constantly.
1D Arrays (C-Style)
A C-style array is a contiguous block of memory:
int a[100]; // array of 100 integers (uninitialized)
int b[5] = {1, 2, 3, 4, 5}; // initialized array
int c[5] = {}; // all zeros
Reading Input into Arrays
int n;
cin >> n;
int a[n]; // VLA — works in GCC but not standard C++
// Standard approach: use vector (covered later)
// For now, fixed-size arrays:
int a[100000];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
Array Indexing
Arrays are 0-indexed: the first element is a[0], the last is a[n-1.
// Reverse an array
for (int i = 0; i < n / 2; i++) {
swap(a[i], a[n - 1 - i]);
}
Common Array Patterns
// Prefix sum (precompute running totals)
long long prefix[100001];
prefix[0] = a[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
// Range sum [l, r] in O(1)
long long rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0);
2D Arrays & Row-Major Layout
2D arrays represent grids, matrices, and tables:
int grid[100][100]; // 100x100 grid
// Reading a grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
Row-Major Order
C++ stores 2D arrays in row-major order: grid[0][0], grid[0][1], ..., grid[0][m-1], grid[1][0], .... This means iterating row-by-row is cache-friendly and faster:
// Cache-friendly (fast)
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
// access grid[i][j]
// Cache-unfriendly (slow)
for (int j = 0; j < m; j++)
for (int i = 0; i < n; i++)
// access grid[i][j]
Grid Traversal
Moving in 4 directions (up, down, left, right):
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
// (nx, ny) is a valid neighbor
}
}
std::string & Character Operations
std::string is a dynamic, resizable sequence of characters:
string s = "hello";
string t;
cin >> t; // reads a word
getline(cin, s); // reads a full line
Common String Operations
int len = s.length(); // or s.size()
char first = s[0]; // access by index
s.push_back('!'); // append a character
s += " world"; // append a string
s.substr(2, 3); // substring starting at index 2, length 3
s.find("lo"); // returns index of first occurrence (or string::npos)
s.empty(); // true if length is 0
Iterating Over Characters
// Range-based for (modern C++)
for (char c : s) {
cout << c << " ";
}
// Index-based
for (int i = 0; i < (int)s.length(); i++) {
cout << s[i] << " ";
}
Character Operations & ASCII
Characters are just integers in C++. 'A' is 65, 'a' is 97, '0' is 48:
// Convert lowercase to uppercase
char upper = 'a' - 32; // or: char upper = toupper('a');
// Convert char digit to integer
int digit = '5' - '0'; // digit = 5
// Check if a character is a letter
bool isLetter = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
// Check if a character is a digit
bool isDigit = (c >= '0' && c <= '9');
String to Number Conversion
// String to integer
int n = stoi("123");
// Integer to string
string s = to_string(42);
Summary
- Arrays are 0-indexed;
a[n-1]is the last element - 2D arrays: iterate row-by-row for cache efficiency
- Grid traversal: use
dx/dyarrays for 4-directional movement std::stringsupports indexing,push_back,substr,find- Characters are ASCII integers:
'a' - 'A' == 32,'5' - '0' == 5
Prefer reading offline? Download the full book as a PDF.
Download Free Book