Sorting Techniques

Bubble Sort Implementation

class Solution {
public:
    void sortColors(vector<int>& arr) {
        performBubbleSort(arr);
    }
    
private:
    void performBubbleSort(vector<int>& data) {
        int length = data.size();
        for(int i = 0; i < length - 1; i++) {
            for(int j = 0; j < length - i - 1; j++) {
                if(data[j] > data[j + 1]) {
                    swapElements(data[j], data[j + 1]);
                }
            }
        }
    }
    
    void swapElements(int& a, int& b) {
        int temporary = a;
        a = b;
        b = temporary;
    }
};

Hash Table Applications

Single Value Hash - Set Operations

class Solution {
public:
    vector<int> intersection(vector<int>& firstArray, vector<int>& secondArray) {
        vector<int> output;
        unordered_set<int> set1, set2;
        
        populateSet(set1, firstArray);
        populateSet(set2, secondArray);
        
        findCommonElements(set1, set2, output);
        return output;
    }

private:
    void populateSet(unordered_set<int>& targetSet, const vector<int>& source) {
        for(int element : source) {
            targetSet.insert(element);
        }
    }
    
    void findCommonElements(const unordered_set<int>& setA, 
                           const unordered_set<int>& setB, 
                           vector<int>& result) {
        for(int item : setB) {
            if(setA.count(item)) {
                result.push_back(item);
            }
        }
    }
};

Duplicate Value Hash - Frequency Counting

class Solution {
public:
    vector<int> intersect(vector<int>& array1, vector<int>& array2) {
        vector<int> commonElements;
        unordered_map<int, int> frequencyMap1, frequencyMap2;
        
        countFrequencies(frequencyMap1, array1);
        countFrequencies(frequencyMap2, array2);
        
        extractIntersections(frequencyMap1, frequencyMap2, commonElements);
        return commonElements;
    }

private:
    void countFrequencies(unordered_map<int, int>& freqMap, const vector<int>& data) {
        for(int value : data) {
            freqMap[value]++;
        }
    }
    
    void extractIntersections(const unordered_map<int, int>& map1,
                             const unordered_map<int, int>& map2,
                             vector<int>& results) {
        for(const auto& pair : map2) {
            if(map1.count(pair.first)) {
                int minCount = min(map1.at(pair.first), pair.second);
                for(int i = 0; i < minCount; i++) {
                    results.push_back(pair.first);
                }
            }
        }
    }
};

Mixed Type Hash - Grouping Anagrams

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& words) {
        vector<vector<string>> groupedWords;
        unordered_map<string, vector<string>> anagramGroups;
        
        createAnagramGroups(words, anagramGroups);
        convertToResultFormat(anagramGroups, groupedWords);
        
        return groupedWords;
    }

private:
    void createAnagramGroups(const vector<string>& wordList,
                            unordered_map<string, vector<string>>& groups) {
        for(const string& word : wordList) {
            string sortedWord = word;
            sort(sortedWord.begin(), sortedWord.end());
            groups[sortedWord].emplace_back(word);
        }
    }
    
    void convertToResultFormat(const unordered_map<string, vector<string>>& source,
                              vector<vector<string>>& destination) {
        for(const auto& group : source) {
            destination.emplace_back(group.second);
        }
    }
};

Dynamic Array Operations

Basic Vector Manipulation

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        unordered_set<int> firstSet, secondSet;
        
        buildSets(firstSet, secondSet, nums1, nums2);
        findIntersection(firstSet, secondSet, result);
        
        return result;
    }

private:
    void buildSets(unordered_set<int>& set1, unordered_set<int>& set2,
                  const vector<int>& array1, const vector<int>& array2) {
        for(int item : array1) set1.insert(item);
        for(int item : array2) set2.insert(item);
    }
    
    void findIntersection(const unordered_set<int>& primary,
                         const unordered_set<int>& secondary,
                         vector<int>& output) {
        for(int element : secondary) {
            if(primary.count(element)) {
                output.push_back(element);
            }
        }
    }
};

Vector Back Element Access

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> mergedIntervals;
        
        processIntervals(intervals, mergedIntervals);
        return mergedIntervals;
    }

private:
    void processIntervals(const vector<vector<int>>& input,
                         vector<vector<int>>& output) {
        for (const auto& interval : input) {
            int start = interval[0], end = interval[1];
            
            if (output.empty() || getLastEnd(output) < start) {
                output.push_back({start, end});
            } else {
                updateLastEnd(output, end);
            }
        }
    }
    
    int getLastEnd(const vector<vector<int>>& container) {
        return container.back()[1];
    }
    
    void updateLastEnd(vector<vector<int>>& container, int newEnd) {
        container.back()[1] = max(container.back()[1], newEnd);
    }
};

Initialized Vector Declaration

// Syntax: vector<type> name(size, initial_value);
vector<int> initializedArray(arraySize, defaultValue);

// Example:
vector<int> result(data.size(), 0);

String Processing

Substring Extraction

string substring = originalString.substr(startIndex, length);

Linked List Fundamentals

Node Initialization

// Method 1
ListNode head;
head.next = firstNode;

// Method 2
ListNode head(0, firstNode);

Dummy Node Creation

// Method 1
ListNode* dummy = new ListNode(0);
dummy->next = firstNode;

// Method 2
ListNode* dummy = new ListNode(0, firstNode);

Problem-Solving Techniques

Difference Detection via Sum Comparison

