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

Easiest way to find out which power of number is big?

If you are given two number with its power and told you which number is big. How do you calculate it. For, instance you would say binary exponentiation technique. But this is bit harder when the test case number is bigger. There is also an easy way to solve this problem. Suppose you are given 2^18 and 6^12. Then, you just take logarithm in both numbers. Then it will become 18*log2 and 12*log6. Logarithm function will break this number and make it a little number. which can be compare easily. But for this you have to Double number type, or you will get an error message. Problem:  Problem - 987B - Codeforces Code: void solve() {    ll a,b;    cin>>a>>b;    double num1 = b*log(a);    double num2 = a*log(b);    if(num1==num2) cout<<'='<<endl;    else if(num1>num2) cout<<'>'<<endl;    else cout<<'<'<<endl; }
Post a Comment
Read more

Binary Search Algorithm!

Binary search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N)¹.  Here's how it works: 1. Compare x with the middle element. 2. If x matches with the middle element, we return the mid index. 3. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half. 4. Else (x is smaller) recur for the left half. This process continues until the element is found or the subarray is empty. Look at the array, it is sorted and if we want to find 7 in this array easily by implementing binary search algorithm. We can find it in O(logn) time. While a linear search will take O(n) time which is very long time. So, if an array is sorted we always use Binary search. Algorithm: int main() {     optimize();     int arr[]= {1,4,5,8,10,26...
Post a Comment
Read more

Binary Search Problems!

1. Find the first and last position of a element in sorted array:   In this problem, they will gave us a sorted array and a number. We have to find out the first and last position of that element. if the target is not found, we have to return [-1,-1]. We have to solve this problem in O(log_n) time. So, we have to use binary search algorithm. Input:      nums =  [5 ,7 ,7, 8, 9, 10], target=7 Output:   [1, 2] Solution: class Solution { public:     vector < int > searchRange ( vector < int > & nums , int target ) {         int st= 0 ,en= nums . size ()- 1 ;         int index1=- 1 ,index2=- 1 ;         while (st<=en){             int mid = st + (en-st)/ 2 ;             if ( nums [mid]>target) en = mid- 1 ;             else if ( nums [mid]<target) st = mid+ 1 ;   ...
Post a Comment
Read more