[algorithm] Multiple pointers pattern explained! (EPISODE 1)

This is part of my quick series on algorithm --- with a lot of images to buttress the point. There are many ways of searching through an array. The simplest and obvious is using a loop!

But the concern it raises is when the iterations are overused -- Loop inside a loop has an effect on how our program runs on a large scale of data. (N square time complexity)

For Loop
    For Loop

So there ought to be a better way of searching through an ordered list

Let's look at an example of an array { 2, 3, 7, 9, 17, 1, 5 } in which we need to find the two sums of the array element that gives us 10!

Pretty easy ei?

Looking at the component of the array,

7 + 3 and 9 + 1 will both give 10

First and foremost, we start with the zero-based index and search through the whole array list. In simple term, it is the summation of the zero-based element with every single element in the array list

DAMN! we didn't see it!

.......Moving to the next index........

Pretty much the summation of all the elements in the array with the first index and we didn't see it. We decided to shift the index by 1 and rescan through the array

Yes!! we found it.

But assuming the array has close to 1 Million elements then we need to scan through the array list, and move the start/correlation index by 1 and rescan through the one million. ~ Repeat.~ (That's time and resource poor performance)

 class Program
    {
        static void Main(string[] args)
        {
           int[] result = SumArray(new int[] { 2, 3, 7, 9, 17, 1, 5 }, 10);

            Console.WriteLine($"{result[0]}, {result[1]}");

            Console.ReadLine();
        }

        private static int[] SumArray(int[] array, int luckySum)
        {
            for (int i = 0; i < array.Length; i++) //Use this to get the index of each element
            {
                for (int j = i+1; j < array.Length; j++) //use this loop to scan through the array
                {
                    int firstVal = array[i];
                    int secondVal = array[j];

                    int sum = firstVal + secondVal;

                    if (sum == luckySum)
                        return new int [] { array[i], array[j]};
                }
            }

            return new int[] { };
        }
    }

So not efficient therefore we need to discard that approach. (unless you working with an unordered list)

Then give room for the multiple/double pointer approach

To be explained in the next episode.... stay tuned