Two pointer method

Question

Recently i came across a question during a programming contest on codeforces. Problem tags referred that the problems could be solved by using two pointer method. What exactly is the Two Pointer Method?

Answer 1

From what I can tell at those links, the "two pointer method" simply refers to indexing into two different arrays using two different indices (they refer to the array indices as pointers, which is somewhat different from how most C programmers use the term).

They were using it in context of a problem like

if (a[i] + b[j] == X)
  // do something with i and j

where i and j were the pointers (in the generic sense of the term "pointer", not the C datatype sense).

This isn't anything terribly exotic, and until today I had no idea that anyone had coined a specific term for it.

When you talk to most C programmers, a term like "two pointer method" would imply something involving a double dereference, such as

x = **p;

which is nothing like what they're talking about at the codeforces link.

Answer 2

Google reports 2350 hits for "two pointer method" but the first couple pages use the phrase to refer to a variety of algorithms. It's seldom capitalized. Probably they were referring to one of several alternatives that had already been established in other discussion, literature, etc specific to the group hosting the competition.

Answer 3

Probably they meant having a pointer to a pointer.

In C this is often used when you e.g. need a called function to modify a pointer that the caller owns.

One example could be a function that inserts a tree node in a binary tree:

void tree_insert(Node **root, int value)
{
  Node *here = *root;

  if(here == NULL)
  {
    if((*root = malloc(sizeof ***root)) != NULL)
      (*root)->value = value;
  }
  else if(value < here->value)
    tree_insert(&root->left, value);
  else if(value > here->value)
    tree_insert(&root->right, value);
}

By passing a pointer to the tree's root (itself a pointer) the function is able to change it.

Using this, a tree can be initialized by:

Node *tree = NULL;

tree_insert(&tree, 42);
tree_insert(&tree, 4711);

In this example we could of course have used the return value from the function too, but hopefully you get the idea.

Answer 4

I guess you are talking about something like this:

int **allocation(int n, int m) {
   int **matrix;
   int i;

   matrix = (int **) malloc(sizeof(int *) * n);
   for (i = 0; i < n; i++)
     matrix[i] = (int *) malloc(sizeof(int) * m);

   return matrix;
}