10 Classic Coding Test Problems Solved in C++: From Two Sum to Dijkstra

Two Sum

Problem: Find indices of two numbers that sum to target in array.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        
        if (seen.find(complement) != seen.end()) {
            return {seen[complement], i};
        }
        
        seen[nums[i]] = i;
    }
    
    return {};
}
// Time complexity: O(n)
// Space complexity: O(n)

Key Points:

• Use hashmap to store seen numbers
• Check complement before adding current number
• Return immediately when found

The order of the two steps is what makes the one-pass version correct. Looking up the complement before inserting nums[i] prevents an element from pairing with itself (target 6 with a single 3), yet still finds a pair of equal values such as [3, 3], because the first 3 is already in the map when the second arrives. The brute-force double loop is O(n²); sorting plus two pointers is O(n log n) but loses the original indices unless you sort index pairs. The hash map trades O(n) memory for O(n) time, which is the usual trade in these problems.

Two small refinements matter in contests. seen[complement] after find performs a second lookup; reusing the iterator from find avoids it. And unordered_map with default hashing can be pushed into its O(n) worst case by adversarial inputs on judges that allow hacks (Codeforces is known for this); a custom hash with a random seed, or reserving buckets up front, avoids both the attack and rehash costs.

Binary Search

Problem: Find target in sorted array.

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}
// Time complexity: O(log n)

Key Points:

• Use left + (right - left) / 2 to avoid overflow
• left <= right condition (not left < right)
• Update left = mid + 1 or right = mid - 1

Binary search bugs almost always come from mixing two conventions. This version uses a closed interval [left, right]: the loop runs while the interval is non-empty (left <= right), and both updates exclude mid because it has already been checked. The half-open convention [left, right) starts with right = n, loops on left < right, and sets right = mid. Either is correct; combining right = n with left <= right, or right = mid with left <= right, produces an out-of-bounds read or an infinite loop. Pick one and write it the same way every time.

Note that int right = nums.size() - 1 converts size_t to int; for an empty vector, size() - 1 wraps to a huge unsigned value first, and only the conversion back to int happens to rescue it as -1. In practice, most contest problems ask for a boundary (“first index where x ≥ target”) rather than an exact match, and std::lower_bound / upper_bound express that directly without hand-written loops. The hand-written form is still worth knowing for “binary search on the answer” problems, where you search over a numeric range with a feasibility check instead of over an array.

Maximum Subarray

Problem: Find maximum sum of contiguous subarray.

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}
// Kadane's Algorithm
// Time complexity: O(n)

Key Points:

• Kadane’s algorithm: Decide whether to extend or start new at each position
• Track both current sum and max sum
• Handle all negative numbers case

currentSum is the best sum of a subarray that ends at position i. At each step there are only two options — extend the best subarray ending at i−1, or start fresh at i — and starting fresh wins exactly when the previous sum is negative. That is a one-dimensional DP with the table compressed to a single variable. Initializing both variables with nums[0] rather than 0 is what handles the all-negative case: with 0, an input like [-3, -1, -2] would wrongly return 0 (the empty subarray), when the answer is −1. The code assumes a non-empty input; nums[0] on an empty vector is undefined behavior. With values up to 10⁹ and n up to 10⁵, the sum can exceed int, so check the constraints and use long long when needed.

Coin Change

Problem: Find minimum number of coins to make amount.

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}
// Dynamic Programming
// Time complexity: O(amount * coins.size())

Key Points:

• Initialize dp with large value (amount + 1)
• Base case: dp[0] = 0
• Check if solution exists (dp[amount] > amount means impossible)

The sentinel amount + 1 is chosen because no valid answer can need more than amount coins (the smallest coin is at least 1). Using INT_MAX as “infinity” is the tempting alternative, and it is a bug: dp[i - coin] + 1 overflows to a negative number, which then wins the min and corrupts everything after it. If you prefer an explicit infinity, check dp[i - coin] != INF before adding.

Greedy (always take the largest coin) is the obvious first idea and is wrong for arbitrary coin systems: with coins {1, 3, 4} and amount 6, greedy picks 4+1+1 (three coins) while the optimum is 3+3 (two). It happens to be correct for standard currency denominations, which is why it survives casual testing. The DP is unbounded — each coin can be reused — which is why the inner loop reads dp[i - coin] from the same table; compare this with the 0/1 knapsack below, where each item may be used once.

Number of Islands

Problem: Count number of islands in 2D grid.

class Solution {
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || 
            j < 0 || j >= grid[0].size() || 
            grid[i][j] == '0') {
            return;
        }
        
        grid[i][j] = '0';  // Mark visited
        
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
};
// DFS
// Time complexity: O(m * n)

Key Points:

• Mark visited cells to avoid revisiting
• Check boundaries before recursion
• Count each connected component once

