💡 Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

Solution

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        
        while (i < j) {
            while (!isalnum(s[i]) && i < j) {
                i++;
            }
            while (!isalnum(s[j]) && i < j) {
                j--;
            }

            if (tolower(s[i]) != tolower(s[j])) {
                return false;
            }
            i++;
            j--;
        }
        
        return true;
    }
};

💡 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• 105 <= nums[i] <= 105

Solution

1. edgecase: nums verctor 가 3개 미만의 숫자를 가지면 → return []
2. sort nums vector, 그래서 작은 값들이 모두 왼쪽에, 큰 값들이 모두 오른쪽에 오도록 한다
3. 이때 첫번쨰 값이 positive number면 해는 없으므로 []를 return
4. 중복 값은 넘어간다 (어차피 같은 result를 만들어 냄)
5. 현재 보고있는 숫자에서 바로 다음값(j)과 vector의 마지막 값(k)을 하나하나 더해보면서 해를 찾는다
   • vector을 sort 해놨기 때문에, 이전값은 보지 않아도 된다 (0에서 멀어진다)
   • 세숫자를 더하면서 0보다 작으면: 값이 커지도록 j를 오른쪽으로 옮긴다
   • 세숫자를 더하면서 0보다 크면: 작아지도록 k를 왼쪽으로 옮긴다

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();

        // 3개 미만의 elements
        if (n < 3) return result;

        // sort
        sort(nums.begin(), nums.end());

        // 첫번쨰 값이 positive number면 no solution
        if (nums[0] > 0) return result;

        for (int i = 0; i < n - 2; i++) { //O(n)
            // consume all the duplicates
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int j = i + 1;
            int k = n - 1;

            while (j < k) { //O(n)
                int sum = nums[i] + nums[j] + nums[k];

                if (sum < 0) {
                    // 값이 커지도록 j를 오른쪽으로
                    j++;
                } else if (sum > 0) {
                    // 값이 작아지도록 k를 왼쪽으로
                    k--;
                } else {
                    result.push_back({nums[i], nums[j], nums[k]});

                    while (j < k && nums[j] == nums[j+1]) {
                        // consume all the duplicates
                        j++;
                    }
                    j++;

                    while (j < k && nums[k-1] == nums[k]) {
                        // consume all the duplicates
                        k--;
                    }
                    k--;
                }
            }
        } //O(n^2)

        return result;
    }
};

💡 Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Solution

Greedy Algorithm

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0;
        int j = height.size() - 1;

        int result = 0;

        while (i < j) {
            int volume = (j - i) * (min(height[i], height[j]));
            result = max(volume, result);

            // give up the shorter one and try the next one
            if (height[i] <= height[j]) {
                i++;
            } else {
                j--;
            }
        }

        return result;
    }
};