SyntaxPilot
Courses/C++ Coding Questions/Lesson 10
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 10 of 30

Vector questions III

two-sum (brute force vs unordered_map)maximum subarray sum (Kadane, all negative)range sum queries with prefix sums

These are the notes for C++ Coding Questions, episode 10, placement practice for people who finished the SyntaxPilot C++ course. Vectors, part three: three of the most asked interview questions of all time. Two sum with an unordered_map, the maximum subarray sum with Kadane's algorithm, and range sum queries with prefix sums. All three use one idea: remember something useful, so you never redo the work.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.

The test blocks. Nobody can type 500,000 numbers, so the programs have a small test block: when the first number read is 0, the program builds a big input itself (for example 500,000 even numbers). Everything else reads normal input.

Real-life pictures

In real life In C++
A Diwali gift voucher worth exactly ₹500: find two items that use all of it two sum: two numbers that add up to a target
Trying every item with every other item two nested loops, O(n²)
Writing each price in a notebook as you walk the shelf: "this is ₹120, did I already see a ₹380?" an unordered_map from value to index, look up target - x
Raju's chai stall: profit some days, loss on others; the best stretch of days in a row the maximum subarray sum
A running khata that went below zero is only a debt: start a fresh one Kadane's algorithm: cur = max(x, cur + x)
The cricket scoreboard: runs in overs 11 to 20 = score after 20 − score after 10; 0 before the first ball prefix sums: p[r + 1] - p[l], with p[0] = 0

Q1: Two sum

Problem. Given n numbers and a target, print the indexes of two different numbers that add up to the target, or -1 -1 if there are none. n can be 500,000.

Input (n target / numbers) Output
4 9 / 2 7 11 15 0 1
3 6 / 3 2 4 1 2
2 6 / 3 3 0 1
3 10 / 1 2 3 -1 -1

Think out loud. The same number can't be used twice (3 2 4 with target 6 is not 3 + 3). Equal values at different indexes are fine (3 3 with target 6). There may be no answer at all.

The obvious attempt: every pair

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> twoSum(const vector<int>& v, int target) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (v[i] + v[j] == target) return {i, j};
    return {-1, -1};
}

int main() {
    int n, target;
    while (cin >> n >> target) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers, no pair
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = 2 * i;
        }
        auto [i, j] = twoSum(v, target);
        cout << i << " " << j << "\n";
    }
    return 0;
}

Input 4 9 / 2 7 11 15 / 3 6 / 3 2 4 / 2 6 / 3 3 / 3 10 / 1 2 3:

0 1
1 2
0 1
-1 -1

Correct. Now 0 1 (the test block: 500,000 even numbers, target 1, so no pair exists):

Time Limit Exceeded (no output: the program was stopped)

Why. Every pair means n × (n − 1) / 2 checks: about 125 billion for 500,000 numbers.

The idea. For each number x we don't need every other number. We need exactly one: target − x. "Is it there, and at which index?" is what a hash map answers, on average in O(1).

Attempt: put everything in the map first, then look up

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

pair<int, int> twoSum(const vector<int>& v, int target) {
    unordered_map<int, int> pos;          // value -> index
    for (int i = 0; i < (int)v.size(); i++) pos[v[i]] = i;
    for (int i = 0; i < (int)v.size(); i++) {
        auto it = pos.find(target - v[i]);
        if (it != pos.end()) return {i, it->second};
    }
    return {-1, -1};
}

int main() {
    int n, target;
    while (cin >> n >> target) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers, no pair
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = 2 * i;
        }
        auto [i, j] = twoSum(v, target);
        cout << i << " " << j << "\n";
    }
    return 0;
}
0 1
0 0
0 1
-1 -1

The second test prints 0 0: index 0 is the 3, and 3 + 3 = 6, but there is only one 3. The number found itself, because the map already held every value.

Fix: look up first, then insert (one pass)

Walk the numbers once. For each v[i], first look for target - v[i] among the numbers before i, then write v[i] in the map. The map never contains v[i] itself when we look, so a number can't match itself, and 3 3 still works because the first 3 is already in the map when we reach the second.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

