Arrays

Question: Let us suppose we have an array whose ith element gives the price of a share on the day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. When we talk about the best times to sell and buy, we mean that we want the best profit possible. A profit is possible when our buying rate is less than the selling rate. We need to maximize…

Question: Given an array arr[], that contains only 0’s and 1’s. Write a function that separate 0’s and 1’s in the array. Input: 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1 Output: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 The objective of the problem is to segregate the array in two parts, and it is more popularly known as a variation of Dutch National Flag Problem. Method 1: The most naive method is to count…

Question: Given an array arr[], write a function that separates even and odd numbers. The function should print first all the even numbers and then the odd numbers. Input: 4, 8, 15, 16, 23, 42 Output: 4, 8, 16, 42, 23, 15 The objective of this problem is mainly to segregate the array in two halves. One half contains all the even numbers and one half contains all the negative numbers. Naive Method:- The most naive method is to allocate a separate empty array and then we fill it as…

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the basic 2 methods to approach this problem here:- Find majority element. (Method 1) Find majority element. (Method 2 , using sorting) It is recommended to have a look…

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 We discussed the most naive method to achieve this in our previous post. To improve the time complexity of our problem we can apply sorting technique. If we sort the array,…

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted. Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8. Output: Majority Element = 8 The most basic method of solving this problem is to take two loops and maintain a count of each of the element. If the count reaches more than (n/2) for any…

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 We discussed the basic method to find the number of occurrences in this post. But here, in both the cases, the time complexity is not good. We can use some of the tricks studied earlier to find a time efficient method. What we can do is:- Find the first occurrence of the element. Find…

Question: Given a sorted array of n elements, possibly with duplicates, find the number of occurrences of an element. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Count = 3 The most basic methodology to solve this problem is linear search. Just scan the array and count the number of occurrences. But this takes time O(n). We can improve the time complexity by using binary search. The steps involved in this method are:- Do a binary search and search for the data in the…

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the last occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 4 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the last occurrence in the array, the number to the right of it must be larger. We…

Question: Given a sorted array A of n elements, possibly with duplicates, find the index of the first occurrence of a number in O(log n) time. Input: 4, 4, 8, 8, 8, 15, 16, 23, 23, 42. Find 8 Output: Index = 2 (0 based indexing) This problem is very much similar to the binary search problem. We can apply the same methodology with just an added condition. For a number to be the first occurrence in the array, the number to the left of it must be smaller. We…