Skip to content
DSA advanced 14 min read

Advanced Data Structures: Answer Sheet & Solutions

This is the answer sheet for the advanced exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here.

Q1. Number of Provinces

Idea: Each city starts in its own set. Union every directly connected pair; the number of provinces is the number of distinct roots left. Start a counter at n and decrement on every successful union (one that actually merged two different sets).

Complexity: O(n²·α(n)) time, O(n) space.

int findCircleNum(std::vector<std::vector<int>>& isConnected) {
    int n = isConnected.size();
    std::vector<int> parent(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    std::function<int(int)> find = [&](int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    };
    int provinces = n;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isConnected[i][j]) {
                int ra = find(i), rb = find(j);
                if (ra != rb) { parent[ra] = rb; provinces--; }
            }
    return provinces;
}

Pitfall: Counting edges instead of merges over-counts. Only decrement when the two endpoints had different roots, otherwise a redundant edge wrongly lowers the count.

Q2. Redundant Connection

Idea: Add edges one by one with union-find. An edge whose two endpoints are already in the same set would create a cycle — that’s the redundant one. Because we process edges in input order and return at the first such edge, we naturally get the last edge that completes a cycle for a single-extra-edge graph.

Complexity: O(n·α(n)) time, O(n) space.

std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
    int n = edges.size();
    std::vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++) parent[i] = i;
    std::function<int(int)> find = [&](int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    };
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra == rb) return e;       // already connected -> cycle
        parent[ra] = rb;
    }
    return {};
}

Pitfall: Nodes are labeled 1..n, so size the parent array n + 1 and skip index 0, or you’ll read out of bounds.

Q3. Range Sum Query — Mutable

Idea: A Fenwick tree gives O(log n) prefix sums with point updates. Keep a copy of the current values so an update can apply the delta value - old. sumRange(l, r) = prefix(r+1) - prefix(l) (the tree is 1-indexed).

Complexity: O(log n) per update/sumRange, O(n log n) to build, O(n) space.

class NumArray {
    std::vector<int> nums;
    std::vector<long long> tree;
    int n;
    void add(int i, long long delta) {          // 1-indexed
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }
    long long prefix(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i)) s += tree[i];
        return s;
    }
public:
    NumArray(std::vector<int>& a) : nums(a), tree(a.size() + 1, 0), n(a.size()) {
        for (int i = 0; i < n; i++) add(i + 1, a[i]);
    }
    void update(int index, int value) {
        add(index + 1, (long long)value - nums[index]);
        nums[index] = value;
    }
    int sumRange(int left, int right) {
        return (int)(prefix(right + 1) - prefix(left));
    }
};

Pitfall: update sets a value; the Fenwick tree only knows how to add. Apply the delta value - old and remember to store the new value, or every later update drifts.

Q4. Design an LRU Cache

Idea: Pair a hash map (O(1) lookup) with an ordering that supports O(1) move-to-front and drop-from-back. C++/Java use an explicit doubly linked list; JS Map and Python OrderedDict give the ordering for free.

Complexity: O(1) per get/put, O(capacity) space.

#include <list>
#include <unordered_map>
class LRUCache {
    int cap;
    std::list<std::pair<int,int>> items;          // front = most recent
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> pos;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;
        items.splice(items.begin(), items, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }
        if ((int)items.size() == cap) {
            pos.erase(items.back().first);
            items.pop_back();
        }
        items.emplace_front(key, value);
        pos[key] = items.begin();
    }
};

Pitfall: A get is a use — forgetting to move the entry to the front corrupts the eviction order. Also remember to delete the evicted key from the map, not just the list.

Q5. Implement strStr() (KMP)

Idea: Build the KMP prefix table for needle, then scan haystack once. On a mismatch, fall back via the table instead of restarting, so the haystack pointer never moves backward — O(n + m).

Complexity: O(n + m) time, O(m) space.

int strStr(const std::string& haystack, const std::string& needle) {
    int m = needle.size();
    if (m == 0) return 0;
    std::vector<int> lps(m, 0);
    for (int i = 1, len = 0; i < m; ) {
        if (needle[i] == needle[len]) lps[i++] = ++len;
        else if (len > 0)             len = lps[len - 1];
        else                          lps[i++] = 0;
    }
    for (int i = 0, j = 0; i < (int)haystack.size(); i++) {
        while (j > 0 && haystack[i] != needle[j]) j = lps[j - 1];
        if (haystack[i] == needle[j]) j++;
        if (j == m) return i - m + 1;
    }
    return -1;
}

Pitfall: Decide the empty-needle policy explicitly (here it returns 0). Forgetting it can cause an out-of-bounds read on needle[0].

Q6. Repeated Substring Pattern

Idea: Build the prefix function and look at its last value k = lps[n-1] — the longest proper prefix that is also a suffix. The shortest repeating unit has length n - k. The string is a repetition iff k > 0 and n is divisible by n - k.

Complexity: O(n) time, O(n) space.

bool repeatedSubstringPattern(const std::string& s) {
    int n = s.size();
    std::vector<int> lps(n, 0);
    for (int i = 1, len = 0; i < n; ) {
        if (s[i] == s[len]) lps[i++] = ++len;
        else if (len > 0)   len = lps[len - 1];
        else                lps[i++] = 0;
    }
    int k = lps[n - 1];
    return k > 0 && n % (n - k) == 0;
}

Pitfall: The k > 0 guard is essential — without it a string of all-distinct characters (where k = 0, so n - k = n) would wrongly report true since n % n == 0.

Q7. Count of Smaller Numbers After Self

Idea: Process the array right to left, inserting each value into a Fenwick tree keyed by rank (coordinate-compressed value). Before inserting nums[i], query the count of already-seen values with a strictly smaller rank — those are the smaller elements to its right.

Complexity: O(n log n) time, O(n) space.

std::vector<int> countSmaller(std::vector<int>& nums) {
    std::vector<int> sorted = nums;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();
    std::vector<int> tree(m + 1, 0);
    auto add = [&](int i) { for (; i <= m; i += i & (-i)) tree[i]++; };
    auto query = [&](int i) { int s = 0; for (; i > 0; i -= i & (-i)) s += tree[i]; return s; };
    std::vector<int> res(nums.size());
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        int rank = std::lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1;
        res[i] = query(rank - 1);   // strictly smaller
        add(rank);
    }
    return res;
}

Pitfall: Query rank - 1, not rank — including the current value’s own rank would count equal elements as smaller. Coordinate-compress first so the Fenwick tree size depends on the number of distinct values, not the value range.

That’s the full answer sheet. Back to the advanced exercises or explore the problem-solving patterns.

Last updated June 25, 2026
Was this helpful?