pair<int, int> twoSum(const vector<int>& v, int target) {
    unordered_map<int, int> seen;         // value -> index
    for (int i = 0; i < (int)v.size(); i++) {
        auto it = seen.find(target - v[i]);
        if (it != seen.end()) return {it->second, i};
        seen[v[i]] = i;
    }
    return {-1, -1};
}

int main() {
    int n, target;
    while (cin >> n >> target) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers, no pair
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = 2 * i;
        }
        auto [i, j] = twoSum(v, target);
        cout << i << " " << j << "\n";
    }
    return 0;
}
0 1
1 2
0 1
-1 -1

And the 500,000-number test, almost instantly:

-1 -1

Complexity. O(n) time on average (each map lookup and insert is O(1) average, O(n) in the rare worst case), O(n) extra space for the map. A classic trade: memory for speed.

Watch out: target - v[i] can overflow an int when the numbers are near ±2 billion (-2000000000 - 2000000000). For such inputs use long long for the values and the map's key.

Q2: Maximum subarray sum

Problem. A subarray is a block of numbers next to each other, at least one number long. Print the largest sum of any subarray.

Input Output Best block
-2 1 -3 4 -1 2 1 -5 4 6 4 -1 2 1
2 -1 2 -1 2 4 the whole thing
5 5 5
-3 -1 -2 -1 -1

Think out loud. If every number is negative, the answer is the largest single number (not 0: an empty block is not allowed). One number. 500,000 numbers. The sum can be bigger than an int.

The obvious attempt: every block, with a running sum

Every start i, and a running sum that grows as j moves right, so each of the n(n + 1)/2 blocks costs one step (already better than three loops, O(n³)).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxSub(const vector<int>& v) {
    int n = v.size();
    long long best = v[0];
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += v[j];
            best = max(best, sum);
        }
    }
    return best;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
        }
        cout << maxSub(v) << "\n";
    }
    return 0;
}
6
4
5

Correct. Now 0 (500,000 numbers):

Time Limit Exceeded (no output: the program was stopped)

The idea: a running khata (Kadane's algorithm)

Let cur be the best sum of a block that ends at today. Today either joins yesterday's block (cur + x) or starts a fresh block (x). Take the bigger one:

cur  = max(x, cur + x)     // continue, or start fresh
best = max(best, cur)      // the best ever seen

For -2 1 -3 4 -1 2 1: cur goes −2, 1, −2, 4, 3, 5, 6 and best ends at 6. Starting fresh is the same as Raju throwing away a khata that has gone into loss: carrying a debt forward can only make later totals smaller.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxSub(const vector<int>& v) {
    long long best = 0, cur = 0;
    for (int x : v) {
        cur = max(0LL, cur + x);
        best = max(best, cur);
    }
    return best;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
        }
        cout << maxSub(v) << "\n";
    }
    return 0;
}

Input with the all-negative test added (3 / -3 -1 -2):

6
4
5
0

The last answer is 0, but there is no 0 in -3 -1 -2. Starting best at 0 (and resetting cur to 0) quietly allows an empty block. With all losses, taking nothing beats every real block. The question says at least one number.

Fix: start from v[0]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long maxSub(const vector<int>& v) {
    long long best = v[0], cur = v[0];
    for (int i = 1; i < (int)v.size(); i++) {
        cur = max((long long)v[i], cur + v[i]);
        best = max(best, cur);
    }
    return best;
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        if (n == 0) {                    // test: 500,000 numbers
            v.resize(500000);
            for (int i = 0; i < 500000; i++) v[i] = i % 10 - 5;
        }
        cout << maxSub(v) << "\n";
    }
    return 0;
}
6
4
5
-1

And 500,000 numbers (the pattern −5, −4, ..., 4 repeated), instantly:

10

Complexity. O(n) time, one pass. O(1) extra space: two numbers. Sums are long long: 500,000 numbers of up to a billion each don't fit in an int.

Q3: Range sum queries

Problem. Read n numbers, then q questions l r (0-based, inclusive). For each, print v[l] + ... + v[r]. n and q can be 300,000.

Numbers Question Answer
3 1 4 1 5 9 0 2 8
2 5 19
4 4 5

Think out loud. A range starting at 0. A range of one number. Big totals.

