DSA C++ Revision

🧠

Core Concepts

Foundation you must know cold

What is an Array?

A contiguous block of memory storing elements of the same type. The base address + index gives direct access to any element in O(1) time.

C++ Declaration

int arr[5] = {1,2,3,4,5};  // static
vector<int> v = {1,2,3};       // dynamic
int* p = new int[10];          // heap alloc

Memory Layout

Elements are stored sequentially. arr[i] translates to base_addr + i × sizeof(type). This makes iteration cache-friendly.

💡 Cache locality makes array iteration ~10× faster than linked list traversal on modern CPUs.

Static Array

Fixed size, stack memory. Use when size is known at compile time.

int a[100];

Dynamic Array

Heap memory, resizable. vector doubles capacity on overflow — amortized O(1) push.

vector<int> v;

2D Array

Row-major storage. Access: a[r][c]. Prefer row iteration for cache hits.

int a[n][m];

⏱️

Time & Space Complexity

Know these by heart

Operation	Average	Worst	Notes
Access `arr[i]`	O(1)	O(1)	Direct address computation
Search (unsorted)	O(n)	O(n)	Linear scan
Search (sorted, binary)	O(log n)	O(log n)	Requires sorted array
Insert at end	O(1)	O(n)	Amortized O(1) for vector
Insert at index i	O(n)	O(n)	Shift elements right
Delete at end	O(1)	O(1)	Just decrement size
Delete at index i	O(n)	O(n)	Shift elements left
Sorting	O(n log n)	O(n²)	Quicksort avg / worst

⚠️ Space complexity is O(n) for storing n elements. Most algorithms use O(1) extra space — always mention this in interviews.

🔷

Algorithmic Patterns

Master these 8 patterns → solve 90% of array problems

01 Two Pointer

O(n) O(1) space ›

Time

O(n)

Space

O(1)

Requires

Sorted / Converging

Use two indices that move toward each other (opposite ends) or in the same direction. Eliminates the need for nested loops in many problems.

When to use: Pair sum, triplet sum, palindrome check, container with most water, removing duplicates.

C++ Two Sum (Sorted) — Opposite Ends

// Find pair summing to target in sorted array
bool twoSum(vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int sum = arr[l] + arr[r];
        if (sum == target) return true;
        else if (sum < target) l++;
        else r--;
    }
    return false;
}

// Remove duplicates from sorted array — same direction
int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < arr.size(); fast++) {
        if (arr[fast] != arr[slow])
            arr[++slow] = arr[fast];
    }
    return slow + 1;
}

02 Sliding Window

O(n) Fixed + Variable ›

Time

O(n)

Space

O(1) / O(k)

Type

Fixed / Variable

Maintain a window over the array. Expand right, shrink left based on conditions. Converts O(n²) brute force to O(n).

C++ Fixed Window — Max Sum of K Elements

int maxSumFixed(vector<int>& a, int k) {
    int n = a.size(), wsum = 0;
    for (int i = 0; i < k; i++) wsum += a[i]; // first window
    int best = wsum;
    for (int i = k; i < n; i++) {
        wsum += a[i] - a[i-k];            // slide
        best = max(best, wsum);
    }
    return best;
}

C++ Variable Window — Smallest Subarray ≥ S

int minLenSubarray(vector<int>& a, int s) {
    int n = a.size(), l = 0, sum = 0, res = INT_MAX;
    for (int r = 0; r < n; r++) {
        sum += a[r];
        while (sum >= s) {
            res = min(res, r - l + 1);
            sum -= a[l++];              // shrink left
        }
    }
    return (res == INT_MAX) ? 0 : res;
}

03 Prefix Sum

Range Queries O(1) Preprocessing O(n) ›

Build

O(n)

Query

O(1)

Space

O(n)

Precompute cumulative sums. Range sum [l,r] = pre[r] - pre[l-1]. Also use prefix XOR, product, max/min.

C++ Prefix Sum + Subarray Sum = K (HashMap Trick)

