Pairs
All topics
Two Pointer Technique
The 2 pointer technique is mostly applicable in sorted arrays where we try to perform a search in O(N).
Here's an example.
Given two arrays ( and ) sorted in ascending order and an integer , we need to find and , such that is equal to .
and are our pointers, at first step is pointing to the first element of , and points to the last element of .
i = 0; j = b.size() - 1;
Move the first pointer one by one through the array , and correct position of the second pointer if needed
while (i < a.size()) {
while(a[i] + b[j] > X && j > 0) j--;
if (a[i] + b[j] == X) writeAnswer(i, j);
i++;
}
Greedy Technique
A greedy algorithm is an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
A very common problem which gives good insight into this is the Job Scheduling Problem.
You have jobs numbered and you have the start times and the end times for the job. Which jobs should you choose such that you get the maximal set of non-overlapping jobs?
The correct solution to this problem is to sort all the jobs on the basis of their end times and then keep on selecting the job with the minimal index in this list which does not overlap with currently selected jobs.
Sounds intuitive, but why does it work?
Well, since each job has equal weight, selecting the one which makes way for newer jobs sooner is optimal. Although a more formal argument can be made for a rigorous proof, the intuition behind it is similar.
Now, let's consider another problem. You again have jobs. Each job can be completed at any time and takes time to complete and has a point value of . But with each second, the point value of the job decreases by . If you have to complete all the jobs, what is the maximum points that you can get?
The problem basically asks us for an order of accomplishing the jobs.
Here, doing the job with higher first makes sense. At the same time, doing the job with lower also sounds good. So how do we decide?
Assume you have just jobs which, without loss of generality, can be numbered as and .
Now, if you do job before job , your net score is:
Otherwise,
If then:
Notice that this argument can be applied to jobs as a sorting rule. The job with maximum value should be done first and so on.
This gives us the optimal ordering and is also in line with our intuition.
Greedy doesn't always work
Greedy solutions are usually good whenever they exist, because they are usually easy to implement and usually have a fast running time. However, greedy algorithms don't always work! By this, we don't mean that the greedy algorithm fails to return the correct answer on all inputs. Instead, we mean that the algorithm fails on at least one input.
For example, consider the following problem: You again have jobs, and the job takes time to complete and has a point value of . This time, the point values do not decrease over time, and you don't have to finish all jobs. Unfortunately you only have a total of time to spend. What is the maximum points you can get?
One greedy algorithm that comes to mind is the following: while there is still time remaining, take the job with the largest point value that can be finished within the remaining time. Intuitively, this can be seen to work in some cases. However, this fails in the following set of jobs:
Assuming , the greedy algorithm mentioned above first takes job , then job , for a total of points. However, this is not the global optimum, because you can take jobs and for a total of points, which is much higher.
The next greedy algorithm we can try is to always take the job which takes the shortest amount of time to finish. However, this also fails the set of jobs above (where you only get points).
You can probably try crafting a more sophisticated greedy algorithm than the ones we described, but it probably won't work, i.e. it will probably fail on some input. This is because the problem we described to you is equivalent to the knapsack problem which currently has no known efficient algorithm!
Dictionary
A dictionary (map in c++) is a data structure used to implement an associative array, a structure that can map keys to values.
In most programming languages we have an in-built dictionary container that can take a key in the form of int, char, string, etc. and the value can be any data type of your choice.
Example in C++ STL:
map <type, type> arr;
Here, type can be anything (int, char, string, etc. even vector<int>).
Storing values is as easy as equating arr["key"] = value;
Sorting
Sorting is a technique to re-order the data in increasing or decreasing order.
Data need not be integers; it can be strings, lists or anything which can have comparable objects.
Each programming language comes with an in-built Sort function.
In C, you can use quick sort as follows
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
here
- *base is pointer to the first element.
- nitems is the number of items to sort.
- size is the size of each element.
- compar is a compare function which can return -1 for less, 0 for equal and +1 for greater.
Sample Code in C
#include <stdio.h>
#include <stdlib.h>
int values[] = { 88, 56, 100, 2, 25 };
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int main()
{
int n;
printf("Before sorting the list is: \n");
for( n = 0 ; n < 5; n++ )
{
printf("%d ", values[n]);
}
qsort(values, 5, sizeof(int), cmpfunc);
printf("\nAfter sorting the list is: \n");
for( n = 0 ; n < 5; n++ )
{
printf("%d ", values[n]);
}
return(0);
}
In C++ algorithm library comes with built in sort function.
example using array and a vector
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[] = {5,4,3,2,1};
vector <int> b(a,a+5); //initialised b using elements of a.
sort(a,a+5);
sort(b.begin(),b.end());
for (auto i :a) {
cout<<i<<" ";
}
cout<<endl;
for (auto i:b) {
cout<<i<<" ";
}
cout<<endl;
}
Note that you can also give your custom compare function in the third argument.
In order to reverse sort you can do
sort(b.rbegin(),b.rend());
In Python you can sort using
a.sort()
sometimes you can even define key which is like compare function.
arr = [[3, 4, 2, 1], [2, 1, 3, 4]]
arr.sort(key = lambda x : x[1]) #key should be a callable function
#here lambda is a returns the 1st element inside the list.
#arr is now [[2, 1, 3, 4], [3, 4, 2, 1]], sorted on 1st index.
Sample Code in Java :
import java.util.* ;
public class sorting{
public static void main(String []args){
Scanner sc = new Scanner(System.in) ;
int n ;
n = sc.nextInt() ;
int A[] = new int[n] ;
for(int i=0;i<n;i++)
A[i] = sc.nextInt() ;
Arrays.sort(A) ;
for(int i=0;i<n;i++)
System.out.print(A[i] + " ") ;
System.out.print("\n") ;
}
}