The obvious attempt: a loop per question

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    bool big = (n == 0);
    if (big) { n = q = 300000; v.assign(n, 100000); }   // test
    for (int k = 0; k < q; k++) {
        int l = 0, r = n - 1;
        if (!big) cin >> l >> r;
        long long s = 0;
        for (int i = l; i <= r; i++) s += v[i];
        if (!big || k == q - 1) cout << s << "\n";
    }
    return 0;
}
8
19
5

Now 0 0 (the test block: 300,000 numbers of 100,000 each, 300,000 questions over the whole array; it prints only the last answer):

Time Limit Exceeded (no output: the program was stopped)

Why. q questions × up to n numbers each = 90 billion additions.

The idea: the scoreboard, p[i]

Build the running totals once. p[i] = the sum of the first i numbers, and p[0] = 0 (the score before the first ball):

v:  3  1  4  1  5  9
p:  0  3  4  8  9  14  23
sum(l..r) = p[r + 1] - p[l]        sum(2..5) = 23 - 4 = 19

p has n + 1 entries, so a range starting at 0 just subtracts p[0] = 0: no special case.

Attempt: prefix sums in vector<int>

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    bool big = (n == 0);
    if (big) { n = q = 300000; v.assign(n, 100000); }   // test
    vector<int> p(n + 1, 0);
    for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
    for (int k = 0; k < q; k++) {
        int l = 0, r = n - 1;
        if (!big) cin >> l >> r;
        long long s = p[r + 1] - p[l];
        if (!big || k == q - 1) cout << s << "\n";
    }
    return 0;
}
8
19
5

Fast, but the big test prints a negative number:

-64771072

The total should be 300,000 × 100,000 = 30,000,000,000, and an int holds at most 2,147,483,647. Signed overflow is undefined behaviour in C++: the language promises nothing; here it wrapped around like an odometer. Writing long long s = p[r + 1] - p[l] does not help: int - int is computed as an int, already wrong, and only then converted.

Fix: vector<long long>

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    bool big = (n == 0);
    if (big) { n = q = 300000; v.assign(n, 100000); }   // test
    vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
    for (int k = 0; k < q; k++) {
        int l = 0, r = n - 1;
        if (!big) cin >> l >> r;
        long long s = p[r + 1] - p[l];
        if (!big || k == q - 1) cout << s << "\n";
    }
    return 0;
}
8
19
5
30000000000

Complexity. O(n) to build, then O(1) per question: O(n + q) in total. O(n) extra space.

Complexity summary

Program Time Extra space
two sum, two loops O(n²) O(1)
two sum, map filled first O(n) average, but wrong O(n)
two sum, look up then insert O(n) average O(n)
max subarray, every block O(n²) O(1)
max subarray, Kadane O(n) O(1)
range sums, loop per question O(n × q) O(1)
range sums, prefix sums O(n + q) O(n)

The pattern: remember something useful (values seen, the best block ending here, running totals) so the work is never redone.

Common mistakes (and the real results)

Mistake What you see Why Fix
two loops for two sum on big inputs Time Limit Exceeded n² / 2 checks unordered_map, one pass
fill the map first, then look up 3 2 4, target 6 → 0 0 x finds itself look up, then insert
long long best = 0, cur = 0; in Kadane -3 -1 -2 → 0 0 is the empty block start at v[0], loop from 1
int sums in Kadane or prefix sums a negative or wrong total signed overflow (undefined behaviour) long long
long long s = p[r + 1] - p[l] with int p still wrong the subtraction is done in int make p itself long long
p of size n, answer p[r] - p[l - 1] l = 0 reads p[-1] out of bounds (undefined behaviour) size n + 1, p[r + 1] - p[l]

Your turn: count subarrays with sum k (solution)

Problem. Count how many subarrays (blocks of numbers next to each other) add up to k. 1 1 1, k = 2 → 2. 1 2 3, k = 3 → 2 (1 2 and 3).

