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[0] < arr[1] < … < arr[i – 1] < arr[i] arr[i] > arr[i… 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 »

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], [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 »