For example the input array is : int [ ] arr = {2, -9, 5, 1, -4, 6, 0, -7, 8}; Output: Maximum sub array sum is 9. Please check the following Algorithm for a better understanding : In this case the output sub array starts from 5 (index : arr[2]) and ends in 9 (index : arr[8]). Check the following step by step calculation. 1. 5, 1, -4, 6, 0, ...
Read MoreThis is a very general class of problem with many variations. The premise however stays the same. The input array consists of integers, some of which maybe duplicates. We are supposed to print all the unique numbers present in that array. Eg, int a[] = {23, 56, 56, 7, -19, 23, -19} Expected output : {23, 56, 7, -19} Solution : The naive soluti...
Read MoreGiven two sorted arrays, find their union and intersection. For example, if the input arrays are : arr1[] = {1,2,3,4,5,7,9} arr2[] = {2,4,6,8,9,10} Then your program should print Union { 1 2 3 4 5 6 7 8 9 10 } and Intersection as { 2 4 9 }. For Union : a) Use two variables i and j for iterating, initial values i = 0, j = 0 b) If arr1[i]...
Read MoreGiven three sorted arrays array1[] = {10, 50, 100, 200, 400, 800}; array2[] = {60, 70, 200, 800, 1000}; array3[] = {30, 40, 150, 200, 300, 700, 800, 1200}; Logic : 1) Take a single Loop and iterate over the elements by checking the size of all the arrays,iterator variable i,j,k 2) if the element at the given index are same increment 1++,j++...
Read MoreGiven an array of integers, Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example: Consider the following Input Array: { 10, 34, 5, 15, 9, 2 } Output: Leaders are- 34 15 9 2. As 34, 15 , 9 are greater than all th...
Read MoreWe have two integer arrays where one array is duplicate of another array with just 1 element missing. We need to find the missing element. There are 2 algorithms described in this article to solve the problem. Consider the following example Input : int[] array1 = {5, 2, 4, 6, 7, 9, 22}; int[] array2 = {2, 22, 6, 5, 9, 7}; Output : Missing Number...
Read MoreHere we have an array of positive and negative integers and a number k. We need to find all the pairs in the array which sums to k. As the array is of unique integers so we do not have any duplicate values. Consider the following example, where we have an input array as: int [ ] arr = {1,3,-5,9,4,5,6,7,11,15,-1,8} and k = 10. So the output pairs ...
Read MoreThe first solution for this problem will come to your mind will be sort the array in ascending/ descending order and multiply the largest 3 numbers. But wait here the twist comes in this problem. Does your function work with negative numbers? If your input array is [-10,-10,5,3,2] then the largest product of 3 is (-10*-10*3) not (2*3*5). To brute f...
Read MoreGiven an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. Examples: i. For any array, rightmost element always has next greater element as -1. ii. ...
Read More