Arrays

Question: We have 2 sorted arrays and we want to combine them into a single sorted array. Input: arr1[] = 1, 4, 6, 8, 13, 25    ||     arr2[] = 2, 7, 10, 11, 19, 50 Output: 1, 2, 4, 6, 7, 8, 10, 11, 13, 19, 50 One of the simplest ways to solve this problem would be to copy both the arrays into a new array and then apply some sorting technique on them. But this method will not utilize the fact that both the arrays are already sorted.…

Bubble sort is one of the simplest sorting algorithms and it works on the principle of swapping two elements. Think of the bubble sort as a water bubble that arises from the bottom of the ocean. As it rises up, it grows in size and its the maximum when it reaches the surface. Similarly, in bubble sort, we arrange items from smallest to the largest at the end one by one in each iteration.The algorithm for bubble sort is as follows:- We start from the bottom of the array and…

As the name suggests SELECTION SORT involves selecting an element. Now the question arises, as to how should we select this element. What is the criteria? Where should we put it? All these answers are given in the algorithm for SELECTION SORT. In selection sort, what we do is:- Start from the first position in the array. Traverse the remaining array to find the smallest number Swap this smallest number with the number we selected in the first place. Repeat steps 2 and 3 with the next position. Let us…

Insertion sort is the most generic example of a sorting algorithm, and the one which is used by one of the most naive users. Often we must have also used this algorithm in our real life examples unknowingly. One of the favorite example is:- This is a very common scenario and we must have used it. Suppose you get a hand of cards. Our general approach is that we start scanning the cards from starting and if we find a card out of place, we remove it from there and…

What is sorting? Sorting is an algorithm that arranges the elements of a list in a certain order (either ascending or descending, as per the requirement). The output is simply a permutation of the input data. Why sorting? Sorting is one of the most important categories of algorithms in computer science. Sometimes sorting significantly reduces the problem complexity. We can use sorting as a technique to reduce the search complexity. Great research went into this category of algorithms because of its importance. These algorithms are very much used in many…

Question: Find spans in an array. Given an array arr[], the SPAN s[i] of arr[i] is the maximum number of consecutive elements arr[j] immediately before arr[i] such that arr[j] <= arr[i]. Let us try to understand the question once again. This is a very common problem in stock markets to find the peaks. Spans have applications to financial analysis(Example:- You might have heard a saying “STOCKS AT 52 WEEK HIGH”). The span of a stocks price on certain day, i , is the maximum number of consecutive days (up-to the…

Question: How do we implement 2 stacks using only one array? Our stack routines should not indicate an exception unless every slot in the array is used? SOLUTION: Algorithm: Start with two indexes, one at the left end and other at the right end The left index simulates the first stack and the right index simulates the second stack. If we want to push an element into the first stack then put the element at left index. Similarly, if we want to push an element into the second stack then…

Question: Given an array of characters formed by a’s and b’s. The string is marked with special character ‘X’ which represents the middle of the list (for example ababa…ababXbabab…baaa). Check whether the string is palindrome or not? Input: ababXbaba Output: PALINDROME Input: ababababababbbbbXbbbbabababababa Output: PALINDROME Input: abababbbabbXabbbabbabbb Output: NOT PALINDROME This is one of the simplest algorithms. What we do is, start two indexes – one at the beginning of the string and other at the ending of the string. Each time compare whether the values at both the indexes…