Marking cells as '0' inside the grid reuses the input as the visited array and saves O(m·n) memory, at the cost of destroying the input — fine in a contest, surprising in library code. The recursive DFS has a hidden limit: on a 1000×1000 grid that is entirely land, the recursion can go about a million frames deep, and with the typical 1–8 MB default stack that crashes with a segmentation fault (or “stack overflow” on Windows) rather than a clean error. Judges differ in stack size, so a solution that passes locally can crash on submission. Converting to BFS with a queue<pair<int,int>>, or DFS with an explicit stack, removes the depth problem entirely; mark cells as visited when they are pushed, not when popped, or the same cell can be enqueued several times.

Valid Parentheses

Problem: Check if parentheses string is valid.

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
    
    for (char c : s) {
        if (pairs.find(c) == pairs.end()) {
            // Opening bracket
            st.push(c);
        } else {
            // Closing bracket
            if (st.empty() || st.top() != pairs[c]) {
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}
// Time complexity: O(n)

Key Points:

• Use stack for matching pairs
• Check stack not empty before accessing top
• Stack must be empty at end

A counter (++ for open, -- for close) is enough when there is only one bracket type, but with three types it accepts "([)]", which is invalid because the brackets interleave. The stack is needed because matching is last-in, first-out: the most recently opened bracket must close first. Note that the code treats every character that is not a closing bracket as an opening one; if the input may contain letters or spaces, that pushes them on the stack and returns false for valid strings, so check explicitly for (, {, [.

Longest Increasing Subsequence (LIS)

Problem: Find length of longest increasing subsequence.

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}
// Dynamic Programming
// Time complexity: O(n²)
// Optimized version (binary search)
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}
// Time complexity: O(n log n)

Key Points:

• DP solution: For each position, check all previous smaller elements
• Optimized: Use binary search with tails array
• lower_bound finds first element >= num

tails[k] holds the smallest possible last element of an increasing subsequence of length k+1 seen so far. Replacing an element with a smaller one never hurts, because a smaller tail leaves more room for future elements, and the array stays sorted, which is what allows binary search. The common misunderstanding is that tails is an LIS — it is not; its contents can mix elements from different subsequences, and only its length is meaningful. Reconstructing the actual sequence needs an extra array of predecessor indices.

lower_bound gives a strictly increasing subsequence; switching to upper_bound gives the longest non-decreasing one. Mixing these up is a classic wrong answer when the problem statement says “non-decreasing”. With n up to about 5,000 the O(n²) DP is fine; at n = 10⁵ it is 10¹⁰ operations and only the O(n log n) version passes.

0/1 Knapsack

Problem: Find maximum value within maximum weight W.

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][W];
}
// Time complexity: O(n * W)

Key Points:

• 2D DP: dp[i][w] = max value using first i items with weight limit w
• Choice: Take item or skip
• Can optimize to 1D DP

The 1D optimization keeps a single dp[w] array and iterates w from W down to weights[i]. The direction is the whole trick: going downward means dp[w - weights[i]] still holds the value from the previous item row, so each item is used at most once. Iterate upward and you have silently written the unbounded knapsack (the coin-change pattern above), where items can be reused — a bug that produces plausible, too-large answers. O(n·W) is pseudo-polynomial: it depends on the numeric value of W, so with W = 10⁹ the table is impossible, and the problem needs a different formulation (DP over values instead of weights, or meet-in-the-middle for small n).

Shortest Path (Dijkstra)

Problem: Find shortest distances from start node to all nodes.

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, weight] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}
// Time complexity: O((V + E) log V)

Key Points:

• Use min heap (priority queue)
• Skip if already found shorter path
• Works only for non-negative weights

std::priority_queue is a max-heap by default, so greater<> is required to pop the smallest distance first; forgetting it still terminates and gives correct answers on many small tests, but runs far slower because nodes are settled in the wrong order and relaxed repeatedly. The pair is ordered {distance, node} so that comparison uses distance first. Since priority_queue has no decrease-key operation, the code pushes duplicates and discards stale entries with if (d > dist[u]) continue; — remove that line and the algorithm is still correct but can degrade badly on dense graphs.

Negative edge weights break the invariant that a popped node’s distance is final; use Bellman-Ford (or SPFA, with care) for those. With weights up to 10⁹ and paths of many edges, distances exceed int, so vector<long long> with a LLONG_MAX sentinel is the safer default. Unreachable nodes keep INT_MAX; print them as the problem requires (often −1) rather than letting the sentinel leak into output.

Permutation/Combination Generation

Problem: Generate all permutations.

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);  // Backtracking
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    permute(nums, 0, result);
    return result;
}
// Time complexity: O(n!)
// Combination
void combine(int n, int k, int start, vector<int>& current, 
             vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    for (int i = start; i <= n; i++) {
        current.push_back(i);
        combine(n, k, i + 1, current, result);
        current.pop_back();
    }
}

