Given a matrix of size n x m filled with 0′s and 1′s e.g.: 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 if the matrix has 1 at (i,j), fill the column j and row i with 1′s i.e., we get: 1 1 … Read More →
Replace every element with the next greatest
Given an array of integers, replace every element with the next greatest element on the right side in the array. Replace last element with 0 as there no element on the right side of it. eg. if the array is {6, 7, 4, 3, 5, 2}, output {7, 5, 5, 5, 2, 0} Method 1 … Read More →
The Coin Problem – Dynamic Programming
Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way … Read More →
Rotate an array by d elements
Problem: Write a program that will rotate a given array of size n by d elements. eg: 1 2 3 4 5 6 7 and d = 3 Output : 4 5 6 7 1 2 3 Method 1: For rotating the array by d elements, first rotate it by 1. Move a[1] to a[0], … Read More →
Find row with maximum number of 1s in sorted matrix
Problem: You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s. eg. matrix given: 000111 001111 011111 000011 111111 // row with max number of 1′s Method 1: Brute force approach Traverse the matrix row wise and count … Read More →
Find the number occurring odd number of times in an array
You are given an array of integers. All the numbers in array occurs even number of times except the one which occurs odd number of time. You have to find the number in O(N) time and constant space. For eg. 1,4,6,7,3,1,4,7,3,1,6 (given array) Output: 1 Solution: Take bitwise XOR of all the elements. We will … Read More →
Print Pairs with the given difference in sorted array
Given a sorted array and a number k. print all pairs in the array with difference between them is k. Solution 1: Using Hash Map Create a hashmap and then traverse the array. Use array elements as hash keys and enter them in hashmap. Traverse the array again and look for value k + arr[i] … Read More →
Merge k sorted arrays
Given k sorted arrays of size n,merge them into an output array which is sorted. Solution (Using Min Heap): This solution is similar to method 4 of this post. Steps: i. Create a min heap of size k of first element of each array. Repeat steps from 2 to 4 n*k times: ii. Take the … Read More →
Pythagorean triplets in an array
Given an array of integers . Write an algorithm to find all the Pythagorean triples. Eg : i/p : int arr[ ] = {1,3,4,5,6,7,8,10,11} o/p: Print 3,4,5 and 6,8,10 Solution: Steps: (1) First square each element. (2) Sort the array in ascending order. This takes O(n log n). (3) Now consider each element a[ i … Read More →
Convert sorted array to balanced binary search tree
Problem : Given a sorted array . Write a program to create balanced BST from the sorted array. We know that the in-order traversal of binary search tree gives the elements in sorted order. This tells us that the middle element of array will be the root. We can create left and right subtree by … Read More →
Kth largest or smallest element in an array
Write an C program to find kth largest element in an array. Elements in array are not sorted. example, if given array is [1, 3, 12, 19, 13, 2, 15] and you are asked for the 3rd largest element i.e., k = 3 then your program should print 13. Method 1 Use sorting. Return first … Read More →
Longest Increasing Subsequence
Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example : {10, 25, 9, 30, 21, 55, 40, 60, 75} Here Length of LIS … Read More →
What’s going on ?