// Build prefix
vector<int> buildPrefix(vector<int>& a) {
    int n = a.size();
    vector<int> pre(n+1, 0);
    for (int i = 0; i < n; i++) pre[i+1] = pre[i] + a[i];
    return pre;
}
// Range query: sum [l, r] (0-indexed)
// Answer = pre[r+1] - pre[l]

// Count subarrays with sum = k
int subarraySum(vector<int>& a, int k) {
    unordered_map<int,int> freq; freq[0] = 1;
    int psum = 0, cnt = 0;
    for (int x : a) {
        psum += x;
        cnt += freq[psum - k];  // key insight!
        freq[psum]++;
    }
    return cnt;
}

04 Kadane's Algorithm

O(n) Max Subarray ›

Time

O(n)

Space

O(1)

Variant

Circular + Product

DP on arrays. If current sum becomes negative, start fresh. Key insight: curMax = max(a[i], curMax + a[i]).

C++ Kadane's — Max Subarray Sum + Subarray Printing

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

// Max circular subarray — Kadane variant
int maxCircular(vector<int>& a) {
    int total = 0, maxSum = a[0], minSum = a[0];
    int curMax = 0, curMin = 0;
    for (int x : a) {
        curMax = max(x, curMax + x);  maxSum = max(maxSum, curMax);
        curMin = min(x, curMin + x);  minSum = min(minSum, curMin);
        total += x;
    }
    return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
}

// Max product subarray
int maxProduct(vector<int>& a) {
    int maxP = a[0], minP = a[0], res = a[0];
    for (int i = 1; i < (int)a.size(); i++) {
        if (a[i] < 0) swap(maxP, minP); // flip on negative
        maxP = max(a[i], maxP * a[i]);
        minP = min(a[i], minP * a[i]);
        res  = max(res, maxP);
    }
    return res;
}

05 Hashing

O(1) lookup O(n) space ›

Use unordered_map / unordered_set to trade space for time. Reduces O(n²) to O(n) in frequency, duplicate, and lookup problems.

C++ Longest Consecutive Sequence — O(n)

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> st(nums.begin(), nums.end());
    int best = 0;
    for (int x : st) {
        if (!st.count(x - 1)) { // sequence start
            int len = 1;
            while (st.count(x + len)) len++;
            best = max(best, len);
        }
    }
    return best;
}

06 Moore's Voting Algorithm

O(n) O(1) space ›

Find majority element (appears > n/2 times) in O(n) time and O(1) space. Cancel out different elements — majority survives.

C++ Majority Element — Boyer-Moore Voting

int majorityElement(vector<int>& a) {
    int cand = a[0], cnt = 1;
    for (int i = 1; i < (int)a.size(); i++) {
        if (cnt == 0) { cand = a[i]; cnt = 1; }
        else if (a[i] == cand) cnt++;
        else cnt--;
    }
    // Verify candidate if majority not guaranteed
    int freq = count(a.begin(), a.end(), cand);
    return (freq > (int)a.size()/2) ? cand : -1;
}

