Longest Increasing Subsequence

To determine the length of the longest strictly increasing subsequence, dynamic programming is applied where dp[i] represents the length of the longest subsequence ending at index i.

class Solution {
public:
    int lengthOfLIS(vector<int>& sequence) {
        int size = sequence.size();
        if (size == 0) return 0;
        
        vector<int> dp(size, 1);
        int maxLength = 1;
        
        for (int i = 1; i < size; ++i) {
            for (int j = 0; j < i; ++j) {
                if (sequence[j] < sequence[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
};

Kth Largest Element in Array

Finding the kth largest element requires an efficient sorting approach. A custom quicksort implementation partitions the array around a pivot element.

class Solution {
public:
    void quickSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        
        int pivotValue = arr[(left + right) / 2];
        int i = left, j = right;
        
        while (i <= j) {
            while (arr[i] < pivotValue) i++;
            while (arr[j] > pivotValue) j--;
            if (i <= j) {
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }
        
        if (left < j) quickSort(arr, left, j);
        if (i < right) quickSort(arr, i, right);
    }
    
    int findKthLargest(vector<int>& numbers, int k) {
        int length = numbers.size();
        quickSort(numbers, 0, length - 1);
        return numbers[length - k];
    }
};

Two Sum Problem

Using a hash table to store previously seen values enables finding two numbers that sum to a target in linear time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashTable;
        
        for (int i = 0; i < nums.size(); i++) {
            if (hashTable.find(target - nums[i]) != hashTable.end()) {
                return {i, hashTable[target - nums[i]]};
            }
            hashTable[nums[i]] = i;
        }
        
        return {};
    }
};

Longest Substring Without Repeating Characters

A sliding window technique with an unordered set efficiently tracks characters in the current substring.

class Solution {
public:
    int lengthOfLongestSubstring(string str) {
        unordered_set<char> charSet;
        int maxLength = 0;
        int rightPointer = -1;
        int length = str.size();
        
        for (int leftPointer = 0; leftPointer < length; leftPointer++) {
            if (leftPointer != 0) {
                charSet.erase(str[leftPointer - 1]);
            }
            
            while (rightPointer + 1 < length && !charSet.count(str[rightPointer + 1])) {
                charSet.insert(str[rightPointer + 1]);
                rightPointer++;
            }
            
            maxLength = max(maxLength, rightPointer - leftPointer + 1);
        }
        
        return maxLength;
    }
};

Container With Most Water

The optimal approach uses two pointers starting from both ends of the array, moving the pointer pointing to the shorter line inward.

class Solution {
public:
    int maxArea(vector<int>& heights) {
        int leftIndex = 0;
        int rightIndex = heights.size() - 1;
        int maxWater = 0;
        
        while (leftIndex < rightIndex) {
            int currentArea = (rightIndex - leftIndex) * min(heights[leftIndex], heights[rightIndex]);
            maxWater = max(maxWater, currentArea);
            
            if (heights[leftIndex] < heights[rightIndex]) {
                leftIndex++;
            } else {
                rightIndex--;
            }
        }
        
        return maxWater;
    }
};

Climbing Stairs

Dynamic programming solves this classic problem where each step's count equals the sum of the previous two steps' counts.

class Solution {
public:
    int climbStairs(int steps) {
        if (steps < 2) return 1;
        
        vector<int> dp(steps + 1);
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= steps; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        return dp[steps];
    }
};

LRU Cache Implementation

Combining a doubly linked list with a hash map creates an efficient LRU cache with O(1) operations.

struct Node {
    int key, value;
    Node* prev;
    Node* next;
    Node(): key(0), value(0), prev(nullptr), next(nullptr) {}
    Node(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};