# two-pointers

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. This is a famous interview problem to learn time and space complexity optimization using various approaches. Two-pointers approach provides an efficient solution in O(n) time and O(1) space.

Container With Most Water Problem

Given an array of n non-negative integers height[n], where each represents a point at coordinate (i, height[i]). n vertical lines are drawn such that the two endpoints of line i is at (i, height[i]) and (i, 0). Write a program to find two lines, which together with the x-axis form a container, such that the container contains the most water.

Intersection of Two Unsorted Arrays

Given two integer arrays, X[] and Y[] of size m and n. Write a program to find the intersection of these two arrays. The intersection of two arrays is a list of distinct elements present in both arrays. The elements in the intersection can be in any order. Suppose m > n and elements in both arrays are distinct.

Find maximum j – i such that A[j] > A[i]

Given an unsorted array X[] of distinct elements, write a program to find the maximum j  -  i such that j > i and X[j] > X[i].

Intersection of two sorted linked lists

Given two sorted linked lists, write a program to find the intersections of the linked lists, and return the head of the new Linked List.

Find middle element in linked list

Given a singly linked list, write a program to find the middle node of the linked list. If the node count is even then we need to return the second middle node.

Triplet with Zero Sum

Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.

Remove Nth Node from List End

Write a program to remove the Nth node from the end of the linked list i.e. when the node is traversed from the end we have to delete the Nth node from there.

Detect Loop in a Linked List

Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.

Median of two sorted arrays of the equal size

There are two sorted arrays A and B of size n each, write a program to find the median of the array obtained after merging both the arrays(i.e., an array of length 2n which is even). The median of a sorted array of size n is defined as the middle element when n is odd and the average of the middle two elements when n is even.

Find whether an array is a subset of another array

We are given two integer arrays X[] and Y[], write a program to check whether array Y[] is a subset of array X[] or not. An array Y is a subset of another array X if each Y element is present in X. How do you check if one array is a subset of another? Explore and Enjoy!

Check for pair in an array with a given sum

Given an array of n integers and a target number, write a program to check whether a pair sum exits in the array or not. In other words, we need to check whether pair of elements in the array sum exactly to the target value.

n Repeated element in 2n size array

In an array of size 2n, there are n+1 unique elements, and exactly one of these elements is repeated n times. Return the element repeated n times.

Remove duplicates from sorted array

Write a program to remove the duplicates from the sorted array. For this we are given a sorted array, the task is to remove the duplicate elements such that there is a single occurrence of each element in the array.

Sort an array of 0s, 1s, and 2s —Dutch National Flag Problem

Given an array X[] consisting of 0s, 1s, and 2s. Write a program to sort the array of 0’s, 1’s, and 2’s in ascending order. This is a famous coding interview problem asked in facebook, microsoft and amazon.

Move all Zeroes to the End of an Array

Given an array X[] of n elements filled with several integers, some of them being zeroes, write a program to move all the zeroes to the end. This is an excellent coding problem to learn space and time complexity optimization.