Arrays

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…

Question: Given a matrix that is sorted in row wise and column wise, find a number if present in the most efficient way. Input: Find if 54 is present in matrix. 4 8 15 16 23 6 9 20 21 44 8 11 24 26 49 9 13 25 27 54 10 17 29 30 66 Output: Present Method 1(Brute force):- Here, we use two loops search the element in entire matrix. Its a linear search so its not an efficient way to solve this problem. Time Complexity:- O(rows *…

Question: Write a program in C to print the given matrix in spiral order. Input: 1    2    3    4 5    6    7    8 9   10   11  12 13  14  15  16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6  7 11 10 Printing a matrix in spiral order can be better understood by the following image. Thus, printing a matrix in spiral order is just a way to traverse the matrix. The matrix can be supposed to be…

Question: Given a sorted array of n integers that has been rotated an unknown number of times, give a O(log (n)) solution that finds an element in the array? Input: arr [] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}. Find 5 . Output: 8 (the index of 5 in the array) We can solve this problem in only one scan of the array as well. Please read Method 1 if you have not done so, as this forms the base of this problem. To…

Question: Given a sequence of integers, find the median of the integers? Input: arr [] = {15, 23, 4, 16, 8, 42}. Find median. Output: 15 Since the question does not specify anything we cannot assume that the given array is a sorted one. The definition of median is the (n/2)th element of a sorted sequence of integers. This definition makes our approach simpler. All we need to do is sort the integers and then return the (n/2)th element. Here is the code for above approach. I use quick sort…