Arrays, strings and hashing

Arrays and dynamic arrays

Also called list, ArrayList, vector, resizable array, dynamic array

What

An array stores items side by side in memory, so reading or writing index i is O(1). A dynamic array grows by allocating a bigger block and copying, so appending is O(1) amortised, while inserting or removing in the middle is O(n).

Why

It is the default container for sequences and the backing store for strings, stacks and heaps. Its contiguous layout also makes it fast in practice thanks to the CPU cache.

vector<int> nums{3, 1, 4};
nums.push_back(1);             // amortised O(1)
nums[0] = 9;                   // O(1)
nums.insert(nums.begin(), 2);  // O(n): shifts every item
nums.pop_back();               // O(1) at the end
nums.erase(nums.begin());      // O(n) at the front

Strings

What

A string is a sequence of characters. In Python, Java and JavaScript strings are immutable, so every change builds a new string; C++ std::string is mutable. Taking a substring or slice copies it, costing O(k) for k characters.

Why

String problems are array problems with extra costs hidden in concatenation, slicing and comparison, and those costs decide whether a solution is O(n) or O(n^2).

string result;
for (const string& word : words) {
  result += word;              // amortised O(word length)
}
s[0] = 'X';                    // std::string is mutable
string sub = s.substr(1, 3);   // copies 3 characters

Hash maps

Also called hash table, dictionary, dict, HashMap, unordered_map, Map

What

A hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete. Collisions are handled by chaining or probing, and the table resizes as it fills.

Why

It is the first tool for counting, grouping, caching and checking whether you have seen something before in one pass, often turning an O(n^2) search into O(n).

unordered_map<string, int> counts;
for (const string& w : words) {
  counts[w]++;                 // missing keys start at 0
}
if (auto it = counts.find("apple"); it != counts.end()) {
  int apples = it->second;
}

Hash sets

Also called set, HashSet, unordered_set, Set

What

A hash set stores unique keys without values, with O(1) average add, remove and membership check.

Why

Use it for de-duplication, visited markers and membership checks. Checking membership in a list is O(n); in a set it is O(1) on average.

bool hasDuplicate(const vector<int>& nums) {
  unordered_set<int> seen;
  for (int x : nums) {
    if (!seen.insert(x).second) return true;
  }
  return false;
}

Composite and custom keys

Also called tuple key, pair key, composite key

What

When a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value. Each language has a safe choice: tuples, records, packed integers or joined strings.

Why

Visited sets on grids and grouping anagrams depend on it, and a wrong key type fails silently by never matching.

set<pair<int, int>> visited;       // ordered, O(log n)
visited.insert({r, c});
unordered_set<long long> fast;     // pack into one number
fast.insert(1LL * r * cols + c);
unordered_map<string, vector<string>> groups;
string key = word;
ranges::sort(key);
groups[key].push_back(word);

Prefix sums

Also called cumulative sum, running total

What

A prefix sum array stores running totals, so prefix[i] is the sum of the first i items. The sum of any range i..j is prefix[j + 1] - prefix[i]: O(1) per query after an O(n) build.

Why

It answers many range-sum queries fast, and combined with a hash map of earlier prefix values it counts subarrays with a given sum in O(n), even with negative numbers.

vector<long long> prefix(nums.size() + 1, 0);
for (size_t i = 0; i < nums.size(); ++i) {
  prefix[i + 1] = prefix[i] + nums[i];
}
long long rangeSum = prefix[j + 1] - prefix[i];  // nums[i..j]

Integer limits and overflow

Also called overflow, MAX_SAFE_INTEGER, INT_MAX, integer overflow

What

Java and C++ int holds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour. JavaScript numbers are exact integers only up to 2^53 - 1. Python integers grow without limit.

Why

Sums, products and midpoints of large values overflow quietly and give wrong answers with no error, a common cause of failing hidden tests.

int mid = lo + (hi - lo) / 2;   // lo + hi can overflow
long long area = 1LL * w * h;   // widen before multiplying
int mx = INT_MAX;               // 2^31 - 1
int q = -7 / 2;                 // -3: truncates toward zero
int r = ((-7 % 2) + 2) % 2;     // 1, while -7 % 2 is -1

C++ standard containers

Also called STL, vector, unordered_map, priority_queue

What

vector is the dynamic array, unordered_map and unordered_set are hash tables, deque, stack and queue cover the ends, priority_queue is a max-heap by default, and map and set are balanced trees with lower_bound.

Why

Matching each structure to its container, and knowing each call cost, is what keeps C++ solutions fast. The snippets on this sheet assume the standard headers and using namespace std.

vector<int> stack;                  // push_back, back, pop_back
deque<int> dq;                      // O(1) at both ends
queue<int> q;                       // push, front, pop
unordered_map<string, int> counts;  // O(1) average
map<int, string> sorted;            // red-black tree
auto it = sorted.lower_bound(5);    // first key >= 5
priority_queue<int> maxHeap;        // max-heap by default
priority_queue<int, vector<int>, greater<>> minHeap;