Category: Arrays

Find the first repeating character in a given string

Objec­tive: Given a string, write an algo­rithm to find the first repeat­ing char­ac­ter in it. Exam­ple: String input = “hori­zon tuto­ri­als” Out­put: ‘o’ String input = “algo­rithms” Out­put: No repeat­ing char­ac­ter found. Approach: Naive approach:…

Find longest Snake sequence in a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one…

2D Matrix with Obstructions in it">Dynamic Programming — Count all paths in 2D Matrix with Obstructions in it

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down.…

Dynamic Programming — Count all paths from top left to bottom right of a mXn matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down. Example:…

Reverse the given Array without using built in function

Objec­tive: Given a array, write an algo­rithm to reverse the array. Exam­ple: int a[] = {1, 2, 3, 4, 5} Out­put: {5, 4, 3, 2, 1} Approach: It’s obvi­ous that you can­not use any built-in…

Print All Diagonals of a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix. Exam­ple: Approach: We will solve this prob­lem in two parts. first half of diag­o­nals and sec­ond half of diagonals.…

Dynamic Programming — Edit Distance Problem

Objec­tive: Given two strings, s1 and s2 and edit oper­a­tions (given below). Write an algo­rithm to find min­i­mum num­ber oper­a­tions required to con­vert string s1 into s2. Allowed Oper­a­tions: Inser­tion — Insert a new character.…

Dynamic Programming — Coin In a Line Game Problem

Objec­tive: In this game, which we will call the coins-in-a-line game, an even num­ber, n, of coins, of var­i­ous denom­i­na­tions from var­i­ous coun­tries, are placed in a line. Two play­ers, who we will call…

Dynamic Programming — Highway Billboard Problem

Objec­tive:  Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by…

Dynamic Programming — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

Kadane’s Algorithm — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

Shortest Range in K-sorted Lists

Objec­tive: You have k lists of sorted inte­gers. Find the small­est range that includes at least one num­ber from each of the k lists. This is very nice and tricky solu­tion, This prob­lem was asked in…

Generate Maximum revenue by selling K tickets from N windows

Objec­tive: Given ‘N’ win­dows where each win­dow con­tains cer­tain num­ber of tick­ets at each win­dow. Price of a ticket is equal to num­ber of tick­ets remain­ing at that win­dow. Write an algo­rithm to sell…

Dynamic Programming — Longest Common Substring

Objec­tive: Given two string sequences write an algo­rithm to find, find the length of longest sub­string present in both of them. This prob­lem has been asked in Ama­zon and Microsoft inter­views. Approach to solve this…

Dynamic Programming — Longest Common Subsequence

Objec­tive: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them. These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft,…

Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can…

Dynamic Programming — Longest Increasing Subsequence

Objec­tive: The longest Increas­ing Sub­se­quence (LIS) prob­lem is to find the length of the longest sub­se­quence in a given array such that all ele­ments of the sub­se­quence are sorted in increas­ing order. OR Given a…

Backtracking — N Queens Problem — Better Solution

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

Find the Kth Smallest/Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the Kth Smallest/largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; K=4. 4th small­est ele­ment in given…

Priority Queue Implementation

Ear­lier in we have seen Min-Heap and Max-Heap Imple­men­ta­tion. Pri­or­ity Queue is its built-in imple­men­ta­tion in Java. In this arti­cle we will see how to per­form Min-Heap and Max-Heap using Pri­or­ity Queue. Brief: A priority…

Find the Second Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the sec­ond largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; Sec­ond largest Ele­ment : 44 Approach:…

Sort Names by their Last Names.

