Skip to main content

Two Pointer Problems


Here we have given some important two pointer problems below:

1. 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.

 -> Solution:

class Solution {
public:
    bool isPalindrome(string s) {
      int low=0;
      int high=s.length()-1;
      while(low<high){
          while(!iswalnum(s[low]) && low<high){
              low++;
          }
          while(!iswalnum(s[high]) && low<high){
              high--;
          }
          if(tolower(s[low])!=tolower(s[high])){
           return false;
          }
          low++;
          high--;
      }
        return true;
    }
};

Time complexity: O(n)


2. Two Sum II:

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order,find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
-> Solution:
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int>vec;
        int st=0;
        int en=numbers.size()-1;
        while(st<en){
            int sum = numbers[st]+numbers[en];
            if(sum<target){
                st++;
            }
            else if(sum>target){
                en--;
            }
            else{
                vec.push_back(st+1);
                vec.push_back(en+1);
                break;
            }
        }
        return vec;
    }
};

Time complexity: O(n)


3. 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.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>vec;
        for(int i=0;i<nums.size();i++){
            int ans = nums[i];
            if(i>0 && nums[i-1]==ans) continue;
            else{
                int st=i+1,en=nums.size()-1;
                while(st<en){
                    if(ans+nums[st]+nums[en]>0) en--;
                    else if (ans+nums[st]+nums[en]<0) st++;
                    else{
                        vec.push_back({ans,nums[st],nums[en]});
                    while(st<en && nums[st]==nums[st+1]){
                        st++;
                    }
                    st++;
                    while(st<en && nums[en]==nums[en-1]){
                        en--;
                    }
                    en--;
                    }
                }
            }
        }
        return vec;
    }
};

Time complexity: O(n^2)

Problem link: 3Sum - LeetCode
Labels:

Comments

Post a Comment

Popular posts from this blog

Rotated Array(Modified Binary Search)

  A modified binary search is an algorithm that can be used to find an element in a sorted array by using a different base or condition than the standard binary search. It is an extension of the bitwise binary search and has a similar running time of O(log N) . There are different ways to modify the binary search algorithm, such as using a different number base, finding the minimum element in a rotated and sorted array, or comparing the input element with the first, last and middle elements of the array. Today we will look at rotated array problems. A rotated array is an array that is sorted in ascending order but shifted to the right by some unknown number of positions. For example, [0,1,2,4,5,6,7] is a sorted array and [4,5,6,7,0,1,2] is a rotated array with 4 positions shifted. A rotated array can also be seen as two sorted subarrays concatenated together. For example, [4,5,6,7] and [0,1,2] are two sorted subarrays that form the rotated array [4,5,6,7,0,1,2]. There are two very ...
Post a Comment
Read more

Find out all divisor in efficient way!

1. Brute force approach:   In this process, we use a for loop and iterate the whole 1 to n number. Then, we find out all the divisors by one by one. It is not a optimal solution for this problem. Because, it will take O(n) time to find out all divisors. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i<=n; i++)     {         if(n%2==0) cout<<i<<" ";     }     cout<<endl;     return 0; } Time complexity: O(n) 2. SQRT approach:   In this process, we only iterate in the loop by half of the numbers. Because, if we see we don't need to go through whole n numbers. int main() {     optimize();     ll n;     cin>>n;     for(ll i=1; i * i<=n; i++)     {         if(n%2==0) cout<<i<<" "<<n/i<<endl;     }     return 0; } Tim...
Post a Comment
Read more