DEV Community

loading...
Cover image for [algorithm] Multiple pointers pattern explained! (EPISODE 1)

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

alokz diptim!
Software Developer, Scientist and Graphical artist
・2 min read

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!

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
Enter fullscreen mode Exit fullscreen mode

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?

easy

Looking at the component of the array,

Alt Text

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........

NaivePattern

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

Native2

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[] { };
        }
    }
Enter fullscreen mode Exit fullscreen mode

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

discard

Then give room for the multiple/double pointer approach

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

Discussion (0)