DSA Practice Problems

Curated problems with detailed explanations, patterns, and intuition

Arrays

Easy

Two Sum

ArrayHashMap

Problem

Given an array of integers and a target, return indices of two numbers that add up to target.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Pattern

Complement Search using HashMap

For a + b = target, if we know a, we need b = target - a. HashMap gives O(1) lookup.

Solution

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.count(complement)) return {seen[complement], i};
        seen[nums[i]] = i;
    }
    return {};
}

Complexity

TimeSpace
O(n)O(n)
Medium

Maximum Subarray (Kadane)

ArrayDP

Problem

Find the contiguous subarray with the largest sum.

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 ([4,-1,2,1])

Pattern

Kadane's Algorithm

At each position: extend previous subarray or start fresh? If previous sum is negative, start fresh.

Solution

int maxSubArray(vector<int>& nums) {
    int curr = nums[0], maxSum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        curr = max(nums[i], curr + nums[i]);
        maxSum = max(maxSum, curr);
    }
    return maxSum;
}

Complexity

TimeSpace
O(n)O(1)
Medium

3Sum

ArrayTwo Pointers

Problem

Find all unique triplets that sum to zero.

Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Pattern

Sort + Two Pointers

Fix one element, use two pointers on remaining sorted array. Skip duplicates.

Solution

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i+1, r = nums.size()-1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++; else r--;
        }
    }
    return res;
}

Complexity

TimeSpace
O(n^2)O(1)
Hard

Trapping Rain Water

ArrayTwo Pointers

Problem

Given elevation map, compute trapped water after rain.

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Pattern

Two Pointers from Ends

Water at i = min(maxLeft, maxRight) - height[i]. Process from both ends, move smaller side.

Solution

int trap(vector<int>& h) {
    int l = 0, r = h.size()-1, lMax = 0, rMax = 0, water = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            h[l] >= lMax ? lMax = h[l] : water += lMax - h[l];
            l++;
        } else {
            h[r] >= rMax ? rMax = h[r] : water += rMax - h[r];
            r--;
        }
    }
    return water;
}

Complexity

TimeSpace
O(n)O(1)
Medium

Product of Array Except Self

ArrayPrefix

Problem

Return array where each element is product of all other elements. No division.

Input: [1,2,3,4]
Output: [24,12,8,6]

Pattern

Prefix and Suffix Products

result[i] = (product of left) * (product of right). Two passes.

Solution

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 1);
    int prefix = 1;
    for (int i = 0; i < n; i++) { res[i] = prefix; prefix *= nums[i]; }
    int suffix = 1;
    for (int i = n-1; i >= 0; i--) { res[i] *= suffix; suffix *= nums[i]; }
    return res;
}

Complexity

TimeSpace
O(n)O(1) extra

Strings

Medium

Longest Substring Without Repeating

StringSliding Window

Problem

Find length of longest substring without repeating characters.

Input: "abcabcbb"
Output: 3 ("abc")

Pattern

Sliding Window with HashMap

Expand right, shrink left when duplicate found. HashMap stores last seen index.

Solution

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> seen;
    int maxLen = 0, left = 0;
    for (int r = 0; r < s.size(); r++) {
        if (seen.count(s[r]) && seen[s[r]] >= left)
            left = seen[s[r]] + 1;
        seen[s[r]] = r;
        maxLen = max(maxLen, r - left + 1);
    }
    return maxLen;
}

Complexity

TimeSpace
O(n)O(charset)
Easy

Valid Anagram

StringHashMap

Problem

Check if two strings are anagrams of each other.

Pattern

Character Frequency Count

Anagrams have same char frequencies. Use array[26] for lowercase.

Solution

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};
    for (int i = 0; i < s.size(); i++) {
        count[s[i]-'a']++;
        count[t[i]-'a']--;
    }
    for (int c : count) if (c != 0) return false;
    return true;
}

Complexity