// Majority II: elements appearing > n/3 times (at most 2 candidates)
vector<int> majorityII(vector<int>& a) {
    int c1 = 0, c2 = 1, cnt1 = 0, cnt2 = 0;
    for (int x : a) {
        if (x == c1) cnt1++;
        else if (x == c2) cnt2++;
        else if (!cnt1) { c1 = x; cnt1 = 1; }
        else if (!cnt2) { c2 = x; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    vector<int> res;
    if (count(a.begin(),a.end(),c1)>(int)a.size()/3) res.push_back(c1);
    if (count(a.begin(),a.end(),c2)>(int)a.size()/3) res.push_back(c2);
    return res;
}

07 Binary Search on Answer

O(n log n) Advanced ›

Binary search isn't just for sorted arrays. Search on the answer space when you can define a monotonic predicate. Key: lo=min_ans, hi=max_ans.

C++ Allocate Min Pages — Binary Search on Answer

auto feasible = [&](vector<int>& pages, int m, int mid) {
    int students = 1, cur = 0;
    for (int p : pages) {
        if (p > mid) return false;
        if (cur + p > mid) { students++; cur = p; }
        else cur += p;
    }
    return students <= m;
};

int allocateMinPages(vector<int>& pages, int m) {
    int lo = *max_element(pages.begin(), pages.end());
    int hi = accumulate(pages.begin(), pages.end(), 0);
    int ans = hi;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(pages, m, mid)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

08 Dutch National Flag

O(n) 3-way partition ›

Partition array into three groups in a single pass using lo, mid, hi pointers. Classic: Sort array of 0s, 1s, 2s.

C++ Sort Colors (0,1,2) — Single Pass

void sortColors(vector<int>& a) {
    int lo = 0, mid = 0, hi = (int)a.size() - 1;
    while (mid <= hi) {
        if (a[mid] == 0)      swap(a[lo++], a[mid++]);
        else if (a[mid] == 1) mid++;
        else                   swap(a[mid], a[hi--]); // don't mid++!
    }
}

⚙️

STL Toolkit

Essential functions — use them, don't rewrite them

vector<int> essentials

C++ Vector Operations

v.push_back(x);     // O(1) amortized
v.pop_back();        // O(1)
v.size();            // O(1)
v.resize(n, 0);     // O(n)
v.assign(n, val);   // fill
v.insert(it, x);    // O(n)
v.erase(it);        // O(n)
v.clear();           // O(n)
v.empty();           // O(1)
v.front(); v.back(); // O(1)

<algorithm> for arrays

C++ Algorithm Functions

sort(v.begin(), v.end());         // O(n log n)
sort(v.begin(), v.end(), greater<int>());
reverse(v.begin(), v.end());
rotate(v.begin(), v.begin()+k, v.end());
unique(v.begin(), v.end());         // needs sort first
lower_bound(v.begin(), v.end(), x); // O(log n)
upper_bound(v.begin(), v.end(), x);
*max_element(v.begin(), v.end());
accumulate(v.begin(), v.end(), 0);
count(v.begin(), v.end(), val);
fill(v.begin(), v.end(), 0);
next_permutation(v.begin(), v.end());

unordered_map tricks

C++ HashMap

unordered_map<int,int> mp;
mp[key]++;              // auto init to 0
mp.count(key);         // 1 if exists
mp.find(key);          // iterator
mp.erase(key);
for (auto& [k,v] : mp)  // C++17 structured binding
    cout << k << " " << v;

// Frequency map from array
unordered_map<int,int> freq;
for (int x : arr) freq[x]++;

Useful one-liners

C++ Handy Snippets

// init vector of size n with 0
vector<int> v(n, 0);

// 2D grid n×m filled with -1
vector<vector<int>> dp(n, vector<int>(m, -1));

// Print vector
for (int x : v) cout << x << " ";

// Copy vector
vector<int> copy(v.begin(), v.end());

// Dedup sorted vector
v.erase(unique(v.begin(),v.end()),v.end());

🎯

Must-Solve Problems

Sorted by pattern — solve in this order

#	Problem	Pattern	Difficulty	Key Idea
1	Two SumLeetCode 1	Hashing	Easy	Store complement in map
2	Max SubarrayLeetCode 53	Kadane	Easy	Reset if cur < 0
3	Best Time to Buy StockLeetCode 121	Greedy	Easy	Track min so far
4	Container With Most WaterLeetCode 11	Two Pointer	Medium	Move shorter pointer inward
5	3SumLeetCode 15	Two Pointer	Medium	Sort + fix one, two-pointer rest
6	Subarray Sum = KLeetCode 560	Prefix Sum	Medium	pre[r]−pre[l]=k → map freq
7	Longest Subarray ≤ KSliding Window	Sliding Window	Medium	Variable window expand/shrink
8	Product of Array Except SelfLeetCode 238	Prefix/Suffix	Medium	Left product × right product
9	Find Duplicate NumberLeetCode 287	Floyd's Cycle	Medium	Array as linked list, detect cycle
10	Majority Element IILeetCode 229	Moore Voting	Medium	2 candidates, verify at end
11	Trapping Rain WaterLeetCode 42	Two Pointer	Hard	min(leftMax, rightMax) − h[i]
12	Merge K Sorted ArraysHeap	Priority Queue	Hard	Min heap of (val, arr, idx)

💼

Interview Tips

What interviewers actually look for

🎯 Always clarify constraints first. Ask: sorted or unsorted? Can values be negative? Duplicate elements allowed? What's the size of n? This shows structured thinking.
🧩 State your brute force first. Mention O(n²) or O(n³) upfront, then optimize. Shows problem decomposition, and gives a fallback if you get stuck.
📊 Walk through edge cases out loud. Empty array, single element, all negatives, all same elements, integer overflow with n > 10⁵.
⚡ Recognize the pattern by constraint. O(n) forced → Two Pointer or Sliding Window. O(1) space → In-place manipulation. Range queries → Prefix Sum. Sorted → Binary Search.
📝 Always mention space complexity. Especially when using extra arrays or hashmaps. Interviewers often follow up asking for O(1) space solution.
🔄 For Two Pointer, state the invariant. What does each pointer represent? What condition moves which pointer? This prevents infinite loops and off-by-one errors.
🏁 Dry run on a small example. Before coding, trace through arr = [2,3,1,5] mentally. This catches bugs before writing code — saves you 10 mins of debugging.

⚠️

Common Mistakes

Every beginner makes these — you won't after today

🚫 Off-by-one in binary search. Always use lo + (hi - lo) / 2 to avoid overflow. Decide carefully: lo = mid+1 vs lo = mid, hi = mid-1 vs hi = mid.
🚫 Accessing arr[-1] or arr[n]. Always check bounds before accessing. Use: if (i >= 0 && i < n). Very common in sliding window and two pointer.
🚫 Integer overflow in prefix sum. When arr values can be up to 10⁹ and n up to 10⁵, use long long for prefix arrays. int max is ~2.1×10⁹.
🚫 Forgetting to handle empty array. Many solutions crash on n = 0. Always add: if (a.empty()) return 0; or if (n == 0) ....
🚫 Using sort() when not needed. Sorting is O(n log n) and costs precious time. If the problem can be solved in O(n) with hashing or two pointer, avoid sorting.
🚫 Not using (int) cast for size(). vector::size() returns size_t (unsigned). size() - 1 on empty vector wraps to a huge number. Cast to int.
🚫 Sliding window: not advancing mid++ in Dutch Flag. When swapping with hi, don't increment mid — the swapped element hasn't been evaluated yet.
🚫 Using map instead of unordered_map. map is O(log n) per operation. unordered_map is O(1) avg. For n = 10⁵, this can be the difference between AC and TLE.

⚡

Quick Revision Cheat Sheet

Last-minute review before your interview

Pattern → Use When

Two Sum / PairHashing or Two Ptr

Subarray sumPrefix Sum + Map

Max/min windowSliding Window

Sorted + targetBinary Search

Majority elementMoore Voting

Partition 3 typesDutch National Flag

Complexity Quick Ref

AccessO(1)

Linear scanO(n)

Binary searchO(log n)

SortO(n log n)

Brute subarrayO(n²)

Prefix buildO(n)

Edge Cases Checklist

Empty arrayn = 0 → return early

Single elementn = 1 check

All same elementsDedup logic

All negativesInit = a[0] not 0

OverflowUse long long

size() - 1Cast to (int)

STL Quick Fire

Sort descendinggreater<int>()

Max element*max_element(b,e)

Sum of arrayaccumulate(b,e,0)

Count occurrencescount(b,e,val)

First ≥ x in sortedlower_bound

Rotate left by krotate(b,b+k,e)

🚀

Next Topics Coming Soon: Strings → Linked List → Stack & Queue → Trees → Graphs → DP

Arrays — The Foundation