Objec­tive: Given a list of names ( first name and last name), sort the list by their last names. Exam­ple: List [] = {“Daen­erys Tar­garyen”, “Jon Snow”, ” Tyrion Lan­nis­ter”, ” Jof­frey Baratheon”} Out­put: [Joffrey…

Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array. Exam­ple : int[][] A = new int[5][]; A[0] = new int[] { 1, 5, 8, 9 }; A[1] = new…

Find a Number occurring odd number of times in a Given array

Objec­tive: Given a array of inte­gers, in which every ele­ments occurs even num­ber of times except one num­ber which occurs add num­ber of times. Find out that num­ber. Exam­ple:   int[] A = {…

Rearrange the Array of Given Range N, such that A[i]=i

Algo­rithms — Rearrange the Array of Given Range N, such that A[i]=i. Objec­tive: Given a array of length N, in which ele­ments are in the range of 1 to N. All ele­ments may not…

XOR Method">Find a Missing Number From a Sequence of Consecutive Numbers | XOR Method

Input:  Array, arrA[] with a miss­ing num­ber and Range Out­put : miss­ing num­ber Exam­ple: int A[] = { 1, 2, 7, 6, 3, 4 }; int range = 7; Out­put: MIss­ing No is :5 In…

Binary Min — Max Heap

A binary heap is a heap data struc­ture cre­ated using a binary tree. binary tree has two rules — Binary Heap has to be com­plete binary tree at all lev­els except the last level. This…

Magic Index — Find Index In Sorted Array Such That A[i] = i.

Objec­tive: Given a sorted array of dis­tinct inte­gers, Find the Magic index or Fixed point in the array. Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index…

Find All the Well Ordered Permutations of a Given String.

Objec­tive: Write an algo­rithm to Print All the Well Ordered Per­mu­ta­tions of a Given String. What is Well Ordered String: When all the alpha­bets in a string occur in the increas­ing order irre­spec­tive of…

Find Increasing Triplet Sub-sequence

Objec­tive: Given an inte­ger array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Exam­ple : int arrA[] = { 10, 9,…

Construct a Special Triangle from a Given Array

Objec­tive: Given an array of inte­gers such that first level will print all the ele­ments in the array and from then at each level num­ber of ele­ments will be one less than the previous…

Print All the Subsets of a Given Set (Power Set)

Objec­tive: Given a set of num­bers, print all the poss­si­ble sub­sets of it includ­ing empty set. Power Set: In math­e­mat­ics, Pow­er­Set of any given set S, PS(S) is set of all sub­sets of S including…

Print All Combinations of subset of size K from Given Array

Objec­tive: Given an array of inte­gers of size N, print all the sub­sets of size k. (k<=N) Exam­ple: Gen­er­ate all sub­sets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5…

Track the Maximum Element in a Stack.

Objec­tive: In a Stack, keep track of max­i­mum value in it. It might be the top ele­ment in the stack but once it is poped out, the max­i­mum value should be from the rest…

Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: — Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”. Exam­ple: Given n=2 Out­put: (()) ()() Approach:

Counting Sort

Count­ing Sort is an sort­ing algo­rithm, which sorts the inte­gers( or Objects) given in a spe­cific range. Algo­rithm: Time Com­plex­ity O(n) Take two arrays, Count[] and Result[] and given array is input[]. Count[] will store the…

Find The Missing Duplicate in a Given Array.

Objec­tive: — Given an Inte­ger array. Array con­tains dupli­cates of all the num­bers in array except one num­ber . Find that num­ber. Exam­ple : int [] A = { 2,1,3,5,5,3,2,1,6,7,7,8,8}; Out­put : Miss­ing duplicate…

OR use only Max() function.">Sort 3 Integers without using if condition OR use only Max() function.

Objec­tive: — Given three inte­gers, sort them with­out using if con­di­tion. Appraoch: Say 3 inte­gers are, a, b, c. Find the max­i­mum of a, b, c using Max() func­tion. mul­ti­ply all inte­gers by –1. Again…

Implement Queue Using Stacks

Objec­tive: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objec­tive is to imple­ment queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used…

Depth First Search/Traversal in Binary Tree

Objec­tive: — Given a Binary Search Tree, Do the Depth First Search/Traversal . Appraoch: Approach is quite sim­ple, use Stack. First add the add to Stack. Pop out an ele­ment from Stack and add its right…

Check if Array Contains All Elements Of Some Given Range

Objec­tive: Given an array of unsorted num­bers, check if it con­tains all ele­ments of some given range. Exam­ples: int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 }; Range : 12–15 Output:…

Check if Array is Consecutive Integers

Objec­tive: Given a array of unsorted num­bers, check if all the num­bers in the array are con­sec­u­tive num­bers. Exam­ples: int [] arrA = {21,24,22,26,23,25}; — True (All the inte­gers are con­sec­u­tive from 21 to…

In an Array, find the Contiguous Subarray with Sum to a Given Value.

Objec­tive: Given an array and an inte­ger, find the Sub­ar­ray whose sum is equal to the given inte­ger. Exam­ples: int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 }; Integer =…

In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objec­tive: Given an array and an inte­ger, find the small­est sub­ar­ray whose sum is greater than the given inte­ger. Exam­ples: arrA[] = { 1, 5, 20, 70, 8} Inte­ger = 97 Out­put : Min…

Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or…

Find intersection between Two Sorted Arrays.

Objec­tive: Given two sorted arrays, Find inter­sec­tion point between them. Exam­ples: int[] a = { 1, 2, 3, 6, 8, 10 }; int[] b = { 4, 5, 6, 11, 15, 20 }; Output:…

Find Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array Exam­ple: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Out­put: The 4th small­est ele­ment is : 8 Approach: Naive…

Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Objec­tive: Given an array arrA[], find the max­i­mum j – i such that arr[j] > arr[i]. Exam­ple: int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 }; Out­put: Max(j-i)…

Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Objec­tive: Given an array of size of N and num­ber k. Find all ele­ments in an Array which appears more than N/K times. Input: Array [] and num­ber k. Exam­ple: int[] arrA = { 2, 2,…

Search an Element in a Rotated Sorted Array

Input: Rotated Sorted Array. What is Rotated Sorted Array. A sorted array is rotated around some pivot ele­ment. See the Exam­ple Below, array is rotated after 6. Approach: