Tag Archives: Array

Mountain Array

Problem Given an array of integers, check if it is a mountain array or not. An array is called a mountain array if: Length of array >= 3 There exists some i with 0 < i < (length of array) – 1 such that: arr < arr < … < arr[i – 1] < arr[i] arr[i] > arr[i… Read More »

Find triplet having maximum product in an array

Problem Find 3 numbers from the array such that their product is maximum. Sample Input [1,2,2,2] Sample Output 8 Approach We can sort the given array and end up on 2 cases: Case 1: The maximum product is obtained by the last 3 numbers. Case 2: The maximum product is obtained by the first 2 numbers and the… Read More »

Find the minimum index of a repeating element in an array

Problem Given an array of integers, find the first repeating element in it. We need to find the element that occurs more than once and whose index of first occurrence is smallest.  Sample Input [1, 2, 2, 1] Sample Output  1 Explanation 1 is the first one occurring twice. Approach We can use sets to solve this efficiently.… Read More »

Find a pair with a minimum absolute difference in an array

Problem Given an unsorted array, find the minimum difference between any pair in a given array and print the array. Sample Input [1, 2, 2, 1] Sample Output 1 1 Approach Sort array in ascending order. Initialize the difference as INT_MAX. Compare all adjacent pairs in a sorted array and keep track of the minimum difference and update… Read More »

Find two non-overlapping pairs having the same sum in an array

Problem Given an unsorted array of integers. The task is to find any two non-overlapping pairs whose sum is equal. Two pairs are said to be non-overlapping if all the elements of the pairs are at different indices. Sample Input [1, 7, 9, 3] Sample Output 1 9 7 3 Explanation They both have sum as 10 Approach… Read More »

Modular Exponentiation in Logarithmic Time

Problem Given three integers, a, b, and p. Compute the value of (ab)%p. Sample Input a = 2, b = 3, p = 5 Sample Output 3 Explanation (23)%5 = 8%5 = 3 Why study modulo mathematics Modulo maths is widely used in various problems. For instance, if the answer gives the integer overflow, problem setters use modulo… Read More »

Count subarrays with given XOR

Problem Given an array of integers, count the number of subarrays that have the XOR equal to ‘x’. Sample Input [4, 2, 2, 6, 4] ‘x’ = 6 Sample Output 4 Explanation [4, 2], [4, 2, 2, 6, 4], [2, 2, 6],  are the subarrays with XOR equal to 6 Approach We can use hashmaps and prefix… Read More »

Find K-th Smallest Element in BST

Problem Given a Binary Search Tree, find the k-th smallest element in the BST. Sample Input K = 2 Sample Output 10 Approach We know that the inorder traversal of a BST gives a sorted order of the nodes. Therefore, we can perform the inorder traversal of the given tree and keep track of the number of nodes… Read More »

Print all subarrays of an array having distinct elements

Problem Given an integer array, print all maximum-sized subarrays having all distinct elements in them. Sample Input [1, 2, 3, 4, 3] Sample Output [1, 2, 3, 4] [4, 3] Approach We can initially iterate until we find a duplicate element. We will obtain a window that has all unique elements. From here, we move the left end… Read More »

Find two numbers with maximum sum formed by array digits

Problem Given an integer array having digits between 0 and 9, find two numbers with maximum sum formed using all the array digits. The difference in the number of digits of the two numbers should be ± 1. Sample Input [3, 4, 5, 6] Sample Output 64 and 53 Approach It is obvious that the largest possible number… Read More »