Key Points:

• Backtracking: Swap, recurse, swap back
• Combination: Track start position to avoid duplicates
• Time explodes for large n

The swap-based permutation generator does not emit permutations in lexicographic order and, with duplicate values, produces duplicate permutations. When the problem wants sorted output or distinct results, sorting the input and using std::next_permutation handles both (see next_permutation and prev_permutation); backtracking with a used[] array and a “skip equal neighbours” rule is the alternative when you need pruning. For combinations, a common optimization is to stop the loop once too few numbers remain: i <= n - (k - current.size()) + 1 instead of i <= n, which prunes branches that can never reach size k.

Fast I/O, a Starter Template, and a Debug Macro

I/O Optimization

// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// File I/O
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

sync_with_stdio(false) stops iostreams from synchronizing with C’s stdio buffers after every operation, and cin.tie(nullptr) stops cin from flushing cout before each read. Together they make cin/cout roughly as fast as scanf/printf for large inputs. The catch is that after disabling sync you must not mix printf and cout (or scanf and cin) in the same program — output can appear out of order. Also prefer '\n' over endl: endl flushes every line, which on a million-line output is often the whole difference between accepted and time limit exceeded. The freopen lines are for local testing only; leaving them in a submission usually produces empty output or a runtime error on the judge.

Frequently Used Template

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Code...
    
    return 0;
}

<bits/stdc++.h> is a GCC-specific header that includes the whole standard library. It is convenient in contests and slows compilation, and it does not exist on MSVC or with Clang on macOS by default, so it has no place in production code. Macros like #define ll long long are a contest convention; a using ll = long long; alias does the same thing with proper scoping. In interviews, write the explicit types — readability is part of what is being evaluated.

Debugging Macro

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl
#else
#define debug(x)
#endif
int main() {
    int x = 10;
    debug(x);  // Output only locally
}

Overflow, Out-of-Bounds, and Time Limit Mistakes

Integer overflow

// Wrong: overflows before the assignment
int sum = a * b;
// Right: widen one operand before multiplying
long long sum = (long long)a * b;

Writing long long sum = a * b; does not fix it: the multiplication happens in int and overflows first, then the (already wrong) result is widened. At least one operand must be converted before the operation. Signed overflow is undefined behavior, so the symptom is not reliably a negative number — with optimization the compiler may assume it never happens and remove your checks. Compiling locally with -fsanitize=undefined reports signed integer overflow at the exact line, which is the fastest way to confirm this class of wrong answer.

Array out of bounds

// Wrong: no range check
if (grid[i+1][j] == 1) { ... }
// Right: check first; && short-circuits
if (i+1 < n && grid[i+1][j] == 1) { ... }

Out-of-bounds access on a vector with operator[] is not checked, so it may read garbage and produce a wrong answer instead of crashing. Locally, -D_GLIBCXX_DEBUG (GCC) turns every operator[] into a checked access and aborts with the offending index, which catches these in seconds.

Time limit exceeded

// Too slow: O(n³)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
// Better: improve to O(n²) or O(n log n)

A working rule of thumb is that judges execute on the order of 10⁸ simple operations per second. From the constraint you can therefore read off the intended complexity before writing code: n ≤ 20 suggests 2ⁿ or backtracking, n ≤ 500 allows O(n³), n ≤ 5,000 allows O(n²), and n ≤ 10⁶ needs O(n log n) or O(n). Matching the constraint to a complexity class first is the habit that prevents most time-limit failures; micro-optimizing an O(n²) solution for n = 10⁵ never works.

FAQ

Q1: Which algorithms should I learn first?

A:

1. Sorting, searching
2. Greedy, DP
3. Graph (BFS, DFS)
4. Advanced (segment tree, etc.)

Q2: Cannot solve problem!

A:

1. Start with small example
2. Think brute force first
3. Find patterns
4. Find similar problems

Q3: How to calculate time complexity?

A:

• Single loop: O(n)
• Nested loops: O(n²)
• Binary search: O(log n)
• Sorting: O(n log n)

Q4: Recommended problem sites?

A:

• LeetCode (English)
• HackerRank (English)
• Codeforces (English)
• AtCoder (English/Japanese)

Q5: How long to prepare for coding tests?

A:

• Basics: 1-2 months
• Intermediate: 3-6 months
• Advanced: 6+ months

Q6: Must I know STL?

A: Yes, vector, map, set, algorithm functions are essential.

---

Related Posts

• Array and List | Essential Data Structures for Coding Tests
• Sorting Problems | Coding Test Sorting Patterns
• DP Practice Problems | Coding Test DP Problem Solving Strategy
• Preparing for C++ Coding Interviews: 7 Problem Types, Must-Know STL and a Day-Of Checklist
• C++ Algorithm Guide

---