Day #7/50 of Learning DSA

Today marks the seventh day of my journey into mastering Data Structures and Algorithms (DSA). I delved into the intriguing world of the two-pointer pattern, a versatile technique often used to solve array and string problems efficiently. By tackling a series of problems—Valid Palindrome, Reverse String, Squares of a Sorted Array, and Valid Palindrome II. I explored the three primary cases where the two-pointer approach shines. This method not only enhances problem-solving skills but also optimizes performance by reducing time complexity. Join me as I share insights and solutions from today's learning experience.

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.

    bool isPalindrome(string s) {
        int i = 0;
        int j = s.length() - 1;

        while (j > i){
            if (!isalnum(s[i])){
                i++;
                continue;
            }
            if (!isalnum(s[j])){
                j--;
                continue;
            }

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

Reverse String:

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size() - 1;

        while (j > i){
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }

Squares of a Sorted Array:

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int j = n - 1;
        int k = n - 1;

        vector <int> res(n);
        while (j >= i){
            if (abs(nums[i]) > abs(nums[j])){
                res[k] = nums[i] * nums[i];
                i++;
            } else {
                res[k] = nums[j] * nums[j];
                j--;
            }
            k--;
        }

        return res;
    }

Valid Palindrome II:

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

    bool palindromeHelper(int i, int j, string s){
        while(i < j){
            if(s[i] != s[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            int left = s[i];
            int right = s[j];
            if (left != right){
                return palindromeHelper(i+1, j, s) || palindromeHelper(i, j-1, s);
            } else {
                i++;
                j--;
            }
        }
        return true;
    }