Equilibrium index of an array

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in an arrya A:
Median of two sorted arrays

A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0

3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

6 is also an equilibrium index, because sum of zero elements is zero, i.e., A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=0

7 is not an equilibrium index, because it is not a valid index of array A.

Write a function int equilibrium(int[] arr, int n); that given a sequence arr[] of size n, returns an equilibrium index (if any) or -1 if no equilibrium indexes exist.

Solution : Iterate through the array and find the sum of all elements, lets call it WholeSum. Then start iterating from left to right, while iterating store the addition of the elements in another variable called left sum. From WholeSum we subtract LeftSum and we get RightSum, if LeftSum is equal to RightSum, that s out Equilibrium index of the array. It takes O(n).

Merge an array of size n into another array of size m+n

There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.

First array : 2, null, 7, null, null, 10, null
Second Array : 5,8, 12,14

This can be solved as follows: Populate all the numbers of the first array to the end of the first array. Then merge the second array on to the first array, by comparing elements from the first array and second array starting from the beginning.

Reversal algorithm for array rotation

Given an array 1,2,3,4,5,6,7. You are asked to rotate the array so that output will be 3,4,5,6,7,8,1,2. How to do this? There is a very easy way to get this done.

Question: Write a function rotate(arr[], d, n) that rotates arr[] of size n by d elements.

here is the pseudo code for it.

Reverse first d element,
reverse d+1 to n,
reverse the whole array
and voila.

Below is the code :

        public static void Rotate(int [] arr, int n)
        {
            RecursiveReverse(arr, 0, n-1);
            RecursiveReverse(arr, n, arr.Length-1);
            RecursiveReverse(arr, 0, arr.Length-1);
        }

        public static void RecursiveReverse(int [] arr, int start, int end)
        {
            if(start >= end)
            {
                return;
            }

            var temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;

            RecursiveReverse(arr, start + 1, end-1);
        }

Maximum difference between two elements

Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[].

Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)

Obvious solution is using two for loops and checking the difference between every element to every other element which is O(n^2). You will need an additional variable to keep the max difference.

It is important to understand this question such that, you can only go from left to right, so we are not talking about absolute value difference. Therefore, sorting doesnt help.

A better solution is to keep two variables, one to keep the minimum element so far and another to keep the maximum difference so far. This allows a single iteratation over the array and you will have the answer.

Below is the code for it.

        public static void FindMaxDifference()
        {
            var arr = new int[] { 7, 9, 5, 6, 3, 20 };
            int min = arr[0];
            int maxSoFar = arr[1] - arr[0];
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] < min)
                {
                    min = arr[i];
                }
                if (arr[i] - min > maxSoFar)
                {
                    maxSoFar = arr[i] - min;
                }
            }
            Console.WriteLine(maxSoFar);
        }

Leaders in an array

Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

This is a pretty simple algorithm, you need to scan the array from right to left and keep track of the maximum element, whenever you change the maximum, you find a leader, you print that.

        public static void FindLeadersInArray()
        {
            int[] arr = new[] { 16, 17, 4, 3, 5, 2 };

            int maxNow = 0;
            for (int i = arr.Length - 1; i >= 0; i--)
            {
                if(arr[i] > maxNow)
                {
                    maxNow = arr[i];
                    Console.WriteLine(arr[i]);
                }
            }

        }

Sort elements by frequency

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came 1st
E.g. 2 5 2 8 5 6 8 8 output: 8 8 8 2 2 5 5 6.
There are several approaches to this problem, such as sorting and counting the number of occurrence, sorting can be done in nlogn using quick sort, merge sort. etc. Also , you can use bucket sort for this kind of questions as well.

Below is a method that uses dictionary/hashtable, first, we need to iterate through the input and find the occurrences of all the elements. Then we need to sort the dictionary by value in descending order, which i used linq in the code below.

You can also use a binary search tree, you will need to modify the Node class, and add the count property to it, so if there is a duplicate, you will need to increment the count. Then you can do a inorder traversal to find the sorted sequence in ascending order then you need to reverse that.

        public static void SortByFrequency(int [] arr)
        {
            Dictionary numbersToOccurence = new Dictionary();

            foreach (var  item in arr)
            {
                int res = 0;

                if(numbersToOccurence.TryGetValue(item,out res))
                {
                    numbersToOccurence[item] = ++res;
                }else
                {
                    numbersToOccurence.Add(item, 1);
                }
            }

            var sorted = (from item in numbersToOccurence orderby item.Value descending select item).ToDictionary(kvpair => kvpair.Key, kvpair=>kvpair.Value);

            foreach (var i in sorted)
            {
                Console.WriteLine("Key : {0}, {1}",i.Key, i.Value);
            }

        }