Idea. A block from l to r adds up to k exactly when p[r + 1] - p[l] == k, that is p[l] == p[r + 1] - k. So walking the prefix sums is two sum again: for each new prefix p, count how many earlier prefixes equal p - k. Store counts (not indexes) in an unordered_map, and start with seen[0] = 1 for the empty prefix. This works with negative numbers too (a sliding window would not).

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long countK(const vector<int>& v, long long k) {
    unordered_map<long long, long long> seen;   // prefix sum -> how many times
    seen[0] = 1;                                // the empty prefix, before the first number
    long long p = 0, count = 0;
    for (int x : v) {
        p += x;
        auto it = seen.find(p - k);
        if (it != seen.end()) count += it->second;
        seen[p]++;
    }
    return count;
}

int main() {
    int n; long long k;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int& x : v) cin >> x;
        cout << countK(v, k) << "\n";
    }
    return 0;
}

Input 3 2 / 1 1 1 / 3 3 / 1 2 3 / 5 0 / 1 -1 1 -1 0:

2
2
7

O(n) average time, O(n) space.

Practice questions (with solutions)

1. Two sum on a sorted vector, without a map. Use two pointers: if the sum is too small, move the left one right; too big, move the right one left.

Solution
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, target;
    while (cin >> n >> target) {
        vector<int> v(n);
        for (int& x : v) cin >> x;          // sorted
        int i = 0, j = n - 1;
        while (i < j && v[i] + v[j] != target) {
            if (v[i] + v[j] < target) i++;   // too small: a bigger left number
            else j--;                         // too big: a smaller right number
        }
        if (i < j) cout << i << " " << j << "\n";
        else cout << "-1 -1\n";
    }
    return 0;
}

Input 5 9 / 1 2 4 5 7 / 4 100 / 1 2 3 4:

1 4
-1 -1

O(n) time, O(1) space. (1 2 4 5 7 has two answers, 2 + 7 and 4 + 5; this finds the first one the pointers meet.)

2. Maximum product subarray. Like Kadane, but a negative number turns the smallest product into the biggest, so keep both.

Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<long long> v(n);
        for (auto& x : v) cin >> x;
        long long hi = v[0], lo = v[0], best = v[0];
        for (int i = 1; i < n; i++) {
            long long x = v[i];
            if (x < 0) swap(hi, lo);          // a negative flips the biggest and the smallest
            hi = max(x, hi * x);
            lo = min(x, lo * x);
            best = max(best, hi);
        }
        cout << best << "\n";
    }
    return 0;
}

Input 4 / 2 3 -2 4 / 3 / -2 0 -1 / 4 / -2 3 -4 1:

6
0
24

O(n) time, O(1) space.

3. Sum of a rectangle with 2D prefix sums. p[i][j] = the sum of the top-left i × j block; a rectangle is one big block minus two strips plus the corner subtracted twice.

Solution
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int r, c, q;
    cin >> r >> c >> q;
    vector<vector<long long>> p(r + 1, vector<long long>(c + 1, 0));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            long long x; cin >> x;
            p[i + 1][j + 1] = x + p[i][j + 1] + p[i + 1][j] - p[i][j];
        }
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;     // 0-based, inclusive corners
        cout << p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1] << "\n";
    }
    return 0;
}

Input: a 3 × 3 grid 1 2 3 / 4 5 6 / 7 8 9, questions 0 0 1 1 and 1 1 2 2:

12
28

O(r × c) to build, O(1) per question.

Mini project: Raju's chai stall report

Read the daily profit or loss, print the best stretch of days (Kadane that also remembers where the block starts and ends), then answer "how much from day a to day b?" questions with prefix sums (1-based days here, like a calendar).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    // best stretch of days (Kadane, remembering where it starts and ends)
    long long best = v[0], cur = v[0];
    int start = 0, bestL = 0, bestR = 0;
    for (int i = 1; i < n; i++) {
        if (cur + v[i] < v[i]) { cur = v[i]; start = i; }
        else cur += v[i];
        if (cur > best) { best = cur; bestL = start; bestR = i; }
    }
    cout << "best stretch: day " << bestL + 1 << " to day " << bestR + 1 << ", profit " << best << "\n";
    // range questions with prefix sums
    vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; i++) p[i + 1] = p[i] + v[i];
    int a, b;
    while (cin >> a >> b)                 // 1-based days, inclusive
        cout << "days " << a << "-" << b << ": " << p[b] - p[a - 1] << "\n";
    return 0;
}

Input 7 / 40 -10 25 -70 30 20 -5, then 1 3, 5 6, 1 7:

