Arrays

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…

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) Let us assume that the given array is arr[]. The basic approach for this problem will be:- Find the pivot element. That means after which all elements are in ascending order. This basically…

Question: Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. ? Input: arr [] = {1, 60, -10, 70, -80, 85} Output: -80, 85 (Their sum is -5 that is closest to 0(zero)) What we discussed was the most naive approach by using two for loops. However, this method is not optimized and will take a lot of time if the data is very large. We need to improve the complexity of the program. One such method is…

Question: Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. ? Input: arr [] = {1, 60, -10, 70, -80, 85} Output: -80, 85 (Their sum is -5 that is closest to 0(zero)) We can solve this problem by a brute force approach. That involves two loops, in the first loop we pick an element from the array and in the second loop we add this element individually with each of the other elements in the array. In…

Question: Given an array of n elements. Find two elements such that their sum is equal to a given element ‘K’ ? Input: arr [] = {42, 23, 15, 16, 8, 4} and element K = 58 Output: 16, 42 We discussed the approach to this problem using 2 loops in this post. But obviously this was not a good approach as it had a time complexity of O(n2). The time taken to solve such a problem if the array has elements in range of million will be very high.…