Reversing an Array or string recursively and iteratively

It’s common to come across a requirement to reverse an array or string recursively or iteratively. Even though C# has a linq method that does this for you. It s a good practice to understand how reversing works.

There are several ways you can reverse a collections. Below are two approaches to reverse an array and string, since string is a character array, same approach applies to them.

        public static void RecursiveReverse(int [] arr, int start, int end)
        {
            if(start >= end)
            {
                return;
            }

            var temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;

            RecursiveReverse(arr, start + 1, end-1);
        }

         public static string Reverse(string str)
        {
            if(String.IsNullOrEmpty(str))
            {
                return string.Empty;
            }
            
            char[] c_str = str.ToCharArray();

            for(int i = 0; i < str.Length / 2 ; i++)
            {

                var temp = c_str[i];

                c_str[i] = c_str[str.Length - i - 1];
                c_str[str.Length - i - 1] = temp;

            }

            return new string(c_str);
        }

C# – Stack and Queue with Linked List Implementation via C-Sharp

Queue and Stack can be implemented using a linked list very easily. Below is a simple implementation.

public class StackWithLinkedList
    {
        private LinkedList _holder = new LinkedList();
    
        public StackWithLinkedList()
        {
            
        }

        public void Push(T data)
        {
            _holder.AddFirst(data);
        }

        public T Pop()
        {
            var item = _holder.First;

            _holder.Remove(_holder.First);

            return item.Value;
        }

        public T Peek()
        {
            var item = _holder.First;

            return item.Value;
        }

        public IEnumerable Traversal()
        {
            foreach (var elememt in _holder)
            {
                yield return elememt;
            }
        }

        public int Count
        {
            get { return _holder.Count; }
        }
    
    }

    public class QueueWithLinkedList
    {
        private LinkedList _container = new LinkedList();

        public QueueWithLinkedList()
        {
            
        }

        public void Enqueue(T data)
        {
            _container.AddFirst(data);
        }

        public T Dequeue()
        {
            var item = _container.Last;

            _container.Remove(_container.Last);

            return item.Value;
        }

        public T Peek()
        {
            var item = _container.Last;

            return item.Value;
        }

        public int Count
        {
            get { return _container.Count; }
        }

        public IEnumerable Iterator
        {
            get
            {
                foreach (var element in _container)
                {
                    yield return element;
                }
            }
        }
    }

Removing Duplicates from an array, list or linked list

There are several algorithms to remove duplicates from a given sequence of elements.

For sorted sequences, this can be done very easily as follows. Have two pointers, one to point to the current node and one to point to the next node, if current node and next node are equal, you can remove the next node. If you are doing this for a linked list, you need to update your next pointer of the current node to the next node of the node to be deleted. By doing this, you can traverse the sequence until the end, and problem solved. This solution doesnt require extra space, and it s in place. running time is O(n).

If the sequence is unsorted, and you are allowed to use extra space, you can use a hash table, while you are iterating through the sequence, you check the dictionary if the dictionary contains the current element, skip that element, if it doesn’t add the element to the dictionary and keep the element. do this for all the elements. and at the end you ll have the unique elements. This solution requires extra space for hashtable. and the solution is O(n).

Another approach, if extra space is not allowed, would be sort the sequence and do the first paragraph. Running time is O(n). no extra space.

If the maximum element of the array is smaller than the array size, you can use count sort. as follows:

 for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }

This work in O(n) and doesnt require extra space.

Another solution would be to use bucket sort, that sorts in O(n). then do the first paragraph.

Move zeros to the end

Given a sequence as following, provide and algorithms and code to move all the zeros to the end of the sequence. This should be in O(n) and using no extra storage.
input :{1, 0, 2, 0, 3, 0, 0, 4, 5, 6, 7, 0, 0, 0};
output :{1, 2, 3, 4, 5, 6, 7, 0, 0, 0,0,0,0,0};

I have used two pointers, second pointer to find the zero and wait until the first pointer reaches a non zero element and then swap them. then change the position of second pointer.

        public static void MoveZerosToEnd(int [] arr)
        {
            int secondPointer = 0;

            for(int i=0;i< arr.Length;i++)
            {
                 
                if(arr[i] == 0 && arr[secondPointer] != 0)
                {
                    secondPointer = i;
                }

                if(arr[i] > 0 && arr[secondPointer] == 0)
                {
                    var temp = arr[i];
                    arr[secondPointer] = temp;
                    arr[i] = 0;
                    
                    while(arr[secondPointer]!=0)
                    {
                        secondPointer++;
                    }
                }
            }
            
        }