DSA EssentialsCheatsheets, Key Points & Interview Questions

Module 1 – Algorithm and Complexity Fundamentals

Algorithm and Complexity Fundamentals

• An algorithm is a finite, step-by-step procedure for solving a problem.
• A correct algorithm should:
• Accept valid input.
• Produce the required output.
• Terminate after finite steps.
• Be logically correct.
• Use reasonable resources.
• Input size, usually represented by n, determines how an algorithm’s running time grows.
• Time complexity measures how the number of operations grows with input size.
• Space complexity measures additional memory required by an algorithm.
• Auxiliary space means extra memory used apart from the input storage.
• Big-O notation, O(g(n)), gives an asymptotic upper bound.
• Big-Omega notation, Ω(g(n)), gives an asymptotic lower bound.
• Big-Theta notation, Θ(g(n)), gives a tight asymptotic bound.
• Constant factors are ignored in asymptotic analysis.
• For example: 3n2+5n+10=Θ(n2)3n^2+5n+10 = (n^2)3n2+5n+10=Θ(n2)
• Common complexity order from faster to slower: O(1)<O(log⁡n)<O(n2)<O(n3)<O(2n)<O(n!)O(1) < O( n) < O(n) < O(n n) < O(n^2) < O(n^3) < O(2^n) < O(n!)O(1)<O(logn)<O(n2)<O(n3)<O(2n)<O(n!)
• A single loop from 0 to n-1 normally has O(n) complexity.
• Two nested loops each running n times normally have O(n2)O(n^2)O(n2) complexity.
• If the input is repeatedly divided by two, the complexity is usually O(log⁡n)O( n)O(logn).
• Binary search has O(log⁡n)O( n)O(logn) time complexity.
• Merge sort has O(nlog⁡n)O(n n)O(nlogn) time complexity.
• The worst-case time complexity of ordinary quicksort is O(n2)O(n^2)O(n2).
• A recursive algorithm must have a base case.
• Without a valid base case, recursion may continue indefinitely or cause stack overflow.
• Best-case complexity describes the most favorable input arrangement.
• Worst-case complexity describes the least favorable input arrangement.
• Average-case complexity describes expected performance over input distributions.
• A stable sorting algorithm preserves the relative order of equal elements.
• An in-place algorithm uses O(1) or limited extra memory apart from the input.
• A recursive algorithm solves a problem using calls to itself.
• An iterative algorithm uses loops to repeat operations.
• Divide and conquer has three stages:
• Divide.
• Conquer.
• Combine.
• Merge sort and binary search use divide and conquer.
• Dynamic programming is useful when a problem has overlapping subproblems and optimal substructure. The booklet emphasizes asymptotic notation, recurrence analysis, Master Theorem, divide and conquer, dynamic programming, greedy algorithms, and graph algorithms as core algorithm topics.

Arrays

• An array stores elements of the same type in contiguous memory.
• Array indexing generally starts from 0 in C++.
• Accessing an array element by index takes O(1) time.
• Searching an unsorted array takes O(n) time in the worst case.
• Inserting at the beginning of an array takes O(n) because elements must shift.
• Inserting at the end takes O(1) if space is available.
• Deleting from the beginning takes O(n).
• A static array has fixed size.
• A dynamic array can grow or shrink during execution.
• C++ vector is a dynamic array.
• A two-dimensional array is commonly stored in row-major order in C++.
• A prefix sum stores cumulative sums to answer range-sum queries efficiently.
• A sliding window maintains a changing range of elements.
• The two-pointer technique uses two indexes to solve array or string problems efficiently.
• Kadane’s algorithm finds the maximum subarray sum in O(n).
• The Dutch National Flag algorithm sorts 0, 1, and 2 in O(n).
• A majority element appears more than n/2 times.
• Moore’s Voting Algorithm finds a majority element in O(n) time and O(1) extra space.
• Hashing can solve Two Sum in O(n) average time.
• Sorting an array before solving a problem may enable binary search or two-pointer techniques.

