Arrays

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…