best stretch: day 1 to day 3, profit 55
days 1-3: 55
days 5-6: 50
days 1-7: 30

Quick quiz

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {2, -5, 3, 1, -2, 4};
    long long best = v[0], cur = v[0];
    for (int i = 1; i < 6; i++) {
        cur = max((long long)v[i], cur + v[i]);
        best = max(best, cur);
    }
    cout << best;
    return 0;
}

(A) 3 (B) 6 (C) 4 (D) 8

Answer

(B) 6. cur goes 2, −3, then starts fresh at 3, 4, 2, 6. The best block is 3 1 -2 4: the −2 is worth keeping because the 4 after it pays it back.

6

Interview questions

  1. Solve two sum in O(n). One pass with an unordered_map from value to index: look up target - x, then insert x.
  2. Why look up before inserting? So a number can never be matched with itself; the map holds only earlier numbers.
  3. Two sum when the array is sorted? Two pointers from both ends, O(n) time and O(1) space.
  4. Explain Kadane's algorithm. cur is the best block ending at the current index: max(x, cur + x); best is the maximum cur ever seen. O(n), O(1).
  5. What does Kadane return for all-negative input, and how do you make sure? The largest single number; start best and cur at v[0], not 0.
  6. How do you answer many range-sum questions fast? Prefix sums: O(n) once, then p[r + 1] - p[l] in O(1).
  7. Why does the prefix array have n + 1 entries? p[0] = 0 stands for "nothing yet", so a range starting at 0 needs no special case.
  8. Count subarrays with sum k when numbers can be negative. Prefix sums + an unordered_map of prefix counts, starting with {0: 1}. A sliding window only works for non-negative numbers.
  9. Is integer overflow a crash? No: signed overflow is undefined behaviour; usually you just get a wrong number. Use long long for sums.

Glossary

Term Meaning Example
Two sum Find two different elements that add up to a target 2 + 7 = 9 → indexes 0 1
Target The value the two numbers must add up to 9
std::unordered_map Key → value container with no order (a hash table) unordered_map<int, int> seen;
Hash table Finds a key by computing a number (hash) from it O(1) average lookup
find (on a map) Looks for a key without inserting it; returns end() if missing seen.find(target - x)
One pass One walk through the data look up and insert in the same loop
Subarray A block of elements next to each other, at least one 4 -1 2 1 in -2 1 -3 4 -1 2 1
Maximum subarray sum The largest sum of any subarray 6
Kadane's algorithm cur = max(x, cur + x), best = max(best, cur) O(n), O(1)
Empty subarray A block of zero elements, sum 0 (usually not allowed) why best = 0 is wrong
Prefix sum p[i] = sum of the first i elements, p[0] = 0 0 3 4 8 9 14 23
Range sum query The sum of v[l..r] p[r + 1] - p[l]
Inclusive range Both ends are included 2 5 means v[2], v[3], v[4], v[5]
long long A 64-bit integer, up to about 9.2 × 10¹⁸ vector<long long> p
Signed overflow A signed result too big for its type: undefined behaviour 30 billion in an int
Undefined behaviour (UB) Code the C++ standard gives no meaning to: anything can happen p[-1], int overflow
Structured binding auto [i, j] unpacks a pair (C++17) auto [i, j] = twoSum(v, target);
pair<int, int> Two values together return {i, j};
O(n²) Work grows with the square of n every pair
O(n + q) Build once, then constant time per question prefix sums
Time Limit Exceeded (TLE) The judge stopped a program that ran too long two loops on 500,000 numbers

Summary

  • Two sum: for each x, look for target - x in an unordered_map, then insert x. O(n) average, O(n) space. Filling the map first lets a number find itself.
  • Maximum subarray (Kadane): cur = max(x, cur + x), best = max(best, cur), both starting at v[0]. Starting at 0 returns 0 for all-negative input.
  • Range sums: p of size n + 1, p[0] = 0, answer p[r + 1] - p[l] in O(1). Use long long: the overflow happens before the subtraction is stored.
  • Remember something useful, so you never redo the work.

Next episode: Sorting questions: your own comparator for std::sort (and the >= that makes it crash), sorting by two keys with a tie-break and stable_sort, and sorting strings by length, then alphabetically.