TimeSpace
O(n)O(1)
Hard

Minimum Window Substring

StringSliding Window

Problem

Find minimum window in s containing all chars of t.

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Pattern

Sliding Window with Frequency Map

Expand to include all chars, shrink to minimize. Track how many chars are satisfied.

Solution

string minWindow(string s, string t) {
    unordered_map<char, int> need, have;
    for (char c : t) need[c]++;
    int required = need.size(), formed = 0;
    int l = 0, minLen = INT_MAX, start = 0;
    for (int r = 0; r < s.size(); r++) {
        have[s[r]]++;
        if (need.count(s[r]) && have[s[r]] == need[s[r]]) formed++;
        while (formed == required) {
            if (r - l + 1 < minLen) { minLen = r - l + 1; start = l; }
            have[s[l]]--;
            if (need.count(s[l]) && have[s[l]] < need[s[l]]) formed--;
            l++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

Complexity

TimeSpace
O(s+t)O(s+t)

Linked Lists

Easy

Reverse Linked List

Linked List

Pattern

Three Pointer Reversal

Use prev, curr, next. Save next, reverse pointer, advance all.

Solution

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr, *curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Complexity

TimeSpace
O(n)O(1)
Easy

Linked List Cycle

Linked ListTwo Pointers

Pattern

Floyd's Tortoise and Hare

Slow moves 1, fast moves 2. If cycle, they meet.

Solution

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Complexity

TimeSpace
O(n)O(1)
Easy

Merge Two Sorted Lists

Linked List

Pattern

Dummy Head + Compare

Use dummy node for edge cases. Compare and link smaller each time.

Solution

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) { tail->next = l1; l1 = l1->next; }
        else { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

Complexity

TimeSpace
O(n+m)O(1)

Stacks and Queues

Easy

Valid Parentheses

Stack

Pattern

Stack for Matching

Push opening brackets, pop and match on closing. LIFO matches nesting.

Solution

bool isValid(string s) {
    stack<char> st;
    unordered_map<char,char> p = {{')','{'},']','['},{'}','{'}};
    for (char c : s) {
        if (p.count(c)) {
            if (st.empty() || st.top() != p[c]) return false;
            st.pop();
        } else st.push(c);
    }
    return st.empty();
}

Complexity

TimeSpace
O(n)O(n)
Medium

Min Stack

StackDesign

Problem

Design stack supporting push, pop, top, getMin in O(1).

Pattern

Auxiliary Stack

Second stack tracks minimum at each level.

Solution

class MinStack {
    stack<int> s, minS;
public:
    void push(int v) { s.push(v); if (minS.empty() || v <= minS.top()) minS.push(v); }
    void pop() { if (s.top() == minS.top()) minS.pop(); s.pop(); }
    int top() { return s.top(); }
    int getMin() { return minS.top(); }
};

Trees

Easy

Maximum Depth of Binary Tree

TreeDFS

Pattern

DFS Recursion

depth = 1 + max(left, right). Base: null returns 0.

Solution

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
Medium

Level Order Traversal

TreeBFS

Pattern

BFS with Level Tracking

Queue + process by level size snapshot.

Solution

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> lvl;
        for (int i = 0; i < sz; i++) {
            auto n = q.front(); q.pop();
            lvl.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(lvl);
    }
    return res;
}
Medium

Validate BST

TreeDFS

Pattern

Range Validation DFS

Each node must be in valid range. Pass min/max bounds down.

Solution

bool isValidBST(TreeNode* r, long mn=LONG_MIN, long mx=LONG_MAX) {
    if (!r) return true;
    if (r->val <= mn || r->val >= mx) return false;
    return isValidBST(r->left, mn, r->val) && isValidBST(r->right, r->val, mx);
}

Graphs

Medium

Number of Islands

GraphDFS

Pattern

Flood Fill DFS

For each unvisited land, DFS to mark entire island. Count DFS starts.

Solution

void dfs(vector<vector<char>>& g, int i, int j) {
    if (i<0||i>=g.size()||j<0||j>=g[0].size()||g[i][j]!='1') return;
    g[i][j] = '0';
    dfs(g,i+1,j); dfs(g,i-1,j); dfs(g,i,j+1); dfs(g,i,j-1);
}
int numIslands(vector<vector<char>>& g) {
    int cnt = 0;
    for (int i=0; i<g.size(); i++)
        for (int j=0; j<g[0].size(); j++)
            if (g[i][j]=='1') { cnt++; dfs(g,i,j); }
    return cnt;
}
Medium

Course Schedule

GraphTopological Sort

Problem

Check if you can finish all courses given prerequisites (detect cycle).

Pattern

Topological Sort / Cycle Detection

Use DFS with visited states (unvisited, visiting, visited) or Kahn's algorithm.

Solution

bool canFinish(int n, vector<vector<int>>& prereqs) {
    vector<vector<int>> g(n);
    vector<int> indegree(n, 0);
    for (auto& p : prereqs) { g[p[1]].push_back(p[0]); indegree[p[0]]++; }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int c = q.front(); q.pop(); cnt++;
        for (int next : g[c]) if (--indegree[next] == 0) q.push(next);
    }
    return cnt == n;
}