Array Code: Maximum Subarray Sum

#include <bits/stdc++.h>
using namespace std;

int maxSubarraySum(const vector<int>& a) {
    int current = a[0];
    int best = a[0];

    for (int i = 1; i < a.size(); i++) {
        current = max(a[i], current + a[i]);
        best = max(best, current);
    }

    return best;
}

int main() {
    vector<int> a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maxSubarraySum(a);
}
Dry Run

Array

-2, 1, -3, 4, -1, 2, 1, -5, 4
Element
	current
	best
	-2
	-2
	-2
	1
	1
	1
	-3
	-2
	1
	4
	4
	4
	-1
	3
	4
	2
	5
	5
	1
	6
	6
	-5
	1
	6
	4
	5
	6

Output

6
The maximum subarray is:

4, -1, 2, 1
Complexity:
* Time: O(n)O(n)O(n).
* Extra space: O(1)O(1)O(1).

Array Code: Move Zeroes to the End

#include <bits/stdc++.h>
using namespace std;

void moveZeroes(vector<int>& a) {
    int position = 0;

    for (int x : a) {
        if (x != 0) {
            a[position++] = x;
        }
    }

    while (position < a.size()) {
        a[position++] = 0;
    }
}

int main() {
    vector<int> a = {0, 1, 0, 3, 12};

    moveZeroes(a);

    for (int x : a)
        cout << x << " ";
}
Dry Run

Initial array

0 1 0 3 12
Non-zero values are copied forward:

1 3 12 _ _
Remaining positions are filled with zero:

1 3 12 0 0
Complexity:
* Time: O(n)O(n)O(n).
* Extra space: O(1)O(1)O(1).

Strings

• A string is a sequence of characters.
• A C-style string ends with the null character '\0'.
• C++ string manages memory automatically.
• String indexing is generally O(1).
• A substring is a contiguous part of a string.
• A subsequence maintains order but does not require contiguity.
• A palindrome reads the same forward and backward.
• Two strings are anagrams if they contain the same characters with the same frequencies.
• A frequency array is useful when characters belong to a small known range.
• A hash map is useful for arbitrary or Unicode characters.
• A sliding window solves many longest-substring problems.
• The longest substring without repeated characters can be solved using a set or frequency map.
• A prefix begins at the first character.
• A suffix ends at the last character.
• A lexicographical comparison compares strings dictionary-wise.
• String concatenation may be expensive when repeated many times.
• s.find(t) returns the starting index of substring t, or string::npos if absent.
• A pangram contains every letter of the alphabet at least once.
• A string can be compressed using character-frequency counts.
• The two-pointer technique can check a palindrome in O(n).

String Code: Palindrome Check

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(const string& s) {
    int left = 0;
    int right = s.size() - 1;

    while (left < right) {
        if (s[left] != s[right])
            return false;

        left++;
        right--;
    }

    return true;
}

int main() {
    cout << boolalpha << isPalindrome("level");
}
Dry Run

String

l e v e l
left
	right
	Comparison
	0
	4
	l == l
	1
	3
	e == e
	2
	2
	Stop

Output

true
Complexity:
* Time: O(n)O(n)O(n).
* Extra space: O(1)O(1)O(1).

String Code: First Non-Repeating Character

#include <bits/stdc++.h>
using namespace std;

char firstNonRepeating(const string& s) {
    unordered_map<char, int> frequency;

    for (char c : s)
        frequency[c]++;

    for (char c : s) {
        if (frequency[c] == 1)
            return c;
    }

    return '#';
}

int main() {
    cout << firstNonRepeating("swiss");
}
Dry Run

String

s w i s s
Frequencies:

s = 3
w = 1
i = 1

Scan again

• s: repeated.
• w: frequency is 1.

Output

w
Complexity:
* Average time: O(n)O(n)O(n).
* Extra space: O(k)O(k)O(k), where kkk is the number of distinct characters.