Data Structures & Algorithms

• 1: Data Structures
• 1.1: Stack
• 1.2: Queue / Deque
• 1.3: Heap
• 1.4: Binary Tree
• 1.4.1: 199. Binary Tree Right Side View
• 1.5: Linked List
• 1.6: Binary Search Tree
• 1.7: Bitset
• 2: Techniques
• 2.1: Two Pointers
• 2.2: Binary Search
• 2.3: Binary Search on the Answer
• 2.4: Binary Search on Float & Ternary Search
• 2.5: Greedy
• 2.6: Recursion + Backtracking
• 2.7: Divide and Conquer

1 - Data Structures

Collection of LeetCode solutions categorized by fundamental data structures:

• Stack
• Queue / Deque
• Heap
• Binary Tree
• Linked List
• Binary Search Tree (set / multiset) / (map / multimap)
• Bitset

1.1 - Stack

A stack is a Last-In-First-Out (LIFO) data structure that supports two main operations: push (insertion) and pop (deletion). In C++, you can use the built-in stack container from the Standard Template Library (STL).

Basic Stack Operations in C++

#include <stack>

// Declaration
stack<long long> mystack;  // Create an empty stack of long long integers

// Basic Operations
// 1. push(value) - Add element to top of stack - O(1)
mystack.push(6);  // mystack = [6]
mystack.push(3);  // mystack = [6, 3]
mystack.push(9);  // mystack = [6, 3, 9]

// 2. pop() - Remove element from top of stack - O(1)
mystack.pop();    // Removes 9, mystack = [6, 3]

// 3. top() - Get value of top element - O(1)
int topValue = mystack.top();  // Returns 3

// 4. size() - Get number of elements in stack - O(1)
int stackSize = mystack.size();  // Returns 2

// 5. empty() - Check if stack is empty - O(1)
bool isEmpty = mystack.empty();  // Returns false

Important Notes:

• Always check if stack is not empty before calling pop() or top()
• Stack has constant time O(1) complexity for all basic operations
• Stack is particularly useful for:
  • Function call management
  • Expression evaluation
  • Backtracking algorithms
  • Undo operations
  • Parentheses matching

Common Mistakes to Avoid:

1. Calling pop() or top() on empty stack
2. Not including <stack> header
3. Forgetting that pop() doesn’t return the removed value

Example Usage:

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

int main() {
    stack<int> st;
    
    // Push elements
    st.push(1);
    st.push(2);
    st.push(3);
    
    // Safe way to process stack
    while (!st.empty()) {
        cout << st.top() << " ";  // Print top element
        st.pop();                 // Remove top element
    }
    // Output: 3 2 1
    
    return 0;
}

Problems that demonstrate the effective use of stack data structure to solve algorithmic challenges.

1.2 - Queue / Deque

Problems that demonstrate the effective use of queue and double-ended queue data structures to solve algorithmic challenges.

1.3 - Heap

Problems that demonstrate the effective use of heap data structure (priority queue) to solve algorithmic challenges.

1.4 - Binary Tree

Problems that demonstrate the effective use of binary tree data structure to solve algorithmic challenges.

1.4.1 - 199. Binary Tree Right Side View

Problem Description

LeetCode Problem Link

Given the root of a binary tree, imagine yourself standing on the right side of it. Return the values of the nodes you can see ordered from top to bottom.

Constraints:

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100

Example:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The nodes visible from the right side are 1, 3, and 4.

Intuition and Approach

Intuition

When viewing a binary tree from the right side, we want to see the rightmost node at each level. Using a queue for level-order traversal (BFS), we can capture the last node at each level to build our right-side view.

Approach

1. Use a queue to perform level-order traversal
2. For each level:
   • Get the current level size
   • Process all nodes at this level
   • Add the last node’s value to our result
3. Return the collected right-side values

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    result := []int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // If it's the last node in current level, add to result
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            // Add children to queue
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return result
}

Time and Space Complexity

Time Complexity: O(n)

• Visit each node exactly once
• Queue operations are O(1)

Space Complexity: O(w)

• w is the maximum width of the tree
• In worst case (perfect binary tree), the last level has n/2 nodes
• Queue stores at most one level at a time

1.5 - Linked List

Problems that demonstrate the effective use of linked list data structure to solve algorithmic challenges.

1.6 - Binary Search Tree

Problems that demonstrate the effective use of binary search tree data structures (set/multiset, map/multimap) to solve algorithmic challenges.

1.7 - Bitset

Problems that demonstrate the effective use of bitset data structure to solve algorithmic challenges.

2 - Techniques

Collection of LeetCode solutions categorized by fundamental algorithmic techniques:

• Two Pointers
• Binary Search
• Binary Search on the Answer
• Binary Search on Float Number + Ternary Search
• Greedy
• Recursion + Backtracking
• Divide and Conquer

2.1 - Two Pointers

Problems that demonstrate the effective use of two pointers technique to solve algorithmic challenges. This technique is particularly useful for array and string problems where we need to find pairs or process elements from both ends.

2.2 - Binary Search

Problems that demonstrate the effective use of binary search algorithm to solve algorithmic challenges. This technique is used to efficiently search for elements in sorted arrays or to find optimal values in monotonic search spaces.

2.3 - Binary Search on the Answer

Problems that demonstrate the effective use of binary search technique to find the optimal answer in the solution space.

2.4 - Binary Search on Float & Ternary Search

Problems that demonstrate the effective use of binary search on floating-point numbers and ternary search techniques to solve algorithmic challenges.

2.5 - Greedy

Problems that demonstrate the effective use of greedy algorithms and techniques to solve algorithmic challenges.

2.6 - Recursion + Backtracking

Problems that demonstrate the effective use of recursion and backtracking techniques to solve algorithmic challenges.

2.7 - Divide and Conquer

Problems that demonstrate the effective use of divide and conquer algorithms to solve algorithmic challenges.