Dynamic Programming

Easy

Climbing Stairs

DP

Pattern

Fibonacci DP

dp[n] = dp[n-1] + dp[n-2]. Only need last 2 values.

Solution

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}
Medium

House Robber

DP

Pattern

Include/Exclude DP

At each house: max(skip, rob + best from 2 ago)

Solution

int rob(vector<int>& nums) {
    int prev2 = 0, prev1 = 0;
    for (int n : nums) { int cur = max(prev1, prev2+n); prev2 = prev1; prev1 = cur; }
    return prev1;
}
Medium

Coin Change

DP

Pattern

Unbounded Knapsack

dp[amount] = min coins needed. Try each coin denomination.

Solution

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 c : coins)
            if (c <= i) dp[i] = min(dp[i], dp[i-c]+1);
    return dp[amount] > amount ? -1 : dp[amount];
}
Medium

Longest Common Subsequence

DPString

Pattern

2D DP on Two Sequences

If match: dp[i][j] = dp[i-1][j-1]+1. Else: max of skipping either.

Solution

int longestCommonSubsequence(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}
Hard

Edit Distance

DPString

Problem

Min operations (insert, delete, replace) to convert word1 to word2.

Pattern

2D DP

If match: dp[i][j] = dp[i-1][j-1]. Else: 1 + min(insert, delete, replace).

Solution

int minDistance(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1] : 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
    return dp[m][n];
}

Sorting and Searching

Easy

Binary Search

Binary Search

Pattern

Divide and Conquer

Compare middle, eliminate half. Use left + (right-left)/2 to avoid overflow.

Solution

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int m = l + (r-l)/2;
        if (nums[m] == target) return m;
        if (nums[m] < target) l = m+1; else r = m-1;
    }
    return -1;
}
Medium

Search in Rotated Array

Binary Search

Pattern

Modified Binary Search

One half always sorted. Check which, then determine if target is there.

Solution

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int m = l + (r-l)/2;
        if (nums[m] == target) return m;
        if (nums[l] <= nums[m]) {
            if (target >= nums[l] && target < nums[m]) r = m-1;
            else l = m+1;
        } else {
            if (target > nums[m] && target <= nums[r]) l = m+1;
            else r = m-1;
        }
    }
    return -1;
}
Medium

Merge Intervals

ArraySorting

Pattern

Sort + Greedy Merge

Sort by start. If overlap, extend end. Else add new.

Solution

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto& i : intervals) {
        if (res.empty() || res.back()[1] < i[0]) res.push_back(i);
        else res.back()[1] = max(res.back()[1], i[1]);
    }
    return res;
}