Solution in C++:

#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0;
    int right = numbers.size() - 1;
    
    while (left < right) {
        int current_sum = numbers[left] + numbers[right];
        
        if (current_sum == target) {
            return {left + 1, right + 1};  // 1-indexed
        } else if (current_sum < target) {
            left++;  // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    
    return {};  // No solution
}

Step-by-Step Simulation:

Explanation: Since the array is sorted, we can use two pointers starting from both ends. If the sum is too small, we move the left pointer right (increase sum). If too large, we move the right pointer left (decrease sum). This works because the array is sorted, guaranteeing we don't miss any valid pairs. The key insight is that if nums[left] + nums[right] < target, then nums[left] + any element to the left of right is also < target, so we can safely move left forward.

Time Complexity: O(n)

Space Complexity: O(1)

Solution in C++:

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();
    
    for (int i = 0; i < n - 2; i++) {
        // Skip duplicates for first number
        if (i > 0 && nums[i] == nums[i-1]) {
            continue;
        }
        
        int left = i + 1;
        int right = n - 1;
        
        while (left < right) {
            int current_sum = nums[i] + nums[left] + nums[right];
            
            if (current_sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                
                left++;
                right--;
            } else if (current_sum < 0) {
                left++;  // Need larger sum
            } else {
                right--;  // Need smaller sum
            }
        }
    }
    
    return result;
}

Step-by-Step Simulation:

Explanation: We fix the first number and use two pointers for the remaining two. After sorting, we iterate through each number as the first element, then use two pointers to find pairs that sum to the negative of the first number. We skip duplicates to avoid duplicate triplets in the result. Sorting allows us to use two pointers efficiently and skip duplicates easily.

Time Complexity: O(n²)

Space Complexity: O(1) excluding output array

Solution in C++:

#include <vector>
#include <algorithm>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0;
    int right = height.size() - 1;
    int max_water = 0;
    
    while (left < right) {
        // Calculate area: width × min(height[left], height[right])
        int width = right - left;
        int current_area = width * min(height[left], height[right]);
        max_water = max(max_water, current_area);
        
        // Move the pointer with smaller height
        // This is optimal because:
        // - Moving the taller pointer can only decrease area (width decreases)
        // - Moving the shorter pointer might increase area (if we find taller line)
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return max_water;
}

Step-by-Step Simulation:

Explanation: We start with pointers at both ends. The area is limited by the shorter line. We always move the pointer with the smaller height because moving the taller one can only decrease the area (width decreases, height can't increase). This greedy approach ensures we check all possible optimal containers. The key insight is that we never miss the optimal solution because if the optimal container uses lines at positions i and j, we'll find it before one of the pointers passes the other.

Time Complexity: O(n)

Space Complexity: O(1)

Solution in C++:

#include <string>
#include <cctype>
using namespace std;

bool isPalindrome(string s) {
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        
        // Compare characters (case-insensitive)
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

Explanation: We use two pointers from both ends. We skip non-alphanumeric characters by moving pointers until we find valid characters. Then we compare them case-insensitively using tolower(). If any pair doesn't match, it's not a palindrome. The algorithm continues until pointers meet or cross. This approach is efficient because we only process each character once.

Time Complexity: O(n)

Space Complexity: O(1)

Solution in C++:

#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    
    int slow = 0;  // Position to place next unique element
    
    for (int fast = 1; fast < nums.size(); fast++) {
        // If current element is different from previous unique element
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    
    return slow + 1;  // Length of array with unique elements
}

Step-by-Step Simulation:

Explanation: We use slow and fast pointers. The slow pointer tracks where to place the next unique element. The fast pointer scans through the array. When we find a new unique element (different from the one at slow), we increment slow and place the new element there. Since the array is sorted, duplicates are adjacent, so this efficiently removes them. The in-place modification ensures O(1) space complexity.

Time Complexity: O(n)

Space Complexity: O(1)