class Solution {
public:
    char findTheDifference(string original, string modified) {
        long originalSum = calculateSum(original);
        long modifiedSum = calculateSum(modified);
        
        return static_cast<char>(modifiedSum - originalSum);
    }

private:
    long calculateSum(const string& text) {
        long total = 0;
        for(char character : text) {
            total += static_cast<long>(character);
        }
        return total;
    }
};

Conditional Execution with Sorting

class Solution {
public:
    int thirdMax(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end(), greater<int>());
        
        int distinctCount = 1;
        for(size_t i = 1; i < numbers.size(); i++) {
            if(numbers[i] != numbers[i-1] && ++distinctCount == 3) {
                return numbers[i];
            }
        }
        return numbers[0];
    }
};

Greedy Algorithm Pattern

class Solution {
public:
    int findContentChildren(vector<int>& children, vector<int>& cookies) {
        sort(children.begin(), children.end());
        sort(cookies.begin(), cookies.end());
        
        int satisfiedChildren = 0;
        size_t cookieIndex = 0;
        
        for(size_t childIndex = 0; 
            childIndex < children.size() && cookieIndex < cookies.size(); 
            childIndex++) {
            
            while(cookieIndex < cookies.size() && 
                  cookies[cookieIndex] < children[childIndex]) {
                cookieIndex++;
            }
            
            if(cookieIndex < cookies.size()) {
                satisfiedChildren++;
                cookieIndex++;
            }
        }
        return satisfiedChildren;
    }
};

Binary Search Implementation

class Solution {
public:
    int search(vector<int>& data, int target) {
        int left = 0, right = data.size() - 1;
        
        if(data.empty() || data[0] > target) return -1;
        
        while(left < right) {
            int middle = left + (right - left) / 2;
            if(data[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        
        return (data[left] == target) ? left : -1;
    }
};

Range Binary Search

class Solution {
public:
    vector<int> searchRange(vector<int>& data, int target) {
        if(data.empty()) return {-1, -1};
        
        int firstPosition = findFirstOccurrence(data, target);
        if(firstPosition == -1) return {-1, -1};
        
        int lastPosition = findLastOccurrence(data, target);
        return {firstPosition, lastPosition};
    }

private:
    int findFirstOccurrence(const vector<int>& array, int value) {
        int left = 0, right = array.size() - 1;
        
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(array[mid] < value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (array[left] == value) ? left : -1;
    }
    
    int findLastOccurrence(const vector<int>& array, int value) {
        int left = 0, right = array.size() - 1;
        
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(array[mid] <= value) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

Integer Overflow Handling

class Solution {
public:
    int myAtoi(string input) {
        long long result = 0;
        size_t index = 0;
        
        skipWhitespace(input, index);
        if(index == input.length()) return 0;
        
        int sign = determineSign(input, index);
        skipLeadingZeros(input, index);
        if(index == input.length()) return 0;
        
        while(index < input.length() && isdigit(input[index])) {
            result = result * 10 + (input[index] - '0');
            
            long long signedResult = result * sign;
            if(signedResult >= INT_MAX) return INT_MAX;
            if(signedResult <= INT_MIN) return INT_MIN;
            
            index++;
        }
        
        return static_cast<int>(result * sign);
    }

private:
    void skipWhitespace(const string& str, size_t& pos) {
        while(pos < str.length() && str[pos] == ' ') pos++;
    }
    
    int determineSign(const string& str, size_t& pos) {
        if(str[pos] == '-') {
            pos++;
            return -1;
        } else if(str[pos] == '+') {
            pos++;
        }
        return 1;
    }
    
    void skipLeadingZeros(const string& str, size_t& pos) {
        while(pos < str.length() && str[pos] == '0') pos++;
    }
};

Backtracking Algorithm Framework

Application areas: combinations, permutations, board games, segmentation, subsets

void backtrack(parameters) {
    if(termination_condition) {
        collect_results();
        return;
    }
    
    for(collection_elements) {
        process_node();
        backtrack();
        undo_operations();
        return;
    }
}

Combination Generation Example

class Solution {
private:
    vector<int> currentPath;
    vector<vector<int>> allResults;
    
    void generateCombinations(int totalNumbers, int selectionSize, int startIndex) {
        if(currentPath.size() == selectionSize) {
            allResults.emplace_back(currentPath);
            return;
        }
        
        for(int i = startIndex; i <= totalNumbers - (selectionSize - currentPath.size()) + 1; i++) {
            currentPath.emplace_back(i);
            generateCombinations(totalNumbers, selectionSize, i + 1);
            currentPath.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        generateCombinations(n, k, 1);
        return allResults;
    }
};

Letter Combination Mapping

class Solution {
private:
    string currentCombination;
    vector<string> validCombinations;
    
    void buildCombinations(const string& digits, 
                          const unordered_map<char, string>& mapping,
                          int position) {
        if(currentCombination.length() == digits.length()) {
            validCombinations.emplace_back(currentCombination);
            return;
        }
        
        char digit = digits[position];
        string letters = mapping.at(digit);
        
        for(char letter : letters) {
            currentCombination.push_back(letter);
            buildCombinations(digits, mapping, position + 1);
            currentCombination.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string phoneNumber) {
        if(phoneNumber.empty()) return {};
        
        unordered_map<char, string> digitMapping = {
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        
        buildCombinations(phoneNumber, digitMapping, 0);
        return validCombinations;
    }
};