Two Pointer

on

 AlgoPrep's 151 Problems Sheet

link --> Click here

 Two Pointers


 Question 15: Container With Most Water

Medium
 
Topics
Companies
 
Hint
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

1. Solution using Array:

class Solution {
    public int maxArea(int[] height) {
        int a = 0;
        int n =height.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                a = Math.max(a , Math.min(height[i],height[j]) * (j-i));
            }
        }
        return a;
    }
}


Question 16: Two Sum

Given an array arr of positive integers and another number x. Determine whether two elements exist in arr whose sum is exactly x or not.

Examples:

Input: x = 16, arr[] = [1, 4, 45, 6, 10, 8]
Output: true
Explanation: arr[3] + arr[4] = 6 + 10 = 16
Input: x = 11, arr[] = [1, 2, 4, 3, 6]
Output: false
Explanation: None of the pair makes a sum of 11

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ arr.size ≤ 105
1 ≤ arr[i] ≤ 105


Solution Using Array: 
class Solution {
    boolean hasArrayTwoCandidates(int arr[], int x) {
        int n = arr.length;
        int sum = 0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                sum = arr[i]+arr[j];
                if(x == sum){
                    return true;
                }
            }
        }
        return false;
    }
}

Question 17: Two Difference

Given an array arr[] of size n and an integer x, return 1 if there exists a pair of elements in the array whose absolute difference is x, otherwise, return -1.

Example 1:

Input:
n = 6
x = 78
arr[] = {5, 20, 3, 2, 5, 80}
Output:
1
Explanation:
Pair (2, 80) have absolute difference of 78.

Example 2:

Input:
n = 5
x = 45
arr[] = {90, 70, 20, 80, 50}
Output:
-1
Explanation:
There is no pair with absolute difference of 45.

Your Task:
You need not take input or print anything. Your task is to complete the function findPair() which takes integers n, x, and an array arr[] as input parameters and returns 1 if the required pair exists, return -1 otherwise.

Expected Time Complexity: O(n* Log(n)).
Expected Auxiliary Space: O(1).

Constraints:
1<=n<=106 
1<=arr[i]<=106 
0<=x<=105

Code Not Runing Check Properly:


class Solution {
    public int findPair(int n, int x, int[] arr) {
        int sub = 0;
        int l=0;
        for(int r=l+1;r<n;r++){
            sub = Math.abs(arr[l]-arr[r]);
            if(sub == x){
                return 1;
            }
            l++;
        }
        return -1;
    }
}

Code : Time Limit Error

class Solution {
    public int findPair(int n, int x, int[] arr) {
        int sub = 0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                sub = Math.abs(arr[i]-arr[j]);
                if(sub == x){
                    return 1;
                }
            }
        }
        return -1;
    }
}

Comments

Post a Comment